Combinatorics Syllabus

State the generalized (strong) Pigeonhole Principle.

If $n$ objects are placed into $k$ boxes, then at least one box contains at least $\left\lceil \dfrac{n}{k} \right\rceil$ objects.

By the pigeonhole principle, what is the minimum number of people needed to guarantee that at least two share a birthday (365 days)?

$366$ people. With $n$ pigeons and $k = 365$ holes, $n > 365$ forces a shared birthday, so $n = 366$ guarantees it.

State the Binomial Theorem.

$$(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^{k}.$$

What is the coefficient of $x^{k}$ in the expansion of $(1 + x)^n$, and what does the term $\binom{n}{k}$ count?

The coefficient is $\binom{n}{k}$. It counts the number of ways to choose $k$ factors (out of $n$) to contribute an $x$, equivalently the number of $k$-subsets of an $n$-set.

Evaluate $\sum_{k=0}^{n} \binom{n}{k}$ and $\sum_{k=0}^{n} (-1)^k \binom{n}{k}$.

$$\sum_{k=0}^{n} \binom{n}{k} = 2^{n}, \qquad \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \ (n \ge 1).$$ These come from setting $x = 1$ and $x = -1$ in $(1+x)^n$.

State the Multinomial Theorem.

$$(x_1 + x_2 + \cdots + x_m)^n = \sum_{\substack{k_1 + \cdots + k_m = n \\ k_i \ge 0}} \binom{n}{k_1, k_2, \ldots, k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m},$$ where $\binom{n}{k_1,\ldots,k_m} = \dfrac{n!}{k_1!\,k_2! \cdots k_m!}$.

How many distinct terms appear in the expansion of $(x_1 + \cdots + x_m)^n$?

$\binom{n+m-1}{m-1}$, the number of nonnegative integer solutions to $k_1 + k_2 + \cdots + k_m = n$.

Give the closed-form formula for the $n$-th Catalan number.

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}, \qquad n \ge 0.$$

State the recurrence relation defining the Catalan numbers.

$$C_0 = 1, \qquad C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}.$$ Equivalently $C_{n+1} = \dfrac{2(2n+1)}{n+2}\,C_n$.

List three classic combinatorial objects counted by the Catalan number $C_n$.

(1) Balanced parenthesizations / valid sequences of $n$ pairs of parentheses; (2) full binary trees with $n+1$ leaves (or $n$ internal nodes); (3) monotonic lattice paths from $(0,0)$ to $(n,n)$ that stay weakly below the diagonal (Dyck paths); also triangulations of a convex $(n+2)$-gon.

Give the first several Catalan numbers $C_0, C_1, \ldots, C_5$.

$C_0 = 1,\ C_1 = 1,\ C_2 = 2,\ C_3 = 5,\ C_4 = 14,\ C_5 = 42$.

Define the ordinary generating function (OGF) of a sequence $(a_n)_{n \ge 0}$.

$$A(x) = \sum_{n=0}^{\infty} a_n x^{n} = a_0 + a_1 x + a_2 x^2 + \cdots.$$ It is a formal power series whose coefficient of $x^n$ encodes $a_n$.

Give the OGF of the constant sequence $a_n = 1$ and of $a_n = \binom{r}{n}$-type geometric sums.

$$\sum_{n=0}^{\infty} x^n = \frac{1}{1-x}, \qquad \sum_{n=0}^{\infty} \binom{n+k}{k} x^n = \frac{1}{(1-x)^{k+1}}.$$ Also $\sum_{n} a^n x^n = \dfrac{1}{1-ax}$.

How does multiplying two ordinary generating functions relate to the sequences (the convolution rule)?

If $A(x) = \sum a_n x^n$ and $B(x) = \sum b_n x^n$, then $A(x)B(x) = \sum_n c_n x^n$ where $c_n = \sum_{k=0}^{n} a_k\, b_{n-k}$ (the Cauchy product / convolution).

Define the exponential generating function (EGF) of a sequence $(a_n)_{n \ge 0}$.

$$A(x) = \sum_{n=0}^{\infty} a_n \frac{x^{n}}{n!}.$$ EGFs are used for labeled structures and arrangements where order matters.

What is the EGF of the sequence $a_n = 1$ for all $n$, and why is it natural?

$$\sum_{n=0}^{\infty} 1 \cdot \frac{x^n}{n!} = e^{x}.$$ This makes $e^x$ the fundamental EGF; e.g. the EGF for permutations ($a_n = n!$) is $\dfrac{1}{1-x}$ using the $n!$ weighting.

State the product rule for exponential generating functions.

If $A(x) = \sum a_n \frac{x^n}{n!}$ and $B(x) = \sum b_n \frac{x^n}{n!}$, then $A(x)B(x) = \sum_n c_n \frac{x^n}{n!}$ where $c_n = \sum_{k=0}^{n} \binom{n}{k} a_k\, b_{n-k}$ (binomial convolution). This models combining labeled structures.

