Combinatorial Identities Reference Cheat Sheet

Key Facts

• The factorial rule is $n! = n(n-1)(n-2)\cdots 2\cdot 1$ for positive integers, with $0! = 1$.
• The number of permutations of $r$ objects chosen from $n$ distinct objects is $P(n,r)=\frac{n!}{(n-r)!}$.
• The number of combinations of $r$ objects chosen from $n$ distinct objects is $\binom{n}{r}=\frac{n!}{r!(n-r)!}$.
• The symmetry identity is $\binom{n}{r}=\binom{n}{n-r}$ because choosing $r$ items is equivalent to leaving out $n-r$ items.
• Pascal’s identity is $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$ for $1\le r\le n-1$.
• The hockey-stick identity is $\sum_{k=r}^{n}\binom{k}{r}=\binom{n+1}{r+1}$.
• Vandermonde’s identity is $\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}$.
• The binomial theorem is $(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k$.

Vocabulary

Factorial

A factorial $n!$ is the product of all positive integers from $1$ through $n$, with $0! = 1$.

Permutation

A permutation is an ordered arrangement, often counted by $P(n,r)=\frac{n!}{(n-r)!}$.

Combination

A combination is an unordered selection, often counted by $\binom{n}{r}=\frac{n!}{r!(n-r)!}$.

Binomial Coefficient

A binomial coefficient $\binom{n}{r}$ counts the number of ways to choose $r$ objects from $n$ objects.

Pascal’s Identity

Pascal’s identity states that $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$.

Binomial Theorem

The binomial theorem expands powers using $(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k$.