[Combinatorics] Divide n different balls into 3 identical boxes (can be empty)

I've figured that if there were only 2 identical boxes, the number of permutations would be

2^n / 2 = 2^n-1

Then if I join the 2nd and the 3rd boxed into the combined box, and assuming the first box contains some k balls, the combined box contains n-k balls hence 2^n-k-1 combinations, while the first box has C(n, k) combinations.

Summing all k from 0 to n we get:

Sigma(k=0 -> k=n) C(n, k) * 2^n-k / 2

According to Newton's binom thats 3^n / 2 and since the boxes (1st and the combined) are identical, we should divide by 2!, thats total of

3^n / 4 options However thats not quite right as for 3 balls and 3 boxes there are actually 5 possibilities, and according to my attempt there should be 27/4=6.75.

Where did I go wrong? :(

Posted Apr 13, 2013, 9:16 PM UTC

15
Loading comments…