2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$$

$\endgroup$
0
$\begingroup$

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}$.

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

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.