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

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!

• After your acceptance I had a second look. In your comment on my question you asked whether $S_{2}^{n}=2^{n}-2$ was correct, and I said 'yes'. But it is not. The correct answer is $S_{2}^{n}=2^{n-1}-1$ i.e. half of it. By counting the number of non-empty subsets that have non-empty complements you count every partition twice. I will also put that in the answer I gave you. – drhab Jan 25 '14 at 18:42
• Can you please explain when we are double counting? – Hawk Jan 25 '14 at 18:45
• If every set $A$ with $A\neq \emptyset$ and $A^c\neq \emptyset$ is sent to partition $P=\{A,A^c\}$ then two sets are sent to the same partition: $A$ and $A^c$. This shows that the number of these sets is twice the number of partitions. Do you understand now? Just try it out on some simple cases (3 or 4 elements) and it becomes more easy to see. – drhab Jan 25 '14 at 18:58
• Yes...I actually understand it now very clearly! – Hawk Jan 25 '14 at 18:59
• Though not a duplicate, but this question is closely related to this one. – Mars Jun 16 '17 at 16:50

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.

• My logic was:There are $n$ elements and $2$ subsets. So,each element belongs to either first set or the second set. So,$2^n$ – Hawk Jan 25 '14 at 11:39
• Was the logic wrong? – Hawk Jan 25 '14 at 11:40
• Logic is okay, but then the possibility that all elements belong to the first set is included. And also the possibility that all elements belong to the second set. In these cases there is no partition in $2$ disjoint nonempty sets, since one of them is empty. – drhab Jan 25 '14 at 11:43
• so,we can subtract the $2$ cases, so the answer is $2^n-2$. Now, is the logic okay? – Hawk Jan 25 '14 at 11:44
• Yes. That is the right answer. – drhab Jan 25 '14 at 11:45

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

• The subscript $k$ in $S_k^n$ denotes the number of classes in the partition, so $S_1^n$ would be 1, not $n$ (only one way to put all $n$ things into one class). – hardmath Jan 25 '14 at 13:00