Number of partitions for a finite set

[geoffrey159]

Homework Statement

Find a recursive relation on the number of partitions $P_n$ for a set $S_n$ of cardinal $n$. $P_0 = 1$ is given.

Homework Equations

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 ?

 

[Samy_A]

$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.

 

[geoffrey159]

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 ?

 

[Samy_A]

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 ?

Yes, that's exactly the method I used. Of course we could both be wrong (argumentwise), but the recursive relation is most certainly correct.

 

[geoffrey159]

Thank you very much !