# Number of decompositions of a finite set into non-empty, pairwise disjoint sets.

This is a question from A.N. Shiryayev's Probability, Springer Graduate Texts in Mathematics (1984). This isn't for a homework assignment - I'm going through the book at my own pace and I'm having difficulty solving this problem. For those with the book (it's available free online from Springer), this is problem 2, page 16:

Let $\Omega$ contain $N$ elements. Define as $d(N)$ the number of decompositions of $\Omega$ i.e. the total number of ways that you can split the sample space into non-empty, pairwise disjoint sets, consisting only of elements of $\Omega$. Show that

$$d(N) = \sum_{k=0}^{N-1} C_{k}^{N-1} d(k)$$

given $d(0) = 1$. Use that to prove that

$$d(N) = e^{-1}\sum_{k=0}^\infty \frac{k^N}{k!}$$

by verifying that it satisfies the same recurrence relation.

• You need $C^{N-1}_k$, not $C_{N-1}^k$. ${}\qquad{}$ – Michael Hardy Jan 9 '16 at 1:13
• I think that the author has the notation flipped in the book. I'll rewrite it in that case. – baibo Jan 9 '16 at 1:16
• Which part are you having trouble with? – Brian Tung Jan 9 '16 at 1:17
• These are the Bell numbers. ${}\qquad{}$ – Michael Hardy Jan 9 '16 at 1:18
• @BrianTung I'm trying to prove that the first recurrence holds by induction. However, I don't see the combinatorial solution (if there even is one) to how $d(N+1)$ is written in terms of $d(N)$ and something else. I tried reverse engineering the solution - I wrote $d(N+1) = d(N) + ...$ and I tried to imagine what the missing part needs to be but that failed as well. Finally, I realised that for $d(N+1)$ the $C$ combinations would have a different value for their first argument ($N$ rather than $N-1$) so I gave up. – baibo Jan 9 '16 at 1:21

It can be explained by observing that, from an arbitrary partition of $n+1$ items, removing the set containing the first item leaves a partition of a smaller set of $k$ items for some number $k$ that may range from $0$ to $n$. There are $\binom{n}{k}$ $\left[ = C^n_k \right]$ choices for the $k$ items that remain after one set is removed, and $B_k$ choices of how to partition them.

There is also this page explaining "Dobiński’s formula", which is the second identity you give, although your proof using the fact that it satisfies the same recurrence relation would be different.

A long-ish comment on the first part: The recurrence is constructed along something like the following line of reasoning: The $N$th item can either be its own subset, or it can join a subset previously existing from a partition of the first $N-1$ items. Either way, $k$ is the number of elements not in the same subset as the $N$th item; that is, if the $N$th item is its own subset, $k = N-1$; if the $N$th item joins a subset of $m-1$ items (to form a subset of $m$ items), then $k = N-m$.

Since there are $C^{N-1}_k$ ways to choose a subset of $k$ items (equivalently, $N-k-1$ items) from a set of $N-1$ items, and in each case, the $k$ items not in a subset with the $N$th item can be partitioned in $d(k)$ ways, the total number of ways to partition $N$ items is

$$d(N) = \sum_{k=0}^{N-1} C^{N-1}_k d(k)$$

t.s. the total number of ways to partition $N$ items is

$$d(N) = \sum_{k=0}^{N-1} C^{N-1}_k d(k) \hspace{10 mm} where\hspace{2 mm} d(0)=1$$

proof by strong induction:

for N=1 the only decomposition is $D = \{1\}$ so $d(1)= d(0) =1$ and the base case is proven

For the $Nth$ case by the induction hypothesis $d(N-1)...d(1)$ is true and there are $N$ different ways we can add the $Nth$ element to a partition of size $N-1$ First we can add it as a set of size $1$. In this case there are $C^{N-1}_{N-1}$ ways of choosing the $N-1$ elements for the decomposition of size $N-1$ to which we are going to add the set $\{N\}$ whence it follows $$C^{N-1}_{N-1}d(N-1)$$

Next we can add the $Nth$ element in a set of size 2 to a decomposition of size $N-2$ and there are $C^{N-1}_{N-2}$ ways of choosing the $N-2$ elements for the decomposition of a set of size $N-2$ whence it follows $$C^{N-1}_{N-2}d(N-2)$$

similarly we can add the $Nth$ element in a set of size $i$ to a decomposition of a set of size $N-i$ in $C^{N-1}_{N-i}$ ways whence

$$C^{N-1}_{N-i}d(N-i)$$ continuing the process we can add the $Nth$ element to a set of size $N$ in $C^{N-1}_{0}$ ways whence

$$C^{N-1}_{0}d(0)$$ hence $$d(N) = \sum_{i=1}^{N} C^{N-1}_{N-i} d(N-i)$$ and then making the change of summation index $k=N-i$

$$d(N) = \sum_{k=0}^{N-1} C^{N-1}_k d(k)$$

Q.E.D