Inductive proof that $S_{m,2} = 2^{m-1} - 1$ (splitting sets)

Question

$S_{m,l}$ is the count of possibilites to split a set of $m$ elements into $l$ not-empty sets ($m,l ≥ 1$).

Obviously, $S_{m,1} = 1$ for all $m ≥ 1$

How to proof inductively over $m$ that $S_{m,2} = 2^{m-1} - 1$

Let me give you an example for this:

M = {a,b,c,d}

m = 4 (because M has 4 Elements)

$S_{4,2} = 2^{4-1} - 1 = 7$ (So we can split M into 7 different not-empty 2-sets). Those were:

1. $\{a\},\{b,c,d\}$
2. $\{b\},\{a,c,d\}$
3. $\{c\},\{b,a,d\}$
4. $\{d\},\{b,c,a\}$
5. $\{a,b\},\{c,d\}$
6. $\{a,c\},\{b,d\}$
7. $\{b,c\},\{a,d\}$

Answer 1

Note that $$ S_{m+1, 2}= S_{m,1}+2S_{m,2}=1+2S_{m,2}\tag{1} $$ by classifying the set of partitions of $[m+1]$ into two blocks based on the placement of $m+1$. Either $m+1$ is in its own block (there are $S_{m,1}$ such partitions) or $m+1$ is not in its own block (in which case partition $1,\dotsc,m$ into $2$ blocks and there are two choices for which block $m$ belongs to).

Equation one together with the inductive hypothesis implies the result.

Answer 2

You can count the number of subsets, i.e. the power set of an $m$-element set, then substract $2$ from the cardinality of the power set because you do not want to include the empty set and the whole set, and then you divide by two. This is equivalent to splitting the set. Each element, except for the empty set and the whole set, in the power set corresponds to a split, since you split the set in the element $A\in\mathcal{P}(\{1,\ldots,m\})$ from the power set and its complement $A^C$ in $\{1,\ldots,m\}$. Since you do not want to count double, you have to divide this power set cardinality by two since otherwise you cound a subset $A$ twice: you also count its complement, but splitting the set in $A$ and $A^C$ is of course the same split as splitting in $A^C$ and $A$.

So actually you are looking for an induction argument for the cardinality of the power set of a finite set. This is equal to $2^m$, with $m$ the cardinality of the finite set. The base step is clear: the empty set (having zero elements) has only the empty set as a subset. Then suppose each $m$ element set has $2^m$ subsets, and consider an $m+1$ element set. For each subset of the first $m$ elements, you can either include or exclude the $m+1$th element, giving $2$ possibilities, thus by the induction hypothesis there are $2\cdot2^m=2^{m+1}$ such subsets. Now the result follows by induction on $\mathbb{N}$.

Answer 3

Base case. $m=2$ gives $S_{2,2}=2^{2-1}-1=1$ which holds.

Inductive hypothesis. Assume true for $m$; that is $S_{m,2}=2^{m-1}-1.$

Inductive step. Now, let's see where we get with $m+1$. Here, we use the Stirling recurrence $$S_{n,k}=kS_{n-1,k}+S_{n,k-1},$$ and get \begin{align*} S_{m+1,2}&=2S_{m,2}+S_{m,1}\\ &=2(2^{m-1}-1)+1\\ &=2^{m}-2+1\\ &=2^m-1, \end{align*} which is precisely what we wanted to prove.

I know this is slightly off-topic; but I will also give a combinatorial proof of this identity.

---

Consider $S_{m,2}=2^{m-1}-1$. The left hand side of course, counts the number of ways to partition a set of $m$ elements into two non-empty subsets. Now, let's consider two bins $A$ and $B$. If we first allow either bin to be empty; there are precisely $2^m$ ways to partition the set of $m$ elements into both bins. Now, let's remove some of these restrictions. Firstly, removing the condition that $A$ and $B$ can be empty rules out two of these arrangements, so we are left with $2^m-2$. Finally, removing the notion of ordering of the bins; we also must divide this number by $2$. This gives $$\frac{2^m-2}{2}=2^{m-1}-1,$$ which is the expression on the right hand side.

There is probably a more correctly worded statement of this proof elsewhere, but I just thought it would be nice to offer this up to you as well.