uniolympiads Ελληνικά

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 n+1n + 1 objects go into nn boxes, some box holds two. The difficulty is always choosing the boxes.

  • Partial sums modulo nn. Among any nn integers a1,…,ana_1, \dots, a_n there is a non-empty block of consecutive ones whose sum is a multiple of nn. Boxes: the residues of S0=0,S1,…,SnS_0 = 0, S_1, \dots, S_n (with Sk=a1+⋯+akS_k = a_1 + \dots + a_k), which are n+1n + 1 numbers for nn residues.
  • From {1,…,2n}\{1, \dots, 2n\}, any n+1n + 1 numbers contain two consecutive ones (boxes {2k−1,2k}\{2k - 1, 2k\}), 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 kk, a colouring, a determinant. To show the process terminates, find a non-negative integer that strictly decreases with every move.

Generating functions

The sequence (an)(a_n) becomes the series A(x)=∑anxnA(x) = \sum a_n x^n. A counting problem becomes polynomial algebra.

  • Partitions. Partitions of nn into distinct parts have generating function ∏k(1+xk)\prod_k (1 + x^k), and into odd parts ∏k11−x2k−1\prod_k \frac{1}{1 - x^{2k-1}}. The two are equal, because 1+xk=1−x2k1−xk1 + x^k = \frac{1 - x^{2k}}{1 - x^k}, so the counts are equal (Euler).
  • Roots-of-unity filter. With ω=e2πi/3\omega = e^{2\pi i/3}, and since 1+ωk+ω2k1 + \omega^k + \omega^{2k} is 33 when 3∣k3 \mid k and 00 otherwise:
∑3∣k(nk)=(1+1)n+(1+ω)n+(1+ω2)n3=2n+2cos⁡(nπ/3)3.\sum_{3 \mid k} \binom{n}{k} = \frac{(1 + 1)^n + (1 + \omega)^n + (1 + \omega^2)^n}{3} = \frac{2^n + 2\cos(n\pi/3)}{3} .

Linearity of expectation

E[X+Y]=E[X]+E[Y]\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y] always, with no independence needed. Write the quantity you want as a sum of indicators X=∑i1AiX = \sum_i \mathbf{1}_{A_i}, so that E[X]=∑iP(Ai)\mathbb{E}[X] = \sum_i \mathbb{P}(A_i).

  • Fixed points of a random permutation: X=∑i=1n1[σ(i)=i]X = \sum_{i=1}^{n} \mathbf{1}[\sigma(i) = i], and each term has probability 1n\frac1n. Hence E[X]=1\mathbb{E}[X] = 1 for every nn.
  • Probabilistic method: if E[X]=m\mathbb{E}[X] = m, there is an outcome with X≥mX \ge m and one with X≤mX \le m. If E[X]<1\mathbb{E}[X] < 1 for an integer X≥0X \ge 0, then P(X=0)>0\mathbb{P}(X = 0) > 0.

Pitfalls

  • Variance is not linear. Var⁡(X+Y)=Var⁡X+Var⁡Y\operatorname{Var}(X + Y) = \operatorname{Var} X + \operatorname{Var} Y only for uncorrelated variables.
  • Union: P(A∪B)≤P(A)+P(B)\mathbb{P}(A \cup B) \le \mathbb{P}(A) + \mathbb{P}(B), 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 xx.

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.