AOCP/Multinomial Coefficients

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}} $

Related Pages

LatticePaths

AOCP/Multisets

AOCP/Binomial Coefficients