Combinatorics and probability
Pigeonhole, invariants and monovariants, generating functions with the roots-of-unity filter, and linearity of expectation with indicators.
The pigeonhole principle
If objects go into boxes, some box holds two. The difficulty is always choosing the boxes.
- Partial sums modulo . Among any integers there is a non-empty block of consecutive ones whose sum is a multiple of . Boxes: the residues of (with ), which are numbers for residues.
- From , any numbers contain two consecutive ones (boxes ), hence two coprime ones.
Invariants and monovariants
A process changes a state through some allowed moves. To show a state is not reachable, find a quantity no move changes: parity, a sum modulo , a colouring, a determinant. To show the process terminates, find a non-negative integer that strictly decreases with every move.
Generating functions
The sequence becomes the series . A counting problem becomes polynomial algebra.
- Partitions. Partitions of into distinct parts have generating function , and into odd parts . The two are equal, because , so the counts are equal (Euler).
- Roots-of-unity filter. With , and since is when and otherwise:
Linearity of expectation
always, with no independence needed. Write the quantity you want as a sum of indicators , so that .
- Fixed points of a random permutation: , and each term has probability . Hence for every .
- Probabilistic method: if , there is an outcome with and one with . If for an integer , then .
Pitfalls
- Variance is not linear. only for uncorrelated variables.
- Union: , with equality only for (almost surely) disjoint events.
- With generating functions work with formal power series, or state where they converge before substituting a value for .
Further reading
- Gelca & Andreescu, Putnam and Beyond, §1.3 (The Pigeonhole Principle)
- Gelca & Andreescu, Putnam and Beyond, §1.5 (Invariants and Semi-Invariants)
- Morris, Combinatorics (Greek transl. S. Nikolopoulos, Kallipos, CC BY-NC-SA 4.0), §7 (Γεννήτριες Συναρτήσεις)
- Morris, Combinatorics (Greek transl. S. Nikolopoulos, Kallipos, CC BY-NC-SA 4.0), §8 (Γεννήτριες Συναρτήσεις και Αναδρομή)
- Gelca & Andreescu, Putnam and Beyond, §6.2.2 (Generating Functions)
- Gelca & Andreescu, Putnam and Beyond, §6.3 (Probability)
Contest problems using these tools
No problems with these tools yet.