How many ways are there to place 7 balls in 14 boxes. Balls are numbered from 1 to 7. One box can contain only one ball. And out of 14 boxes atleast 6 boxes must contain first 6 balls. 7th ball is optional either you may put it in boxes or not.

Please explain how to solve these types of question and what approach should I use. Also if the number of boxes was 1 or 2 or 100 what approach should I use?

  • 2
    $\begingroup$ suggest you look at factorials and nCr. As for ball 7 being optional, simply split the problem into 2 sub-problems (one with 7 + one with 6) $\endgroup$
    – Dave
    Sep 6 '14 at 17:45
  • $\begingroup$ ''out of $14$ boxes atleast $6$ boxes must contain first $6$ balls''..Why do you say 'atleast'? If they can only contain one ball then that seems to be redundant. Are the 'first $6$' those with the numbers $1$,...,$6$? $\endgroup$
    – drhab
    Sep 6 '14 at 17:54
  • $\begingroup$ @drhab Yes balls numbered 1 to 6 are mandatory to be placed. Ball numbered 7 is not mandatory to be placed in boxes present. $\endgroup$ Sep 6 '14 at 17:58
  • $\begingroup$ the answer is C(N/2,6) $\endgroup$ Sep 10 '14 at 14:56

Assuming the order in which the balls are placed in their respective boxes doesn't matter, you can just use the combinations formula $C_{(n,k)}$,

$$C_{(n,k)}={n! \over k!(n-k)!}$$

In your case $k$ would be the number of balls being placed in the boxes, and $n$ would be the number of boxes.

The restriction that only one ball can be placed in each box simplifies the problem considerably. As for the option of keeping the $k^{th}$ ball and not placing it in any box, the formula could be modified as follows:

$${(n+1)! \over k!((n+1)-k)!}$$

$n$ becomes $n+1$ because the effect of the option of withholding the $k^{th}$ ball is essentially that of adding another box.

This will work for any number of boxes $n \geq 1$ and any number of balls $0 \leq k \leq n+1$.

  • $\begingroup$ I'm not sure that this modification for the option of keeping the kth ball will work, since only that ball (and none of the first k-1 balls) could be placed in the added box. $\endgroup$
    – user84413
    Sep 6 '14 at 21:08
  • $\begingroup$ Seems to work. The option of keeping the ball is the same as all the boxes in that once it is selected it cannot be selected again, and so any combination where this $(n+1)^{th}$ 'box' is selected will be possible, it just needs to be assumed to be the last, or $k^{th}$, selection. $\endgroup$
    – Zach W
    Sep 6 '14 at 21:29
  • $\begingroup$ If there were 4 boxes and 3 balls, say, with the keep option on the 3rd ball, I think there would be $\binom{4}{2}=6$ ways to place the 1st two balls, and then there would be 3 options for the last ball (one of the two remaining boxes, or keep it). This would give 18 choices instead of $\binom{5}{3}=10$. $\endgroup$
    – user84413
    Sep 6 '14 at 21:39
  • $\begingroup$ The problem with simply multiplying $C_{n,k-1}$ by $(n+1)-(k-1)$ is that it doesn't account for redundant permutations. If you manually go through the different combinations for your case $n=4$ and $k=3$, $10$ turns out to be correct. I apologize for not having a more succinct explanation. $\endgroup$
    – Zach W
    Sep 6 '14 at 23:28
  • $\begingroup$ I'm sorry, I realize now that I wasn't taking into account that the balls are numbered; so permutations should be used instead of combinations. $\endgroup$
    – user84413
    Sep 7 '14 at 0:10

We can select the boxes for the first 6 balls in $\binom{14}{6}$ ways,

and then there are $6!$ ways to place the balls in these 6 boxes.

Then for the 7th ball there are 9 options, either keep it or place it in any of the remaining 8 boxes; so

there are $\displaystyle\binom{14}{6}\cdot6!\cdot9=9\left(\frac{14!}{8!}\right)$ ways to do this.

More generally, if we have $k$ numbered balls to be placed in $n$ boxes with the same restrictions,

there are $\binom{n}{k-1}$ ways to choose the places for the first $k-1$ balls,

$(k-1)!$ ways to place the balls in these boxes, and then

$(n-(k-1))+1=n-k+2$ options for the last ball

(since it can either be kept or placed in any of the remaining $n-(k-1)$ boxes);

so there are $\displaystyle\binom{n}{k-1}\cdot(k-1)!\cdot(n-k+2)$ possibilities.


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.