Counting Principles - Key Properties

The binomial coefficients and factorials satisfy numerous algebraic identities that make counting problems tractable. Understanding these properties enables us to manipulate counting expressions and solve complex combinatorial problems efficiently.

DefinitionPascal's Identity

For integers $n$ and $r$ with $0 \leq r \leq n$ , we have $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

This identity has a combinatorial interpretation: to choose $r$ objects from $n$ objects, we can either include a particular object (and choose $r-1$ from the remaining $n-1$ ) or exclude it (and choose $r$ from the remaining $n-1$ ).

Pascal's identity is the foundation for Pascal's triangle, where each entry is the sum of the two entries above it. This provides an efficient method for computing binomial coefficients recursively.

DefinitionBinomial Theorem

For any real numbers $x$ and $y$ and any non-negative integer $n$ , $(x + y)^n = \sum_{r=0}^{n} \binom{n}{r} x^{n-r} y^r = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \cdots + \binom{n}{n}y^n$

The binomial theorem is one of the most important results in combinatorics, connecting algebra with counting. Setting $x = y = 1$ gives $\sum_{r=0}^{n} \binom{n}{r} = 2^n$ , which counts all subsets of an $n$ -element set.

ExampleExpanding with the Binomial Theorem

Let's expand $(x + 2)^4$ using the binomial theorem: $(x + 2)^4 = \sum_{r=0}^{4} \binom{4}{r} x^{4-r} 2^r$

Computing each term: $= \binom{4}{0}x^4 + \binom{4}{1}x^3(2) + \binom{4}{2}x^2(4) + \binom{4}{3}x(8) + \binom{4}{4}(16)$ $= x^4 + 8x^3 + 24x^2 + 32x + 16$

DefinitionSymmetry Property

For any integers $n$ and $r$ with $0 \leq r \leq n$ , $\binom{n}{r} = \binom{n}{n-r}$

This symmetry reflects the fact that choosing $r$ objects to include is equivalent to choosing $n-r$ objects to exclude.

DefinitionVandermonde's Identity

For non-negative integers $m$ , $n$ , and $r$ , $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$

This identity counts the number of ways to choose $r$ objects from two disjoint sets of sizes $m$ and $n$ by considering all possible ways to distribute the choice between the two sets.

Remark

Another important property is the hockey stick identity: $\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$ . This can be proven combinatorially by considering paths in Pascal's triangle or algebraically through telescoping. These identities are not merely algebraic curiosities; they often provide elegant solutions to counting problems that would otherwise require lengthy case analysis.

Mastering these properties allows for efficient computation and provides deep insights into the structure of combinatorial problems.