How many ways there are to distribute $25$ distinct balls to $40$ bins such that:

  1. At least one bin will have more than one ball.

  2. One and only one bin (not predetermined) will hold exactly 10 balls. (In other words, only one bin will hold 10 balls and all others will have less or more than 10)

My attempt:

  1. with complement, the general case: each ball has 40 bins to go to $25^{40}$.

    At most one ball in every bin: $\binom {40} {25} 25!$

    Total: $25^{40}-\binom {40} {25} 25!$

  2. Choose one bin: $\binom {40} 1=40$.

    choose $10$ balls: $\binom {25} {10}$ and place them in the above bin: $40 \binom {25}{10}$

    Now there are $39$ bins and $15$ balls left, we want that for all, bins none has 10 balls, so the complement would be that there's one bin with 10 balls:

    The general case: $15^{39}$. Choose the other bin to hold 10 balls: $39$, choosing the balls that would go to that bin: $\binom {15} {10}$, $5$ balls left and $38$ bins: $5^{38}$

    Total: $(40 \binom {25}{10})(15^{39}-39\binom {15} {10}5^{38})$

  • $\begingroup$ $5$ balls left and $38$ bins: $5^{38}$ (instead of $15^{38}$). I suspect that is no more than a typo. I can't find other mistakes. $\endgroup$ – drhab Mar 12 '15 at 15:45
  • $\begingroup$ @drhab yup. BTW, throughout the answers, I wasn't sure if it's supposed to be $5^{38}$ or $38^5$. $\endgroup$ – shinzou Mar 12 '15 at 15:54
  • $\begingroup$ Now that you mention it: if every ball has $40$ to go to then there are $40^{25}$ possibilities. I overlooked that. Correction is needed on more places. $\endgroup$ – drhab Mar 12 '15 at 15:59
  • $\begingroup$ @drhab okay but why is it $40^{25}$? $\endgroup$ – shinzou Mar 12 '15 at 16:18
  • 1
    $\begingroup$ The first ball can be sent to $40$ bins. Then the second also to $40$ bins, giving $40\times 40$ possibilities for the first two balls. Et cetera. $\endgroup$ – drhab Mar 12 '15 at 16:23

Community wiki answer so the question can be marked as answered:

As noted in comments, your calculation is basically right; the only error is that wherever you count the number of ways to put $k$ distinct objects into $n$ bins you have $k^n$ instead of $n^k$.


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.