How many ways are there to distribute 8 balls into 6 boxes with the first two boxes collectively having at most four balls?

How many ways are there to distribute eight balls into six boxes with the first two boxes collectively having at most four balls if:

a) The balls are identical.

b) The balls are distinct.

I'm thinking you have to use the stars and bars method, but don't know how to go about the restriction of only having collectively 4 balls in the first two boxes.

I'll solve the case in which the balls are identical. This is not the nicest solution, but it works and I hope it is clear.

Case 1: First two boxes have exactly four balls.

If the first two boxes together contain four balls, then we can use stars and bars twice. The number of ways to place four balls in two boxes is the number of ways to arrange $4$ stars and $1$ bar, or $5$ choose $1$. The number of ways to place the remaining four balls in the other four boxes is the number of was to arrange $4$ stars and $3$ bars, or $7$ choose $3$. This gives

$$\binom{5}{1}\binom{7}{3}$$

Case 2: First two boxes have exactly three balls. With the same reasoning, we get

$$\binom{4}{1}\binom{8}{3}$$

Case 3: First two boxes have exactly two balls.

$$\binom{3}{1} \binom{9}{3}$$

Case 4: First two boxes have exactly one ball.

$$\binom{2}{1}\binom{10}{3}$$

Case 5: First two boxes have no balls.

$$\binom{1}{1}\binom{11}{3}$$

(This makes sense because this is just stars and bars applied to putting $8$ balls into $4$ boxes)

Our total is therefore

$$5\binom{7}{3}+4\binom{8}{3}+3\binom{9}{3}+2\binom{10}{3}+\binom{11}{3}=\boxed{1056}$$

1) You have 5 cases, e.g. if there are 4 balls in the first 2 boxes it is $\binom{5}{1} \cdot \binom{7}{3}$, you can work out the rest.

2) There are $\binom{8}{4}$ ways to select 4 balls out of 8 that will go into the first 2 boxes. Then you will have $2^4 \cdot 4^4$ ways to allocate them; you can work out the remaining 4 cases.

a) Suppose indistinguible balls. For $k$ fixed, $k=0,1,2,3,4$, let us distribute the other $8-k$ in the boxes 3,4,5,6: $\binom{8-k+3}{3}=\binom{11-k}{3}$. The $k$ are distributed in $\binom{k+1}{1}$. Thus we have $\sum_{k=0}^4\binom{k+1}{1}\binom{11-k}{3}$.

b) Suppose distinguible balls: For $k$ fixed, $k=0,1,2,3,4$, let us distribute the $k$ into the first 2 boxes: choose the $k$ balls:$\binom{8}{k}$. Now, each of this $k$ has $2$ boxes for enter: then there are $2^k$. The other $8-k$ enter in the other 4 boxes in $4^{8-k}$. Then, we have $\sum_{k=0}^4\binom{8}{k}2^k4^{8-k}$.

• Is it supposed to be $4^{8-k}$? Or did Alex get it wrong? Jan 25 '16 at 0:59
• @Alex is wrong. Jan 25 '16 at 3:40
• Why? There are 4 boxes left.
– Alex
Jan 25 '16 at 9:20
• Oh that's right. I suppose 8 boxes instead 6. Jan 25 '16 at 9:22