# Why does this not hold? (partitioning sets into nonempty subsets)

I stumbled upon the following problem in an introductory course to Computer Science (this is a first glimpse of Stirling numbers for first year students):

In how many ways can we partition a set of n elements into 2 non-empty subsets? How many ways for 3 subsets?

It is easy to think of this as the way of distributing $n$ numbered balls into $2$ undistinguishable boxes, where no box is empty. This is $\frac{2^n - 2}{2!} = 2^{n-1} -1$, because first we distribute the numbered balls in numbered boxes, substract the 2 cases with an empty box, and divide by (amount of boxes)!

So when moving on to 3 nonempty subsets we can think of distributing n numbered balls in 3 numbered boxes, substracting the cases in which a box is empty, and dividing everything by 3!

The number of cases in which a box is empty should be ${3 \choose 1} \cdot (2^{n-1} - 1)$ which means that I choose a box that will be empty in 3 different ways and then distribute the n balls in two boxes such that no box is empty (which is the number we calculated before).

So we get $\frac{3^n -3 (2^{n-1} - 1)}{3!}$ as a result.

It is easy to see however that this does not hold, for example, for n=3, since this would imply that there's 3 ways of partition a set of 3 elements into nonempty subsets

Where does my argument fail?

• Are you forgetting the possibility that two boxes could be empty? Don't forget the inclusion-exclusion principle! – Lord Shark the Unknown Apr 4 '18 at 19:22
• But if I choose a box to be empty and distribute the balls between two boxes such that none of those two boxes are empty, how could two boxes be empty? – Francisco José Letterio Apr 4 '18 at 19:27

You divide by $2$ once (in computing the $2-$ box case) and then again when you divide by $3!$. Also, you neglect the case where only one box is filled.
Your method should work, though. First, assume the boxes are distinguishable. Then there are $3^n$ ways to distribute the balls with no restriction. We must then subtract the $2-$box case, which means subtracting $3\times (2^n-2)$. And then we must subtract the $1-$box case, which means subtracting $3$. At this point we can divide by $3!$ Thus we have $$\frac {3^n-3\times (2^n-2)-3}{3!}$$
Taking $n=3$ yields $$\frac {3^3-3\times (2^3-2)-3}6=\frac {27-18-3}6=1$$ as desired.
Sanity check: the formula yields $6$ when $n=4$. Is that correct? Well, the division is entirely determined by knowing which $2$ objects go in the box which contains $2$, hence the answer in this case is $\binom 42=6$ as predicted.
• Not at all. These things are endlessly confusing. Your method was basically sound and your instinct (to check small $n$) was spot on. – lulu Apr 4 '18 at 19:44