1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of partitions for a finite set

  1. Dec 2, 2015 #1
    1. The problem statement, all variables and given/known data
    Find a recursive relation on the number of partitions ##P_n## for a set ##S_n## of cardinal ##n##. ##P_0 = 1## is given.

    2. Relevant equations


    3. The attempt at a solution
    A partition of ##S_{n+1}## is given by the choice of a non-empty ##k##-block ##A_k## of ##S_{n+1}## and a partition of ##S_{n+1} - A_k## which has cardinality ##n+1-k##, for all ##k \in [[ 1...n+1 ]]##. I find :

    ##P_{n+1} = \sum_{k = 1}^{n+1} {n+1\choose k} P_{n+1-k} = \sum_{k = 1}^{n+1} {n+1\choose n+1-k} P_{n+1-k} = \sum_{s = 0}^{n} {n+1\choose s} P_s ##

    But this formula is wrong and I don't understand why. What did I miss ?
     
  2. jcsd
  3. Dec 2, 2015 #2

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    ##n=4,n+1=5##
    ##S_{5}=\{1,2,3,4,5\}##
    Take your argument for k=2
    Non empty 2-block: ##A_2=\{1,2\}##, partition of ##S_{n+1-k} \setminus A_2##: ##\{\{3,4\},\{5\}\}##
    Non empty 2-block: ##A_2=\{3,4\}##, partition of ##S_{n+1-k}\setminus A_2##: ##\{\{1,2\},\{5\}\}##
    Take your argument for k=1
    Non empty 1-block: ##A_1=\{5\}##, partition of ##S_{n+1-k} \setminus A_1##: ##\{\{1,2\},\{3,4\}\}##

    So there is some double (or even more) counting going on in your argument.
     
    Last edited: Dec 2, 2015
  4. Dec 2, 2015 #3
    Thank you Samy, your answer is very clear ! I think that in order to avoid this double counting, I must impose that the ##k##-blocs ##A_k## contain a random element ##x\in S_{n+1}##.
    In which case, each ##A_k## is the union of ##x## and of a ##(k-1)##-block of ##S_{n+1}-\{x\}##, so that ##A_k## can be chosen in ##{ n \choose k-1}## ways. Finally,

    ##P_{n+1} =\sum_{k = 1}^{n+1} { n \choose k-1} P_{n+1-k} =\sum_{k = 1}^{n+1} { n \choose n+1-k} P_{n+1-k} =\sum_{s = 0}^{n} { n \choose s} P_{s}##

    Which looks much more plausible. What do you think ?
     
  5. Dec 2, 2015 #4

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Yes, that's exactly the method I used. Of course we could both be wrong (argumentwise), but the recursive relation is most certainly correct.
     
  6. Dec 2, 2015 #5
    Thank you very much !
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted