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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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