Multinomial Coefficients

Definition

The multinomial coefficient is defined as

$$\binom{n}{n_1,n_2,\dots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}$$

where:

• $n$ is a nonnegative integer,
• $n_1,n_2,\dots,n_k$ are nonnegative integers,
• and

$$n_1+n_2+\cdots+n_k=n.$$

This coefficient counts the number of ways to divide $n$ distinct objects into $k$ ordered groups of sizes $n_1,n_2,\dots,n_k$, or equivalently, the number of ways to arrange $n$ objects where $n_1$ are of one kind, $n_2$ of another kind, and so on.

A very important special case is the binomial coefficient:

$$\binom{n}{r,n-r}=\frac{n!}{r!(n-r)!}=\binom{n}{r}.$$

So, binomial coefficients are simply a two-part case of multinomial coefficients.

---

Main Content

1. Counting Arrangements with Repeated Groups

• Multinomial coefficients count the number of ways to arrange objects when there are repeated categories or group sizes.
• If $n$ distinct objects are split into groups of sizes $n_1,n_2,\dots,n_k$, the number of such arrangements is $$\frac{n!}{n_1!n_2!\cdots n_k!}.$$

For example, consider the word MISSISSIPPI. It has 11 letters:

• $M=1$
• $I=4$
• $S=4$
• $P=2$

So the number of distinct arrangements is

$$\frac{11!}{1!4!4!2!}.$$

This works because:

• $11!$ counts all arrangements if all letters were different,
• but swapping identical letters does not create a new arrangement,
• so we divide by the factorial of each repeated count.

A smaller example: arrange the letters in BALLOON.

• Total letters: $7$
• Repetitions: $L=2, O=2$

Number of distinct arrangements:

$$\frac{7!}{2!2!}.$$

This is a common and practical use of multinomial coefficients in combinatorial counting.

2. Expansion of a Multinomial Expression

• Multinomial coefficients appear as coefficients in the expansion of $(x_1+x_2+\cdots+x_k)^n$.
• The multinomial theorem states: $$(x_1+x_2+\cdots+x_k)^n = \sum \frac{n!}{n_1!n_2!\cdots n_k!} x_1^{n_1}x_2^{n_2}\cdots x_k^{n_k},$$ where the sum is over all nonnegative integer tuples $(n_1,n_2,\dots,n_k)$ such that $n_1+\cdots+n_k=n$.

For example, in

$$(a+b+c)^3,$$

the coefficient of $a^1b^1c^1$ is

$$\frac{3!}{1!1!1!}=6.$$

So the term $abc$ appears with coefficient 6 in the full expansion.

A useful smaller example is:

$$(x+y)^4.$$

Here, multinomial coefficients reduce to binomial coefficients:

$$(x+y)^4=\sum_{r=0}^{4}\binom{4}{r}x^r y^{4-r}.$$

Thus multinomial coefficients generalize the pattern of coefficients in polynomial expansions to more than two variables.

3. Connection with Combinatorial Structures

• Multinomial coefficients can be interpreted through step-by-step choices, making them useful in counting processes and discrete structures.
• They are also related to partitions of sets into labeled parts and to counting lattice paths with multiple step types.

For example, suppose we want to count the number of ways to choose:

• 2 students for Team A,
• 3 students for Team B,
• 1 student for Team C,

from a group of 6 distinct students.

The number of ways is

$$\binom{6}{2,3,1}=\frac{6!}{2!3!1!}=60.$$

This means there are 60 possible assignments of students to these three labeled teams.

A visual counting idea:

6 distinct students
   |
   +--> choose 2 for A
   |
   +--> from remaining 4 choose 3 for B
   |
   +--> remaining 1 goes to C

This can also be computed as:

$$\binom{6}{2}\binom{4}{3}\binom{1}{1}=15 \times 4 \times 1 = 60.$$

This shows how multinomial coefficients naturally arise from successive choices.

---

Working / Process

1. Identify the total count and the category sizes

• Determine the total number $n$ of items.
• Break them into group sizes $n_1,n_2,\dots,n_k$ such that $n_1+\cdots+n_k=n$.

2. Apply the multinomial formula

• Use $$\binom{n}{n_1,n_2,\dots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}.$$

• If the problem is about a polynomial expansion, match the exponents of the variables to the group sizes.

3. Interpret the result in the context of the problem

• For arrangements, the value gives the number of distinct permutations.
• For expansions, it gives the coefficient of the corresponding term.
• For distribution problems, it gives the number of ways to assign objects to labeled groups.

For example, to find the coefficient of $x^2y^1z^3$ in $(x+y+z)^6$:

• Verify $2+1+3=6$,
• Compute $$\frac{6!}{2!1!3!}=60.$$

So the coefficient of $x^2y z^3$ is 60.

---

Advantages / Applications

• Useful in counting distinct permutations of objects with repeated types, such as letters in words or grouped items in arrangements.
• Essential in expanding powers of sums with three or more variables through the multinomial theorem.
• Widely used in probability, statistics, and discrete mathematics for counting outcomes, distributions, and structured selections.

It is also useful in:

• partitioning a set into labeled subsets,
• analyzing outcomes in multinomial probability distributions,
• counting paths and states in combinatorial models,
• solving problems in algebraic expansions and coefficient extraction.

---

Summary

• Multinomial coefficients generalize binomial coefficients to more than two groups.
• They count arrangements, distributions, and coefficients in expansions of sums.
• They are computed using factorials based on the sizes of all groups.

Important terms to remember: multinomial coefficient, multinomial theorem, factorial, repeated objects, coefficient extraction.