Combinatorics – Complete Reference Guide

1. Basic Counting Principles

Sum Rule

If tasks are mutually exclusive:

$|A \cup B| = |A| + |B| - |A \cap B|$

Product Rule

Independent sequential choices:

Total outcomes = $n_1 \times n_2 \times \cdots \times n_k$

Division Rule

Equivalent outcomes (symmetry):

$\frac{\text{Total outcomes}}{\text{Equivalence class size}}$

Use when sequence/order doesn't matter.

2. Permutations

Without Repetition

Arrange $k$ of $n$ items:

$P(n,k) = \frac{n!}{(n-k)!}$

$P(n) = n!$ (all items)

With Repetition

Each position any of $n$ choices:

$P_{\text{rep}}(n,k) = n^k$

Circular Permutations

Rotations are identical:

$P_{\text{circ}}(n) = (n-1)!$

Distinct objects only.

3. Combinations

Without Repetition

Choose $k$ of $n$ items (unordered):

$\binom{n}{k} = \frac{n!}{k!(n-k)!}$

With Repetition

Choose with replacement:

$\binom{n+k-1}{k} = \binom{n+k-1}{n-1}$

Symmetry

$\binom{n}{k} = \binom{n}{n-k}$

Pascal's Identity

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

4. Binomial Theorem & Pascal's Triangle

Binomial Expansion

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

Special Cases

$(1+1)^n = 2^n = \sum \binom{n}{k}$

$(1-1)^n = 0 = \sum (-1)^k \binom{n}{k}$ (odd $n$)

Row Sum

Row $n$ sum: $2^n$

Construction

Each entry is sum of two above.

Row $n$ has entries $\binom{n}{k}$.

5. Multinomial Coefficients

Definition

Distribute $n$ items into $m$ groups:

$\binom{n}{k_1, k_2, \ldots, k_m} = \frac{n!}{k_1! k_2! \cdots k_m!}$

where $k_1 + k_2 + \cdots + k_m = n$

Multinomial Theorem

$(x_1+x_2+\cdots+x_m)^n = \sum \binom{n}{k_1, \ldots, k_m} x_1^{k_1} \cdots x_m^{k_m}$

Generalizes binomial coefficients.

6. Stars & Bars

Distribute Identical Items

$n$ identical objects into $k$ distinct bins:

$\binom{n+k-1}{k-1} = \binom{n+k-1}{n}$

With Lower Bounds

Each bin gets $\geq m_i$ items:

Subtract minimums first, then apply above.

Weak Compositions

Solutions to $x_1+x_2+\cdots+x_k=n$ with $x_i \geq 0$:

$\binom{n+k-1}{k-1}$

Stars: objects, Bars: dividers.

7. Inclusion-Exclusion

General Formula

$|\bigcup A_i| = \sum|A_i| - \sum|A_i \cap A_j|$ $+ \sum|A_i \cap A_j \cap A_k| - \cdots$

Complement Form

$|\overline{A_1 \cup \cdots \cup A_n}| = |U| - |\bigcup A_i|$

Applications

Counting surjections.

Counting primes (Sieve).

Derangements.

8. Derangements

Definition

Permutations with no fixed points:

$D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$

Approximation

$D_n \approx \frac{n!}{e}$ (for large $n$)

Recurrence

$D_n = (n-1)(D_{n-1} + D_{n-2})$

$D_n = n \cdot D_{n-1} + (-1)^n$

$D_0=1, D_1=0, D_2=1, D_3=2$

9. Pigeonhole Principle

Basic Form

$n$ items in $k$ bins, $n > k$:

Some bin has $\geq 2$ items.

Generalized Form

$n$ items in $k$ bins:

Some bin has $\geq \lceil n/k \rceil$ items.

Applications

Birthday problem.

Diophantine approximations.

Graph coloring lower bounds.

10. Generating Functions

Ordinary (OGF)

$A(x) = \sum_{n=0}^\infty a_n x^n$

Exponential (EGF)

$E(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!}$

Common Series

$\frac{1}{1-x} = \sum x^n$

$\frac{1}{(1-x)^k} = \sum \binom{n+k-1}{k-1} x^n$

OGF for combinatorics, EGF for labeled structures.

11. Recurrence Relations

Linear Homogeneous

$a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$

Characteristic eq: $r^k - c_1 r^{k-1} - \cdots - c_k = 0$

Solution Steps

1. Find characteristic roots.

2. General solution: $a_n = \sum A_i r_i^n$.

3. Use initial conditions.

Non-Homogeneous

$a_n = c_1 a_{n-1} + f(n)$

Solution: homogeneous + particular.

12. Catalan Numbers

Definition

$C_n = \frac{1}{n+1}\binom{2n}{n}$

Recurrence

$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$

$C_n = \frac{4n-2}{n+1} C_{n-1}$

Counts

Balanced parentheses.

Dyck paths (never go below diagonal).

Binary trees, triangulations.

$C_0=1, C_1=1, C_2=2, C_3=5$

13. Stirling Numbers

Second Kind $S(n,k)$

Partitions of $n$ items into $k$ non-empty subsets:

$S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$

First Kind $c(n,k)$

Permutations of $n$ items with $k$ cycles:

$c(n,k) = c(n-1,k-1) + (n-1) c(n-1,k)$

Bell Numbers

$B_n = \sum_{k=0}^n S(n,k)$ (all partitions)

$S(3,2) = 3, S(4,2) = 7$

14. Partition Numbers

Integer Partitions $p(n)$

Ways to write $n$ as sum of positive integers (order irrelevant):

$p(5) = 7$ (5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1)

Ferrers Diagram

Visual representation: dots in left-justified rows.

Euler's Theorem

Number of partitions with odd parts = number with distinct parts.

No closed form, use generating functions or recursion.

15. Burnside's Lemma

Formula

Number of distinct colorings under group action:

$|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$

where $|X^g|$ = elements fixed by $g$

Polya's Enumeration

$\frac{1}{|G|} \sum_{g \in G} P_g(c_1, \ldots, c_k)$

Applications

Counting necklaces, bracelets.

Symmetries of polyhedra.

16. Ramsey Theory

Basic Statement

In any coloring of edges, monochromatic structure exists.

Ramsey Number $R(m,n)$

Min vertices needed to guarantee monochromatic $K_m$ or $K_n$.

$R(3,3) = 6, R(3,4) = 9$

Van der Waerden

For any coloring of integers, monochromatic arithmetic progression exists.

Guarantees structure in any partition.

COMBINATORICS Complete Reference Sheet