Combinatorial identities are equations that show different ways to count the same set of objects. They are important because they turn complicated counting problems into simpler ones using patterns and structure. Pascal’s Triangle gives a visual map of many of these identities, with each entry representing a combination value.
These patterns appear in probability, algebra, computer science, and many real-world selection problems.
The central idea is that C(n, k) counts the number of ways to choose k objects from n objects without caring about order. Pascal’s rule explains why each interior entry of Pascal’s Triangle is the sum of the two entries above it. Symmetry comes from the fact that choosing k objects to include is the same as choosing n minus k objects to leave out.
The hockey-stick identity shows that a diagonal sum in Pascal’s Triangle equals a single entry farther down the triangle.
Key Facts
- Combination formula: C(n, k) = n! / (k!(n - k)!)
- Pascal’s rule: C(n, k) = C(n - 1, k - 1) + C(n - 1, k)
- Symmetry identity: C(n, k) = C(n, n - k)
- Hockey-stick identity: C(r, r) + C(r + 1, r) + ... + C(n, r) = C(n + 1, r + 1)
- Boundary values: C(n, 0) = 1 and C(n, n) = 1
- Binomial theorem: (a + b)^n = sum from k = 0 to n of C(n, k)a^(n - k)b^k
Vocabulary
- Combination
- A combination is a selection of objects where order does not matter.
- Binomial coefficient
- A binomial coefficient C(n, k) is the number of ways to choose k items from n items.
- Pascal’s Triangle
- Pascal’s Triangle is a triangular array of numbers where each interior number is the sum of the two numbers above it.
- Pascal’s rule
- Pascal’s rule states that C(n, k) equals C(n - 1, k - 1) plus C(n - 1, k).
- Hockey-stick identity
- The hockey-stick identity says that certain diagonal sums in Pascal’s Triangle equal one entry just beyond the diagonal.
Common Mistakes to Avoid
- Using permutations when order does not matter. This is wrong because combinations count groups, while permutations count arrangements.
- Forgetting the boundary values C(n, 0) = 1 and C(n, n) = 1. These values are essential because there is exactly one way to choose nothing or everything.
- Applying Pascal’s rule with the wrong row or column. The correct relationship is C(n, k) = C(n - 1, k - 1) + C(n - 1, k), so both terms must come from the row above.
- Misreading the hockey-stick identity by stopping at the wrong endpoint. The diagonal sum from C(r, r) through C(n, r) equals C(n + 1, r + 1), not the last term on the diagonal.
Practice Questions
- 1 Compute C(8, 3) using the combination formula, then verify it using values from Pascal’s Triangle.
- 2 Use the hockey-stick identity to find C(2, 2) + C(3, 2) + C(4, 2) + C(5, 2) + C(6, 2).
- 3 Explain why C(10, 3) = C(10, 7) using a counting argument about choosing students for a committee.