Generating functions · Definition

Multinomial coefficient

enumerative combinatoricsgenerating functions

Before you start you need to know

It appears when expanding \((x_1+\cdots+x_m)^n\) and when counting anagrams with repeated letters. The binomial coefficient, its two-group case, is the natural prerequisite.

Definition

Multinomial coefficient \(\binom{n}{k_1,\dots,k_m}\): the number of ways to split \(n\) distinct objects into \(m\) labeled groups of sizes \(k_1,\dots,k_m\), where \(k_1+\cdots+k_m=n\).

\[\binom{n}{k_1,\dots,k_m}=\frac{n!}{k_1!\,k_2!\cdots k_m!}\]

When \(m=2\) it reduces to \(\binom{n}{k}\), and it factors as \(\binom{n}{k_1,\dots,k_m}=\binom{n}{k_1}\binom{n-k_1}{k_2,\dots,k_m}\). The multinomial theorem states that \((x_1+\cdots+x_m)^n=\sum \binom{n}{k_1,\dots,k_m}x_1^{k_1}\cdots x_m^{k_m}\), summing over all \(m\)-tuples of nonnegative integers with sum \(n\).

For the word PEPPER, if all letters were distinct there would be \(6!\) orderings. Since P appears 3 times and E 2 times, the total is \(\frac{6!}{3!\,2!\,1!}=\frac{720}{12}=60\).

The typical mistake is forgetting that the groups are labeled or that the sizes must sum to exactly \(n\). If the groups are unlabeled, one must also divide by the factorial of the number of groups with equal size.

Think about it

What happens to the coefficient if we swap \(k_1\) and \(k_2\)?

Nothing: it is symmetric in the \(k_i\), since the denominator \(k_1!\,k_2!\cdots k_m!\) is unchanged by reordering them.

Exercises 10

  1. Compute \(\binom{3}{1,1,1}\).
  2. Compute \(\binom{4}{2,2}\).
  3. Compute \(\binom{5}{2,3}\).
  4. Compute \(\binom{6}{2,2,2}\).
  5. How many distinct anagrams does the word AAB have?
  6. Find the coefficient of \(x^2yz\) in \((x+y+z)^4\).
  7. Seven distinct people are split into labeled groups A, B and C of sizes 3, 2 and 2. How many ways are there?
  8. How many distinct anagrams does the word PEPPER have?
  9. Nine distinct books are placed on 3 identical shelves, 3 books per shelf. How many distinct distributions are there?
  10. Let \(a\) be a fixed object. How many ways are there to distribute 6 distinct objects, including \(a\), into three labeled boxes of 2 objects each, with \(a\) in box 1?

References

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.