Interpretation of multinomial coefficients in terms of choosing elements from a set

binomial-coefficientscombinatoricsmultinomial-coefficients

The binomial coefficients represent the coefficients on the terms in the expansion of $(x+y)^n$, but they can also be interpreted as choosing a subset of items from a set while disregarding the order of choice and disallowing repeated choices.

Multinomial coefficients are the coefficients in the expansion of $(x1+x2+…+x_m)^n$, but I have not yet been able to think of a "choose" related interpretation of multinomial coefficient in the same vein as the interpretation of binomial coefficients.

The only interpretation I know of is that of counting the number of strings with repeated letters, e.g. the number of rearrangements of MISSISSIPPI is the multinomial $\frac{11!}{1!4!4!2!}$. I suppose binomials can also be thought of as counting the number of strings with repeated letters, made out of only two letters, e.g. $6 \choose 4$ is the number of rearrangements of AAAABB.

But is there an interesting interpretation of multinomials in terms of forming subsets or otherwise "choosing" items in some way? I know it's not choosing elements disregarding order but allowing repeated choices; that problem is solved by multichoose aka stars and bars. So what could the interpretation of multinomials be?

Best Answer

You can write a multinomial coefficient as a product of binomial coefficients. If $n,m$ are nonengative integers, and $k_1,\dots,k_m$ are nonnegative integers summing to $n$, then $$ \binom{n}{k_1,k_2,\dots,k_m}=\binom{n}{k_1} \binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3}\cdots \binom {n-k_1-\dots-k_{m-2}}{k_{m-1}}. $$ This leads to the following combinatorial interpretation; the multinomial coefficient is the number of ways to choose $k_1$ objects from a pool of $n$, then to choose $k_2$ objects from the remaining pool of $n-k_1$ objects, then choose $k_3$ objects from the remaining pool of $n-k_1-k_2$ objects, and so on. So, you are not choosing a single subset, but rather $m-1$ disjoint subsets.

Equivalently, this is the number of ways to take $n$ distinct objects, and place them each into one of $m$ distinct boxes, so that box number $i$ gets exactly $k_i$ objects for each $i\in \{1,\dots,m\}$.