Se7en Balls and Boxes

Let $X_n$ denote the number of ways of doing it with n balls in n boxes, so $X_0 = 1$ vacuously. Then, it is easy to see $X_1 = 1, X_2 = 2$ .

It is easy to see that $X_n$ is also the number of ways of doing it with more than n boxes. We will prove the recurrence formula:

$X_{n+1} = \sum_{k = 0}^n \binom{n}{k} \times X_k$ .

This is true because a boxing of the n+1 balls corresponds to a selection of n-k balls to go with ball n+1 (the binomial coefficient), along with a boxing of the remaining k balls in the other boxes (the $X_k$ factor), for any value of k (summation).

It is easy to run this formula to get the sequence 1,1,2,5,15,52,203,877.

Consider the general case of the number of ways to distribute balls labeled $1, 2, \ldots, n$ among $n$ indistinguishable boxes, which we will denote $B(n)$ . Then each arrangement corresponds to a distinct grouping of the balls into $k$ of the $n$ boxes, for some $1 \le k \le n$ . Because of this, we note that as long as the number of boxes is at least as large as the number of balls, the number of essentially distinct arrangements is the same (i.e., empty boxes are indistinguishable).

Now consider the box that contains ball number $n$ . For each $j = 0, 1, 2, \ldots, n-1$ , there are $\binom{n-1}{j}$ ways to choose $j$ of the $n-1$ other numbered balls to place in the same box. Of the remaining $n - j - 1$ balls, there are $B(n-j-1)$ ways to distribute them among the remaining $n-1 \ge n-j-1$ boxes. (If there are no balls remaining, then clearly we should have $B(0) = 1$ .) Hence $B(n) = \sum_{j=0}^{n-1} \binom{n-1}{j} B(n-j-1), \quad n \ge 1.$ Using this formula, we can recursively compute $\begin{aligned} B(1) &= B(0) = 1, \\ B(2) &= B(1) + B(0) = 2, \\ B(3) &= B(2) + 2B(1) + B(0) = 5, \\ B(4) &= B(3) + 3B(2) + 3B(1) + B(0) = 15, \\ B(5) &= 52, \\ B(6) &= 203, \\ B(7) &= 877, \end{aligned}$ the last of which is the desired answer. The numbers $B(n)$ are known as Bell numbers.

