$30$ red balls and $20$ black balls are being distributed to $5$ kids. Each kid gets at least one red ball. In how many ways can we distribute balls?

Question

$30$ red balls and $20$ black balls are being distributed to $5$ kids, so that each kid gets at least one red ball. In how many ways can we distribute balls?

Circle the correct answers:

a) $\binom{29}{4}$ $\binom{24}{20}$

b) $\binom{29}{5}$ $\binom{24}{5}$

c)$|Sur(N_{30},N_{5})|S(20,5)$ Note: $|Sur(N_{30},N_{5})|$ is the number of surjections, and $S(20,5)$ is a Stirling number of the second kind

d) None of $3$ previous answers are correct

My approach:

First I gave each of $5$ kids one red ball, which leaves me with $25$ red balls. Now I used the stars and bars method to distribute the balls I am left with.

Red balls: $x_1+x_2+x_3+x_4+x_5=25,x_i\geq 0, i=1,..,5$. This equation has $\binom{5+25-1}{25}=\binom{29}{25}=\binom{29}{4}$.

Black balls: $x_1+x_2+x_3+x_4+x_5=20,x_i\geq 0, i=1,..,5$. This equation has $\binom{5+20-1}{20}=\binom{24}{20}=\binom{24}{4}$.

So I would say a) is the correct answer.. am I right?

Answer 1

I don't know what the "stars and bars" method is, and I despise permutations, combinations, etc. and all of those combinatoric black boxes. So this is how I would do it:

Just place all of the balls on a straight line (going from left to right) in front of you. Choose 4 random spots between the balls. You have $\binom{29}{4}$ ways of doing so.

Give the first kid the balls before the first spot, the second kit the balls between the first and second spot, ... the last kid the balls after the last spot. Thus you have $\binom{29}{4}$ ways of distributing the red balls.

For the black balls, first go to the store and buy 5 new black balls. But then also add the condition of giving each kid at least one black ball. The same argument yields $\binom{24}{4}$ ways of distributing them. After the distribution is done, get one black ball back from each kid, so you have the same distribution as if you didn't get those extra 5 balls (and did not care to give at least one black ball to each kid).

So indeed the answer seems to be $\binom{29}{4}\binom{24}{4}$ ways of distributing the red and black balls.

Answer 2

Number of ways of distributing balls into boxes tells us the following:

Theorem 1: The number of ways in which $n$ indistinguishable balls can be distributed into $k$ distinguishable boxes is $\binom{n+k-1}{n}, $ which also equals $\binom{n+k-1}{k-1}$.

So... give one red ball to each kid because you have to, i.e. you have no choice here because there cannot be a kid without a red ball. Now you have 25 red balls and 20 black balls remaining.

But after this you have total freedom: any ball can go to any kid with no restrictions. But how many ways are there of doing this? Using Theorem 1, there are $\binom{25+5-1}{25} = \binom{29}{25}$ ways of distributing the red balls out, and $\binom{20+5-1}{20} = \binom{24}{20}$ ways to distribute the black balls out. Since "distributing red balls" and "distributing black balls" in this way are independent, there are no duplicate scenarios to worry about, so we may use the product rule of counting, and the answer is:

$\binom{29}{25} \times \binom{24}{20} $, which is answer (a).