Combinatorial Probability - Main Theorem

The multinomial theorem generalizes the binomial theorem to expansions involving more than two terms. It provides both a powerful algebraic tool and a counting formula for distributing objects into categories.

Multinomial Theorem

Theorem

For any real numbers $x_1, x_2, \ldots, x_r$ and non-negative integer $n$ : $(x_1 + x_2 + \cdots + x_r)^n = \sum_{k_1 + k_2 + \cdots + k_r = n} \binom{n}{k_1, k_2, \ldots, k_r} x_1^{k_1} x_2^{k_2} \cdots x_r^{k_r}$

where the sum is over all non-negative integer solutions to $k_1 + k_2 + \cdots + k_r = n$ , and: $\binom{n}{k_1, k_2, \ldots, k_r} = \frac{n!}{k_1! k_2! \cdots k_r!}$

Proof Outline: When expanding $(x_1 + x_2 + \cdots + x_r)^n$ , we multiply $n$ factors together. Each term in the expansion results from choosing one $x_i$ from each of the $n$ factors. A term $x_1^{k_1} x_2^{k_2} \cdots x_r^{k_r}$ arises when we choose $x_1$ from $k_1$ factors, $x_2$ from $k_2$ factors, etc. The coefficient counts the number of ways to partition the $n$ positions into groups of sizes $k_1, k_2, \ldots, k_r$ . □

Setting all $x_i = 1$ yields: $r^n = \sum_{k_1 + \cdots + k_r = n} \binom{n}{k_1, \ldots, k_r}$

This counts the number of ways to place $n$ distinguishable balls into $r$ distinguishable boxes.

Example

Expand $(x + y + z)^3$ : $(x+y+z)^3 = \sum_{i+j+k=3} \binom{3}{i,j,k} x^i y^j z^k$

Computing each term:

$(3,0,0)$ permutations: $\binom{3}{3,0,0} x^3 = x^3$ , $\binom{3}{0,3,0} y^3 = y^3$ , $\binom{3}{0,0,3} z^3 = z^3$
$(2,1,0)$ permutations: $\binom{3}{2,1,0} x^2y = 3x^2y$ , and similarly $3x^2z, 3y^2x, 3y^2z, 3z^2x, 3z^2y$
$(1,1,1)$ : $\binom{3}{1,1,1} xyz = 6xyz$

Result: $(x+y+z)^3 = x^3 + y^3 + z^3 + 3x^2y + 3x^2z + 3y^2x + 3y^2z + 3z^2x + 3z^2y + 6xyz$

Stirling's Approximation

For large factorials, exact computation becomes impractical. Stirling's formula provides an excellent approximation.

Theorem

For large $n$ : $n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$

More precisely: $\lim_{n \to \infty} \frac{n!}{\sqrt{2\pi n} (n/e)^n} = 1$

This allows us to approximate binomial coefficients for large $n$ : $\binom{2n}{n} \approx \frac{4^n}{\sqrt{\pi n}}$

Example

Compare $10!$ with Stirling's approximation:

Exact: $10! = 3,628,800$
Stirling: $\sqrt{20\pi} (10/e)^{10} \approx 3,598,696$
Relative error: less than 1%

Remark

The multinomial theorem and Stirling's approximation are indispensable tools in probability theory. The multinomial theorem handles discrete distributions over multiple categories, while Stirling's formula enables asymptotic analysis of probabilities involving large numbers of trials.