IOQM cheat sheet

Combinatorics

• Permutations and combinations: P(n,r) = n!/(n-r)! counts ordered selections; C(n,r) = n!/(r!(n-r)!) counts unordered selections; C(n,r)=C(n,n-r).

• Pigeonhole principle: if n items are placed into k boxes and n>k, at least one box contains more than one item; generalized, some box holds at least ceil(n/k) items.

• Inclusion-exclusion: |A union B| = |A|+|B|-|A intersect B|; for three sets add singles, subtract pairs, add the triple intersection.

• Stars and bars: the number of nonnegative integer solutions to x1+...+xk = n is C(n+k-1, k-1); for positive solutions it is C(n-1, k-1).

• Binomial theorem: (x+y)^n = sum over k of C(n,k) x^(n-k) y^k; setting x=y=1 gives sum C(n,k)=2^n, and the alternating sum is 0 for n>0.

• Handshake lemma: in any graph the sum of all vertex degrees is twice the number of edges, so the number of odd-degree vertices is even.

• Counting with symmetry: count arrangements as if distinct, then divide by the size of the symmetry group; for a round table of n people, fix one person to get (n-1)! arrangements.

• Recurrence relations: a sequence defined by a_n = a_{n-1}+a_{n-2} (Fibonacci) can be solved by characteristic roots; the number of binary strings with no two consecutive zeros satisfies a similar recurrence.

• Invariants and monovariants: identify a quantity unchanged (parity, sum mod k) or monotone to prove a configuration is impossible or a process terminates.