Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I will elaborate this with an analogy, 15 toys are to be distributed amongst 3 children , such that any child can get any number of toys, so we have to find the number of ways in which we can do so if,

  1. toys are distinct

  2. toys are identical

We can apply multinomial in only the latter case , why so?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

The answers in the two cases are clearly different, so a formula for one of the problems cannot possibly work, without change, to solve the other. A reasonable way to approach the question is to solve each of the problems, in the concrete case you mentioned. We use approaches that readily generalize.

Different toys: Call the toys $1$, $2$, and so on up to $15$ (numbers make great toys). There are $3$ ways to decide who gets toy $1$. For each of these ways, there are $3$ ways to decide who gets toy $2$, for a total so far of $3\times 3$. For each way of making these two decisions, there are $3$ ways to decide who gets toy $3$, and so on, for a total of $3^{15}$ ways.

We could approach the problem through multinomial coefficients. The number of ways to choose $t_A$ toys to give to kid $A$, and $t_B$ toys to give to kid $B$, and $t_C$ to give to kid $C$, where $t_A+t_B+t_B=15$, is the multinomial coefficient $\binom{15}{t_A,t_B,t_C}$. To get the total number of ways, sum over all $(t_A,t_B,t_C)$. We can use the multinomial theorem to conclude that the sum is $3^{15}$. But we already had a simpler argument for $3^{15}$.

Identical toys: A standard approach is to count the number of ways to distribute $18$ toys among the $3$ kids, at least one toy to each kid. Then we make each kid give back a toy. Line up the $18$ toys. They determine $17$ inter-toy gaps. Put a marker into $2$ of these gaps. Give kid $A$ all the toys up to the first marker, kid $B$ the toys from the first marker to the second, and kid $C$ the rest. There are $\binom{17}{2}$ ways to choose where the markers will go, and hence $\binom{17}{2}$ ways to distribute $15$ toys among $3$ kids, where some kid(s) may get nothing.

The argument perhaps is not *multi*nomial, since only the special binomial case of the multinomial is being used. But it certainly belongs to the same family of ideas. In both cases, "nomial" ideas can be used.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.