AOCP/Multinomial Coefficients

Volume 1

Chapter 1: Basic Concepts: Multinomial Coefficients

Definition

We can generalize this approach and define the multinomial coefficient:

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

This can also generalize the binomial theorem to a higher power of multiple sums:

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