Chapter 17 — Key Takeaways

Advanced Counting: pigeonhole, stars and bars, inclusion–exclusion, generating functions. Reread this before an exam.

The four tools at a glance

Tool Use it when… Core result
Pigeonhole you must show a collision/repeat exists $n>m$ objects in boxes $\Rightarrow$ some box has $\ge 2$
Generalized pigeonhole you need a bound on the fullest box some box has $\ge \left\lceil \dfrac{n}{m}\right\rceil$
Stars and bars distributing identical objects into distinct boxes $\dbinom{n+k-1}{k-1}$
Inclusion–exclusion counting a union of overlapping sets / "at least one" alternating sum of intersections
Generating functions you want a whole sequence of counts, or to encode constraints answer $= [x^n]A(x)$

Pigeonhole — quick reference

Form Statement
Basic $n$ objects, $m$ boxes, $n>m$ $\Rightarrow$ some box $\ge 2$
As a function $\lvert A\rvert>\lvert B\rvert$ (finite) $\Rightarrow$ $f\colon A\to B$ not injective
Generalized $n$ objects, $m$ boxes $\Rightarrow$ some box $\ge \lceil n/m\rceil$
  • Proof pattern (always): assume the conclusion fails (every box "spread out"), sum the max counts, get a total $< n$ → contradiction.
  • The skill is choosing the holes. Divisibility problem? Holes = remainders mod $m$ (there are exactly $m$). Geometry? Holes = a partition of the region. Then "two in one box" must mean what you want.
  • Existence only: tells you a collision must exist; never where, and says nothing when $n\le m$.

CS payoff: keys $>$ slots $\Rightarrow$ a hash collision is guaranteed (no injective map from a bigger set into a smaller one). → Chapter 26.

Stars and bars — quick reference

Counting non-negative integer solutions of $x_1+x_2+\cdots+x_k=n$:

Constraint Count How
boxes may be empty ($x_i\ge0$) $\dbinom{n+k-1}{k-1}=\dbinom{n+k-1}{n}$ $n$ stars, $k-1$ bars
every box non-empty ($x_i\ge1$) $\dbinom{n-1}{k-1}$ give 1 to each box first, then distribute $n-k$
some box $x_i\ge c$ substitute $y_i=x_i-c$, then use the non-negative formula on $n-c$ shift the lower bound away
  • Same formula = combinations with repetition: choosing $n$ items from $k$ types, order irrelevant, repeats allowed $=\binom{n+k-1}{n}$.
  • Decision rule: identical objects + distinct boxes → stars and bars. Distinct objects → permutations/combinations (Ch. 16).

Inclusion–exclusion (general) — quick reference

