Combinatorics Reference

Discrete Math · Axiom Academy

FORMULA SHEET Combinatorics Reference Complete reference for counting principles, permutations, combinations, and advanced techniques FUNDAMENTAL COUNTING PRINCIPLES If task A can be done in m ways OR task B in n ways (mutually exclusive), total is m + n ways If task A can be done in m ways AND task B in n ways (independent), total is m × n ways Number of ways to arrange n distinct objects Number of ways to arrange r objects from n distinct objects Alternative form: n(n-1)(n-2)···(n-r+1) COMBINATIONS (ORDER DOESN'T MATTER) Number of ways to select r objects from n distinct objects Alternative form using factorials Symmetry property: choosing r equals not choosing n-r n 1 of type 1, n 2 of type 2, ..., n k of type k Arrangements of n objects in a circle (rotations are identical) Circular arrangements with reflections identical (necklaces, bracelets) Select r objects from n types with replacement allowed (multisets) Stars and bars: distributing r identical objects into n distinct bins Expansion of (x + y) n where coefficients are binomial coefficients Each entry is the sum of the two entries above it. Row n contains the coefficients of (x + y) n . Stirling numbers of the first kind: ways to arrange n objects into k cycles Stirling numbers of the second kind: ways to partition n objects into k non-empty subsets Recurrence relation for Stirling numbers of the second kind For two sets: count union by adding sizes, subtracting overlap

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