Combinations

Math for CS · Axiom Academy

Choosing subsets -- when order doesn't matter A combination is an unordered selection. We want to choose k items from n without caring about the arrangement. Choosing which k items to include is the same as choosing which n-k items to exclude . Every subset of size k corresponds to a unique complement of size n-k . Contains x: Choose the remaining k-1 items from the other n-1 elements: k-1 ways Doesn't contain x: Choose all k items from the other n-1 elements: k ways This identity is what makes Pascal's triangle work -- each entry is the sum of the two entries above it. Sum of all: _ k=0 ^ n k = 2^n (total number of subsets) Alternating sum: _ k=0 ^ n (-1)^k k = 0 Vandermonde: r = _ k=0 ^ r k r-k

This is the written version of the interactive lesson above. See the full Math for CS course.