1
$\begingroup$

I have $90$ identical balls to distribute among $64$ distinguishable bins. Each must get at least 1 ball, after that the distribution over the remaining $26$ does not matter. I know I first have to distribute $64$ balls, one to each bin $k^n$ so $90^{64}$ even though that already seems wrong. After I do that, I have to distribute $26$ balls to $64$ bins, so would that just be $\binom{64}{26}$? Fairly lost on all this, all of the formulas have jumbled together, thanks in advance for the help guys.

$\endgroup$
  • $\begingroup$ Please see the Wikipedia article on Stars and Bars. You will also find discussions on MSE. The answer is $\binom{90-1}{64-1}$. $\endgroup$ – André Nicolas Mar 31 '14 at 23:52
3
$\begingroup$

Please see the Wikipedia article on Stars and Bars. It is quite accessible.

I like to think of the problem as asking the following. How many ways are there to distribute $90$ candies among $64$ distinguishable kids, so that every kid gets at least one candy. To make typing easier, we use $12$ candies and $5$ kids, but the idea for $90$ and $64$ is the same. Line up the candies as follows, with a little space between candies. $$\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad$$

There are, in our small example, $11$ intercandy gaps. Choose $4$ of these $11$ gaps to put a separator (bar) into. One example would be $$\ast\qquad\ast\quad|\quad\ast\qquad\ast\quad|\quad\ast\quad|\quad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\quad|\quad\ast\qquad\ast\qquad$$

Now line up the kids in order of student number. Give the first kid all the candies up to the first bar, the next kid the candies between the first bar and the second, the third kid all the candies between the second bar and the third, and so on. So with our placement of bars, the kids got, respectively, $2$, $2$, $1$, $5$, and $2$ candies.

Every choice of $4$ gaps to put bars into determines a candy distribution, and if we know the candy distribution we know where to place the bars.

Thus, in our example, there are $\binom{11}{4}$ ways to distribute the candies.

In your problem the same argument yields that there are $\binom{89}{64}$ ways to distribute the balls.

$\endgroup$

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.