$$\left\lvert \bigcup_{i=1}^{n} A_i \right\rvert=\sum_i\lvert A_i\rvert-\sum_{i

  • Sign rule: a $t$-fold intersection enters with sign $(-1)^{t+1}$ (add singles, subtract pairs, add triples, …).
  • Why it works: an element in $s$ of the sets is counted $\sum_{t=1}^{s}(-1)^{t+1}\binom{s}{t}=1$ time, because $\sum_{t=0}^{s}(-1)^t\binom{s}{t}=(1-1)^s=0$.
  • Complement trick: "none of the properties" $=$ (universe) $-$ $\lvert\bigcup A_i\rvert$. This is how derangements and surjections are counted.
Counting "divisible by 2, 3, or 5" in $1..1000$ value
singles $\lfloor 1000/2\rfloor+\lfloor1000/3\rfloor+\lfloor1000/5\rfloor$ $500+333+200=1033$
pairs $\lfloor1000/6\rfloor+\lfloor1000/10\rfloor+\lfloor1000/15\rfloor$ $166+100+66=332$
triple $\lfloor1000/30\rfloor$ $33$
union $=1033-332+33$ 734 (so $266$ divisible by none)

Generating functions — quick reference

Definition: OGF of $a_0,a_1,a_2,\dots$ is $A(x)=\sum_{n\ge0}a_n x^n$. Answer for size $n$ is the coefficient $[x^n]A(x)$. $x$ is a formal label — no convergence needed.

Building block Series Models
$\dfrac{1}{1-x}$ $1+x+x^2+\cdots$ unlimited supply of one item
$1+x+\cdots+x^c$ finite at most $c$ of an item
$1+x^2+x^4+\cdots=\dfrac{1}{1-x^2}$ even-only an even number of an item
$1+x^d+x^{2d}+\cdots=\dfrac{1}{1-x^d}$ multiples of $d$ item of "size" $d$
$(1+x)^n$ $\sum\binom nk x^k$ $n$ distinct items, each in/out
$\dfrac{1}{(1-x)^k}$ $\sum\binom{n+k-1}{k-1}x^n$ distribute identical items into $k$ boxes (recovers stars & bars)
  • Method: each independent choice/rule → a factor; legal sizes → which powers the factor may contribute; multiply the factors; read the coefficient of $x^n$.
  • Multiplication = convolution: $[x^n](PQ)=\sum_{i+j=n}p_i q_j$ — exactly "combine one term from each factor and total the exponents."
  • Keep enough low-order terms of each factor to reach $x^n$.
  • Forward: generating functions are the systematic way to solve recurrences (Ch. 18–19, incl. Fibonacci's closed form).

Derangements & surjections (inclusion–exclusion in action)

Object Formula First values
Derangements $D_n$ (perms with no fixed point) $D_n=n!\displaystyle\sum_{t=0}^{n}\frac{(-1)^t}{t!}$ $D_0..D_5=1,0,1,2,9,44$
Derangement recurrence $D_n=(n-1)(D_{n-1}+D_{n-2})$, $D_0=1,D_1=0$ —
Derangement limit $\dfrac{D_n}{n!}\to e^{-1}\approx0.3679$ already $0.375$ at $n=4$
Surjections $n$-set onto $m$-set $\displaystyle\sum_{j=0}^{m}(-1)^j\binom{m}{j}(m-j)^n$ $(3\to2)=6,\ (4\to3)=36$
  • Derangement setup: $A_i=$ perms fixing position $i$; $\lvert$ $t$-fold intersection $\rvert=(n-t)!$; $D_n=n!-\lvert\bigcup A_i\rvert$.
  • Surjection setup: total functions $=m^n$; $A_i=$ functions missing target $i$; missing $j$ targets gives $(m-j)^n$.

Common pitfalls

Pitfall Fix
Reading pigeonhole as "safe if $n\le m$" it only guarantees a collision when $n>m$; collisions still possible below
Forgetting to invent the holes restate the goal as "two in one box"; for divisibility use remainders mod $m$
Mixing $x_i\ge0$ vs $x_i\ge1$ in stars & bars empty allowed $\to\binom{n+k-1}{k-1}$; non-empty $\to\binom{n-1}{k-1}$
Wrong signs in inclusion–exclusion $t$-fold term sign is $(-1)^{t+1}$: $+,-,+,-,\dots$
Truncating a generating-function factor too early keep terms up to $x^n$ in every factor before reading $[x^n]$
Counting derangements directly count "$\ge1$ fixed point" by I–E, then take the complement

Toolkit additions (combinatorics.py)

def stars_and_bars(n, k):     # comb(n+k-1, k-1): identical objs into k boxes
def derangement_count(n):     # D_n via D_n=(n-1)(D_{n-1}+D_{n-2})
# e.g. stars_and_bars(12, 4) == 455 ;  derangement_count(5) == 44

Builds on Ch. 15–16 (perm_count, comb_count, permutations, combinations); feeds Ch. 20 probability (favorable / total counts) and the capstone (sizing search spaces).

One-line decision aid

"Exists a repeat?" → pigeonhole. "How full is the fullest?" → generalized pigeonhole. "Distribute identical things / choose with repetition?" → stars and bars. "At least one of several overlapping properties?" → inclusion–exclusion (complement for "none"). "A whole sequence of counts, or messy per-item constraints?" → generating functions.