1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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 !
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Loading...