0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are you forgetting the possibility that two boxes could be empty? Don't forget the inclusion-exclusion principle! $\endgroup$ – Lord Shark the Unknown Apr 4 '18 at 19:22
  • $\begingroup$ 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? $\endgroup$ – Francisco José Letterio Apr 4 '18 at 19:27
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow am I dumb. Thanks! $\endgroup$ – Francisco José Letterio Apr 4 '18 at 19:43
  • $\begingroup$ Not at all. These things are endlessly confusing. Your method was basically sound and your instinct (to check small $n$) was spot on. $\endgroup$ – lulu Apr 4 '18 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.