Multinomial Coefficients

Let \(X\) be a set of \(n\) elements. Suppose that we have two colors of paint, say red and blue, and we are going to choose a subset of \(k\) elements to be painted red with the rest painted blue. Then the number of different ways this can be done is just the binomial coefficient \(\binom{n}{k}\). Now suppose that we have three different colors, say red, blue, and green. We will choose \(k_1\) to be colored red, \(k_2\) to be colored blue, and the remaining \(k_3 = n - (k_1+k_2)\) are to be colored green. We may compute the number of ways to do this by first choosing \(k_1\) of the \(n\) elements to paint red, then from the remaining \(n-k_1\) elements choosing \(k_2\) to paint blue, and then painting the remaining \(k_3\) elements green. It is easy to see that the number of ways to do this is \[\begin{aligned}\end{aligned}\] Numbers of this form are called multinomial coefficients; they are an obvious generalization of the binomial coefficients. The general notation is: \[\begin{aligned}\end{aligned}\] \(\binom{n}{k_1,k_2,k_3,\dots,k_r}\) multinomial coefficient

For example, \[\begin{aligned}\end{aligned}\]

Note that there is some overkill in this notation, since the value of \(k_r\) is determined by \(n\) and the values for \(k_1\), \(k_2,\dots,k_{r-1}\). For example, with the ordinary binomial coefficients, we just write \(\binom{8}{3}\) and not \(\binom{8}{3,5}\).

Just as with binomial coefficients and the Binomial Theorem, the multinomial coefficients arise in the expansion of powers of a multinomial:

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.