Volume 1

Chapter 1: Basic Concepts: Multinomial Coefficients

Definition

We can generalize this approach and define the multinomial coefficient.

More compactly, let n denote the sum of the ks:

$\binom{n}{k_1 , k_2 , \dots , k_m } = \dfrac{n!}{k_1 ! k_2 ! \dots k_m !} \qquad k_i \in \mathbb{Z}, k_i \geq 0$

or,

$\binom{k_1 + k_2 + \dots + k_m}{k_1 , k_2 , \dots , k_m } = \dfrac{(k_1 + k_2 + \dots + k_m)!}{k_1 ! k_2 ! \dots k_m !} \qquad k_i \in \mathbb{Z}, k_i \geq 0$

Generalization of Binomial Theorem

The binomial theorem gives a formula that allows powers of binomial sums to be expanded in terms of binomial coefficients:

$(x+y)^n = \sum_{0 \leq k \leq n} \binom{n}{k} x^k y^{(n-k)}$

There is an analogous expansion for powers of multinomial sums (sums of multiple terms), in terms of these multinomial coefficients:

$(x_1 + x_2 + \dots + x_m)^n = \sum_{k_1 + k_2 + \dots + k_m = n} \binom{n}{k_1, k_2, \dots, k_m} x_1^{k_1} x_2^{k_2} \dots x_m^{k_m}$

Any multinomial coefficient can also be expressed in terms of binomial coefficients:

$\binom{k_1 + k_2 + \dots + k_m}{k_1, k_2, \dots k_m} = \binom{k_1 + k_2}{k_1} \binom{k_1 + k_2 + k_3}{k_1 + k_2} \dots \binom{k_1 + k_2 + \dots + k_m}{k_1 + \dots + k_{m-1}}$