Let denote F(a, b) the number of ways to distribute a balls exactly in b boxes (that is, no box remains empty). Evidently, when we put a+1 balls into exactly b+1 boxes we put the last ball into a new box (F(a, b) variants) or into a filled one box of (b+1) already filled ((b+1) (F(a,b+1) variants), and all the variants are different, that is F(a+1,b+1)=F(a,b)+(b+1) F(a,b+1). We can see that F(a,a)=1, F(a,1)=1, so we calculate recursively:
b=1: 1, 1, 1, 1, 1, 1, 1
b=2: 0, 1, 3, 7, 15, 31, 63
b=3: 0, 0, 1, 6, 25, 90, 301
b=4: 0, 0, 0, 1, 10, 65, 350
b=5: 0, 0, 0, 0, 1, 15, 140
b=6: 0, 0, 0, 0, 0, 1, 21
b=7: 0, 0, 0, 0, 0, 0, 1

The answer is the sum of the last column: 1+63+301+350+140+21+1=877 as we can fill any number of the given 7 boxes.

These are the well-known Bell numbers, but here is a ground-up solution.

Let f(n) be the answer to the general question for n labelled balls in n unlabelled boxes. Given an particular arrangement, we can sort the nonempty boxes according to the least-numbered ball within. This gives a unique correspondence between "balls in boxes" and sequences of disjoint subsets S 1, ..., S k partitioning {1, 2, ..., n} where S 1 contains 1 and each S i contains the smallest number not contained in S 1, ... S {i-1}.

Now, S 1 contains 1 as well as some subset of {2, 3, ..., n}. By relabelling the remaining balls {1, 2, ..., n} \ S 1 (in an order-preserving way), we see that the number of ways of choosing the remaining subsets S 2, ..., S k is equal to f(n - |S 1|). For a given choice of k = |S 1|, there are C(n-1, k-1) ways to choose S 1 of that size, since we must include 1. Collecting common values of |S 1| thus gives the recurrence

f(n) = C(n-1, 0) f(n-1) + C(n-1, 1) f(n-2) + C(n-1, 2) f(n-3) + ... + C(n-1, n-1) f(0).

Starting from f(0) = f(1) = 1 we easily calculate f(2) = 2, f(3) = 5, f(4) = 15, f(5) = 52, f(6) = 203, f(7) = 877.

Solution 1- The number of different ways to distribute n labeled balls into exactly k indistinguishable non-empty boxes, which I will call B(n,k), is given by the recurrence relation,

B(n,k) = B(n-1,k-1) + k B(n-1,k)

The reason this recurrence relation works can be illustrated recursively.

B(1,1)=1 because there is just one way to put one labeled ball into one unlabeled box.

Now suppose you know the number of ways to put n-1 labeled balls into k unlabeled boxes (and you also know the number of ways to put n-1 labeled balls into k-1 unlabeled boxes), and you want to add one more ball and use k boxes. You can either start with any of the B(n-1,k-1) combinations, and put the nth ball into a new box or else you can start with any of the B(n-1,k) combinations, and put the nth ball into a non-empty box.

For each of the B(n-1,k-1) combinations, there is just one way to add the new ball to a new box.

For each of the B(n-1,k) combinations, there are k ways to add the new ball to a non-empty box.

Thus the number of combinations B(n,k) is the sum of B(n-1,k-1) and k times B(n-1,k). The purpose now is to find B(7,7)

After an exhaustive algebra session, using the obtained equation, we can obtain B(7,7)=877.

Solution2- The general idea here is If you need to find the number of ways to put n labeled balls into k boxes, and the boxes can be empty, then just sum B(n,j), for j=1 to k. That is, we make seven cases. CASE 1- No box is empty. There is just one way of distribution, where every box has 1 ball. CASE 2- 1 box is empty. There is again, only one kind of permissible distribution, (1,1,1,1,1,2).So we divide a group of 7 balls into parts of (1,1,1,1,1,2) Number of ways to do this are 7!/2!5!=21. CASE 3- 2 boxes are empty. We have 2 permissible distributions- (1,1,1,1,3) and (1,1,1,2,2) The number of ways for these to occur are 7!/3!4! and 7!/2!2!2!3! respectively. =35+105=140. CASE 4- 3 Boxes are empty. Possible cases are- (1,1,1,4) , (1,1,2,3) , (1,2,2,2) And the ways for them to occur are- 7!/3!4!, 7!/3!2!2! , 7!/2!2!2!2! =35+210+105=350. Case 5- 4 boxes are empty.The cases are- (1,1,5) , (1,2,4) , (1,3,3) , (2,2,3) And the corresponding ways are 7!/5!2! , 7!/4!2! , 7!/3!3!2! , 7!/2!2!2!3! =21+105+70+105=301. CASE 6- 5 boxes are empty. We have the following ways- (1,6) , (2,5) , (3,4) The corresponding ways- 7!/6! , 7!/5!2! , 7!/4!3! =7+21+35=63. CASE 7- 6 boxes are empty. Clearly, there is only 1 way, where all balls go into 1 box. Summing them up, 1+21+140+350+301+63+1=877. Hence the answer.

For notational purpose let's denote $(a_1,a_2,a_3,a_4,a_5,a_6,a_7)$ as the setup of $a_i$ balls into box $i$ where $0 \leq a_i \leq 7$ . As the boxes are unlabelled, the order of the $a_i$ 's doesn't matter.

Case 0 : 0 empty boxes or (1,1,1,1,1,1,1) or exactly one ball in every box. Since the boxes are unlabelled this only has $\underline1$ solution.

Case 1 : 1 empty box or (0,2,1,1,1,1,1) which has ${7\choose2}=\underline{21}$ possibilities.

Case 2 : 2 empty boxes. From here on we get some more options. (0,0,3,1,1,1,1) with ${7\choose3}=\underline{35}$ possibilities and (0,0,2,2,1,1,1) with $\frac{{7\choose2}\times{5\choose2}}{2!}=\underline{105}$ possibilities.

Case 3 : 3 empty boxes. (0,0,0,4,1,1,1) with ${7\choose4}=\underline{35}$ possibilities, (0,0,0,3,2,1,1) with ${7\choose3}\times{4\choose2}=\underline{210}$ possibilities, (0,0,0,2,2,2,1) with $\frac{{7\choose2}\times{5\choose2}\times{3\choose2}}{3!}=\underline{105}$ possibilities.

Case 4 : 4 empty boxes. (0,0,0,0,5,1,1) with ${7\choose5}=\underline{21}$ , (0,0,0,0,4,2,1) with ${7\choose4}\times{3\choose2}=\underline{105}$ , (0,0,0,0,3,3,1) with $\frac{{7\choose3}\times{4\choose3}}{2!}=\underline{70}$ and (0,0,0,0,3,2,2) with $\frac{{7\choose3}\times{4\choose2}}{2!}=\underline{105}$ possibilities.

Case 5 : 5 empty boxes. (0,0,0,0,0,6,1) with ${7\choose6}=\underline7$ , (0,0,0,0,0,5,2) with ${7\choose5}=\underline{21}$ and (0,0,0,0,0,4,3) with ${7\choose4}=\underline{35}$ possibilities.

Case 6 : 6 empty boxes. (0,0,0,0,0,0,7} with $\underline1$ possibility.

Adding all underlined results we get a total of $\fbox{877}$ possibilties.

This can also be seen as the 7th Bell number where $B_7$ is the number of partitions of a set of size 7, with a partition of a set S being defined as a set of nonempty, pairwise disjoint subsets of S whose union is S. (Source wikipedia)

Stirling numbers of the second kind are the number of ways in which we can distribute 'n' distinguishable objects into 'k' non-empty sets. We can denote the Stirling numbers as S(n,k).

They can be calculated using the following recursive formula

S(n, k) = S(n−1, k−1) + S(n−1, k)

S(n, 1) is always 1 as there’s only one way to partition a set into one subset, which is to leave it alone.

S(n, n) is also always 1 as there’s only one way to partition a set of length n into n subsets, each of length 1.

We can also use the triangular array of Stirling values to find S(n,k)

(n \ k)- 0-1-2-3-4- 5-6-7-8- 9 -10

0-1

1-0 -1

2-0-1-1

3-0-1-3-1

4- 0-1-7-6-1

5-0-1-15 -25-10-1

6-0-1-31-90-65-15-1

7-0-1-63- 301-350-140-21-1

8-0-1-127-966-1701-1050-266-28-1

9- 0-1-255- 3025-7770 -6951-2646-462-36-1

10- 0-1-511-9330-34105-42525-22827-5880-750-45-1

We can divide the problem into 7 parts,i.e. the division of the 7 balls into

1)only 1 box=S(7,1)=1

