Combination Properties

Combinatorics · Axiom Academy

Exploring fundamental properties and identities of combinations through visual proofs One of the most elegant properties of combinations is symmetry: choosing r items from n is equivalent to choosing which n-r items to leave out. Combinatorial Proof: When we select r objects from n objects, we're simultaneously deciding which n-r objects to exclude. Each selection of r objects corresponds to exactly one selection of n-r objects to leave behind. 2. Sum of a Row in Pascal's Triangle The sum of all combinations from n objects equals the total number of subsets of n elements, which is 2^n. Combinatorial Proof: Each element can either be in or out of a subset. For n elements, there are 2 choices per element, giving 2^n total subsets. These subsets are counted by C(n,0) + C(n,1) + ... + C(n,n), where C(n,k) counts subsets of size k. A diagonal sum in Pascal's triangle equals an entry one row down and one column to the right. This pattern resembles a hockey stick when highlighted in the triangle. Combinatorial Proof: Count the ways to choose r+1 objects from n+1 objects where the "largest" chosen object is in position k+1. The largest could be r+1 (giving C(r,r) ways), or r+2 (giving C(r+1,r) ways), and so on up to n+1 (giving C(n,r) ways). Summing these disjoint cases gives C(n+1,r+1).

This is the written version of the interactive lesson above. See the full Combinatorics course.