Combinatorial Probability - Key Properties

Binomial coefficients possess remarkable algebraic properties that make combinatorial calculations tractable. These properties arise from both algebraic manipulation and combinatorial interpretations.

Pascal's Triangle and Recurrence

Theorem

For $1 \leq r \leq n$ : $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

Combinatorial Proof: To choose $r$ objects from $n$ , either the first object is included (leaving $r-1$ to choose from remaining $n-1$ ), or it is not included (leaving $r$ to choose from remaining $n-1$ ). □

This identity generates Pascal's triangle, where each entry is the sum of the two entries above it:

& & & 1 & & & \\ & & 1 & & 1 & & \\ & 1 & & 2 & & 1 & \\ 1 & & 3 & & 3 & & 1 \end{array}$$ ## Binomial Theorem <Theorem name="Binomial Theorem"> For any real numbers $x, y$ and non-negative integer $n$: $$(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}$$ </Theorem> Setting $x = y = 1$ yields $\sum_{k=0}^n \binom{n}{k} = 2^n$, the total number of subsets of an $n$-element set. Setting $x = 1, y = -1$ yields $\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$. <Example> Expand $(x+y)^4$: $$(x+y)^4 = \binom{4}{0}y^4 + \binom{4}{1}xy^3 + \binom{4}{2}x^2y^2 + \binom{4}{3}x^3y + \binom{4}{4}x^4$$ $$= y^4 + 4xy^3 + 6x^2y^2 + 4x^3y + x^4$$ </Example> ## Multinomial Coefficients When dividing $n$ objects into groups of sizes $k_1, k_2, \ldots, k_r$ where $k_1 + k_2 + \cdots + k_r = n$: <Definition> The **multinomial coefficient** is: $$\binom{n}{k_1, k_2, \ldots, k_r} = \frac{n!}{k_1! k_2! \cdots k_r!}$$ </Definition> This counts the number of ways to partition $n$ distinct objects into $r$ labeled groups. <Example> How many ways can we arrange the letters in "MISSISSIPPI"? $$\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{11!}{4! \cdot 4! \cdot 2!} = 34,650$$ Here we have 11 letters: 1 M, 4 I's, 4 S's, and 2 P's. </Example> ## Vandermonde's Identity <Theorem name="Vandermonde's Identity"> For non-negative integers $m, n, r$: $$\binom{m+n}{r} = \sum_{k=0}^r \binom{m}{k} \binom{n}{r-k}$$ </Theorem> **Combinatorial Proof**: The left side counts ways to choose $r$ objects from $m+n$ objects. Partition these objects into two groups of sizes $m$ and $n$. For each $k$, choose $k$ from the first group and $r-k$ from the second. □ <Remark> Many binomial coefficient identities have both algebraic proofs (manipulation of formulas) and combinatorial proofs (counting the same quantity in two different ways). Combinatorial proofs often provide deeper insight into why an identity holds. </Remark>