Number of partitions of an $n$-element set into $k$ classes

Question

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!

Answer 1

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.

Answer 2

$$S_0^{n}=1,S_1^{n}=n$$ $$S_k^{n+1}=S_{k-1}^n+kS_k^n,k>1$$ for $k=2$ we get that $$S_2^{n}=S_{1}^{n-1}+2S_2^{n-1}=n+2S_2^{n-1}$$ Solution for last recurrence is not correct because $S_2^{n}\neq2^n$

Answer 3

We can prove $S^n_2 = 2^{n-1} -1$ using Mathematical induction.

${\bf Base\ case} :\ n=1$

Clearly $S^1_2 = 0$ as number of classes need to be 2 but elements in set is 1.

${\bf Inductive\ step}:$ Assuming statement is true for $n=k$, now

Let $a_{k+1}$ is the new element that is added to set of size $k$ to create a new set of size $k+1$.

We can divide $k+1$ elements into 2 parts in two ways

1. $a_{k+1} \cup \{a_1,a_2,...,a_k\}$
2. appending $a_{k+1}$ to either of the 2 classes that we get from each $S^k_2$ partition.

In other words,

$S^{k+1}_2 = 1 + 2S^k_2$

But $S^k_2 = 2^{k-1}-1$

$\implies S^{k+1}_2 = 1 +2(2^{k-1}-1)$

$\implies S^{k+1}_2 = 2^{k}-1$

So, statement is true for $k+1$ and hence true for all natural numbers.