2)only 2 boxes=S(7,2)=63

3)only 3 boxes=S(7,3)=301

4)only 4 boxes=S(7,4)=350

5)only 5 boxes=S(7,5)=140

6)only 6 boxes=S(7,6)=21

7)all 7 boxes=S(7,7)=1

The total number of ways of dividing the 7 distinct balls into 7 identical cells will be

= S(7,1)+S(7,2)+S(7,3)+...S(7,7)

which is = 1+63+301+350+140+21+1

= 877

We simply list all the different ways to group the seven balls. This is equivalent to listing all the partitions of $7$ . Then we compute the number of ways to order the balls in each specific grouping:

$7\rightarrow 1$

$6+1\rightarrow\binom{7}{6}=7$

$5+2\rightarrow\binom{7}{5}=21$

$5+1+1\rightarrow\binom{7}{5}=21$

$4+3\rightarrow\binom{7}{4}=35$

$4+2+1\rightarrow\binom{7}{4}\binom{3}{2}=105$

$4+1+1+1\rightarrow\binom{7}{4}=35$

$3+3+1\rightarrow\binom{7}{1}\binom{6}{3}/2!=70$

$3+2+2\rightarrow\binom{7}{3}\binom{4}{2}/2!=105$

$3+2+1+1\rightarrow\binom{7}{3}\binom{4}{2}=210$

$3+1+1+1+1\rightarrow\binom{7}{3}=35$

$2+2+2+1\rightarrow\binom{7}{3}\binom{6}{2}\binom{4}{2}/3!=105$

$2+2+1+1+1\rightarrow\binom{7}{2}\binom{5}{2}/2!=105$

$2+1+1+1+1+1\rightarrow\binom{7}{2}=21$

$1+1+1+1+1+1+1\rightarrow1$

Finally, we add all of the possible ways up to get $\boxed{877}$ .

Let $B_k$ be the number of ways to put $k$ numbered balls into $k$ unlabelled boxes. For an arrangement of balls in $B_k,$ we have some number of balls (say $m$ balls) in the same box as ball $k,$ and $k - 1 - m$ balls distributed amongst the other boxes. As $m$ ranges from $0$ to $k-1$ , we have that $B_k = \sum\limits_{i=0}^{k-1} \binom{k-1}{i} B_i.$ We clearly have $B_0 = B_1 = 1.$ Recursively calculating, we get

$\begin{array}{|r|cccccccc|} \hline k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline B_k & 1 & 1 & 2 & 5 & 15 & 52 & 203 & 877\\ \hline \end{array}$

Thus, there are $877$ ways to arrange the balls.

number of ways to put 7 unlabelled balls in k boxes $(k\leq7)$ is $\frac {1}{k!}\displaystyle \sum_{i=0}^k(-1)^{(k-i)}{k \choose i}i^n$ . summing the values for $k=1,2,....,7$ ,we get $877$

for a detailed discussion on the formula please visit wiki page

The boxes are indistinguishable, which means that two configurations are identical if they can be obtained from each other by permuting the boxes.

If we label the boxes by the number of balls they contain, then it is clear that any partition of 7, see here for partitions:

http://en.wikipedia.org/wiki/Partition (number theory)

defines a valid configuration and vice versa (because of the permutation symmetry).