# Combinatorial proof of number of disjoint subsets

Fix positive integers $n$ and $k$. Find the number of $k$-tuples $(S_1, S_2,\dots, S_k)$ of subsets $S_i$ of $\{1, 2, \dots , n\}$ with the $S_i$’s pairwise disjoint.

I am looking for a way to find this combinatorially, instead of generating functions/recursion. The balls and boxes idea seems like the way to go, but the fact that every box needs one ball except the "unused numbers" box is causing me difficulty.

• What do you mean, "every box needs one ball"? Are the subsets $S_i$ required to be nonempty? Where does it say that in the problem you quoted? – bof Feb 3 '16 at 5:30
• If the sets $S_i$ are required to be nonempty, then you want to add two numbers: the number of surjections from $\{1,\dots,n\}$ to $\{1,\dots,k\}$ (no "unused numbers"), and the number of surjections from $\{1,\dots,n\}$ to $\{1,\dots,k+1\}$ (one or more "unused numbers"). To count the surjections, use either Stirling numbers (of the "second kind"), or the in-and-out formula ("Principal of Inclusion and Exclusion"). – bof Feb 3 '16 at 5:37
• I thought they couldnt be empty because they had to be pairwise disjoint, but that may not actually be the case, are two empty sets considered disjoint? – user310322 Feb 3 '16 at 5:54
• There is only one empty set, and it is disjoint from everything, including itself. I would interpret the quoted problem as allowing $S_1=S_2=\cdots=S_k=\emptyset$ as a possibility. – bof Feb 3 '16 at 6:00

We count the number of $(k+1)$-tuples of pairwise disjoint subsets whose union is all of $\{1,\dots,n\}$. This is the number of functions from the set $\{1,\dots,n\}$ to the set $\{1,\dots,k,k+1\}$. There are $(k+1)^n$ such functions.
The "extra box" $k+1$ gets the elements of $\{1,\dots,n\}$ that are not in any of the $S_i$.
• The OP's last sentence seems to imply that the subsets $S_i$ have to be nonempty, although the formal problem statement in the first paragraph does dot seem to make that requirement. I'm trying to get the OP to clarify the question. – bof Feb 3 '16 at 5:40