Number of Partitions of n-Element Set into k Classes – Combinatorics

combinatoricsset-partition

A partition of a set $S$ is formed by disjoint, nonempty subsets of $S$ whose union is $S$. For example, $\{\{1,3,5\},\{2\},\{4,6\}\}$ is a partition of the set $T=\{1,2,3,4,5,6\}$ consisting of subsets $\{1,3,5\},\{2\}$ and $\{4,6\}$. However, $\{\{1,2,3,5\},\{3,4,6\}\}$ is not partition of $T$.
If there are $k$ nonempty subsets in a partition, then it is called a partition into $k$ classes. Let $S_k^n$ stand for the number of different partitions of a set with $n$ elements into $k$ classes.

  1. Find $S_2^n$.

  2. Show that $S_k^{n+1}=S_{k-1}^n+kS_k^n$.

—

My work:
From the definition of $S$, $S_2^n=2^n$. I think I am wrong somewhere, because when I put this formula into the second part to prove, I get,
$$k^{n+1}=(k-1)^n+k \cdot k^n.$$
Please tell me where I am wrong. I think this problem cannot be solved by star-and-bar method as that method finds value for $k$ but does not prove it. Please help!

Best Answer

on(i):

$2^n$ gives you the number of all subsets of $S$, but you are looking for the number of subsets that are not empty and have no empty complement. Their total number is $2^n-2$. Note that a nonempty subset $A$ having a non-empy complement $A^c$ corresponds with partion $P=\{A,A^c\}$. However, $A^c$ corresponds with that partition too. So counting these sets gives twice the number of partitions. This amounts in: $$S_n^2=2^{n-1}-1$$ addendum on (ii)

Start with a set $S$ having $n$ elements. Now form $S'=S\cup\left\{ x\right\} $ where $x\notin S$. Partitions of $S'$ in $k$ classes can be made in two ways:

1) Let $\left\{ x\right\} $ be one of the classes. If $P$ is a partition of $S$ in $k-1$ classes then $P'=P\cup\left\{ \left\{ x\right\} \right\} $ is a partition of $S'$ in $k$ classes. Here there are $S_{k-1}^{n}$ possibilities.

2) Let $\left\{ x\right\} $ be not one of the classes. For every partition of $S$ in $k$ classes we can put $x$ in one of these classes wich will induce a partition of $S'$ in $k$ classes. There are $S_{k}^{n}$ such partitions and for $x$ there are $k$ candidates so there are $kS_{k}^{n}$ possibilities.

Related Question