When should you use an ordinary generating function versus an exponential generating function?

Use an OGF for unlabeled / unordered selection problems (combinations, integer partitions, multisets). Use an EGF for labeled / ordered arrangement problems (permutations, arrangements, distributing distinguishable objects), because the $n!$ weighting handles labelings.

Outline the generating-function method for solving a counting problem.

(1) Encode each object/choice as a factor (polynomial or series) whose exponents track a parameter; (2) multiply the factors to form the generating function; (3) simplify to closed form; (4) extract the coefficient of $x^n$ (via known series, partial fractions, or the binomial series) to get the count $a_n$.

Using generating functions, what is the OGF for the number of ways to make change/select with parts of sizes in a set, e.g. any number of items of size $k$?

An unlimited supply of an item of size $k$ contributes the factor $\dfrac{1}{1-x^{k}} = 1 + x^k + x^{2k} + \cdots$. The product over all allowed sizes gives the OGF; the coefficient of $x^n$ counts the ways to total $n$.

Define a linear recurrence relation with constant coefficients of order $k$.

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n),$$ where $c_1, \ldots, c_k$ are constants with $c_k \ne 0$. It is homogeneous if $f(n) = 0$ and requires $k$ initial conditions.

Write the characteristic equation of the homogeneous linear recurrence $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$.

$$r^{k} - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0.$$ Its roots (characteristic roots) determine the form of the general solution.

How do you write the general solution of a linear homogeneous recurrence when the characteristic equation has distinct roots $r_1, \ldots, r_k$?

$$a_n = \alpha_1 r_1^{n} + \alpha_2 r_2^{n} + \cdots + \alpha_k r_k^{n},$$ where the constants $\alpha_i$ are fixed by the initial conditions.

How does a repeated characteristic root of multiplicity $m$ affect the general solution of a linear recurrence?

A root $r$ of multiplicity $m$ contributes the terms $(\alpha_0 + \alpha_1 n + \alpha_2 n^2 + \cdots + \alpha_{m-1} n^{m-1}) r^{n}$ to the general solution.

Solve the Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ using its characteristic equation (Binet's formula).

Characteristic equation $r^2 - r - 1 = 0$ gives $r = \varphi = \frac{1+\sqrt5}{2}$, $\psi = \frac{1-\sqrt5}{2}$. With $F_0=0, F_1=1$: $$F_n = \frac{\varphi^{n} - \psi^{n}}{\sqrt 5}.$$

How do you find a particular solution for a non-homogeneous linear recurrence, and how is the full solution assembled?

Guess a particular solution $a_n^{(p)}$ of the same form as $f(n)$ (e.g. polynomial for polynomial $f$, $A s^n$ for $f(n)=s^n$; multiply by $n^s$ if it clashes with a characteristic root). The full solution is $a_n = a_n^{(h)} + a_n^{(p)}$, then fit constants using initial conditions.

What distinguishes a non-linear recurrence relation from a linear one? Give an example.

A non-linear recurrence has terms that are not first-degree in the previous terms — e.g. products, powers, or other nonlinear functions of $a_{n-1}, a_{n-2}, \ldots$. Example: the Catalan recurrence $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$ (a convolution, hence nonlinear), or $a_n = a_{n-1}^2 + 1$.

Describe how to solve a recurrence using ordinary generating functions.

Multiply the recurrence by $x^n$, sum over all valid $n$, and express the sums in terms of $A(x) = \sum a_n x^n$. Solve the resulting algebraic equation for $A(x)$, simplify (often by partial fractions), then extract $[x^n]A(x)$ to obtain a closed form for $a_n$.

Give the divide-and-conquer recurrence for merge sort and its solution (an application of recurrences).

$T(n) = 2\,T(n/2) + \Theta(n)$ with $T(1) = \Theta(1)$. By the Master Theorem (case $a = b^d$ with $a=2,b=2,d=1$), $$T(n) = \Theta(n \log n).$$

State the Master Theorem for recurrences $T(n) = a\,T(n/b) + \Theta(n^d)$ (application to algorithm analysis).

For $a \ge 1, b > 1, d \ge 0$: $T(n) = \Theta(n^{d})$ if $a < b^{d}$; $\ \Theta(n^{d} \log n)$ if $a = b^{d}$; $\ \Theta(n^{\log_b a})$ if $a > b^{d}$.

Give the recurrence for the Tower of Hanoi problem and its closed-form solution (a classic recurrence application).

Let $H_n$ be the minimum moves for $n$ disks: $H_n = 2H_{n-1} + 1$, $H_1 = 1$. Solving gives $$H_n = 2^{n} - 1.$$