Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs

A single-page survey of undergraduate combinatorics. Covers the fundamentals of counting, binomial coefficients, inclusion-exclusion, generating functions, Catalan numbers, Ramsey theory, Burnside and Polya enumeration, combinatorial designs, posets, and algebraic combinatorics. Includes a dependency diagram and a theorem-algorithm directory.

Folio Official

March 1, 2026

1. Introduction: How to Use This Article

This article provides a single-page panoramic view of undergraduate combinatorics. For each topic we state the key definitions, major theorems, and principal algorithms in concise form.

How to use this page:

Newcomers: read the sections in order to build a coherent picture of the subject.
Review or exam preparation: jump to any section from the table of contents.
Competitive-programming reference: Section 14, “ Theorem and Algorithm Directory,”{} collects all the major results in one list.

The dependency diagram below shows how the main topics are interrelated.

graph TD
    A["Fundamentals of Counting"] --> B["Binomial Coefficients and the Binomial Theorem"]
    A --> C["Inclusion-Exclusion"]
    B --> C
    B --> D["Generating Functions I (Ordinary)"]
    C --> D
    D --> E["Generating Functions II (Exponential)"]
    A --> F["Recurrences and Counting"]
    D --> F
    B --> G["Catalan Numbers and Lattice Paths"]
    D --> G
    F --> G
    A --> H["Pigeonhole Principle and Ramsey Theory"]
    B --> I["Burnside and Pólya Enumeration"]
    A --> J["Combinatorial Designs"]
    C --> K["Posets and Lattices"]
    D --> L["Algebraic Combinatorics"]
    E --> L
    G --> L

    style A fill:#f5f5f5,stroke:#333,color:#000
    style D fill:#f5f5f5,stroke:#333,color:#000
    style G fill:#f5f5f5,stroke:#333,color:#000
    style L fill:#f5f5f5,stroke:#333,color:#000

Remark 1.

This article is designed to accompany the “ Combinatorics Textbook”{} series. Links at the end of each section point to the corresponding full-length chapter for detailed exposition and complete proofs.

2. Fundamentals of Counting

Definition 2 (Rule of sum and rule of product).

Rule of sum: if events

A_{1}, \dots, A_{k}

are pairwise disjoint, the number of ways for at least one of them to occur is

∣ A_{1} ∣ + \dots + ∣ A_{k} ∣

. Rule of product: when independent choices are made in sequence, the total number of outcomes is the product of the number of choices at each stage.

Definition 3 (Permutations and combinations).

The number of permutations (ordered selections) of

r

objects from a set of

n

distinct objects is

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

. The number of combinations (unordered selections) is

(r n) = \frac{n !}{r ! ( n - r )!}

Definition 4 (Permutations and combinations with repetition).

The number of permutations with repetition when choosing

r

objects from

n

types (repetition allowed, order matters) is

n^{r}

. The number of combinations with repetition (multisets) is

(r n + r - 1) = H (n, r)

Theorem 5 (Multinomial coefficient).

The number of ways to partition

n

objects into

k

groups of sizes

n_{1}, \dots, n_{k}

with

n_{1} + \dots + n_{k} = n

(n _{1} , n _{2} , \dots , n _{k} n) = \frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}

For more details:

https://interconnectd.app/articles/zRkJ8HA9YVar72IjiO4c

3. Binomial Coefficients and the Binomial Theorem

Theorem 6 (Binomial theorem).

For any non-negative integer

n

and any

x, y

(x + y)^{n} = k = 0 \sum n (k n) x^{k} y^{n - k}

Theorem 7 (Fundamental identities for binomial coefficients).

Symmetry: $(k n) = (n - k n)$
Pascal's rule: $(k n) = (k - 1 n - 1) + (k n - 1)$
Vandermonde's convolution: $(r m + n) = \sum_{k = 0}^{r} (k m) (r - k n)$
Absorption identity: $k (k n) = n (k - 1 n - 1)$
Row sum: $\sum_{k = 0}^{n} (k n) = 2^{n}$

Theorem 8 (Hockey-stick identity).

i = r \sum n (r i) = (r + 1 n + 1)

Definition 9 (Generalized binomial coefficient).

For a real number

α

and a non-negative integer

k

, define

(k α) = \frac{α ( α - 1 ) \dots ( α - k + 1 )}{k !}

. This extends the binomial theorem to a formal power series.

For more details:

https://interconnectd.app/articles/Wa9bXQsgM1i1BPbKwiDj

4. The Inclusion-Exclusion Principle

Theorem 10 (Inclusion-exclusion principle).

For finite sets

A_{1}, A_{2}, \dots, A_{n}

i = 1 ⋃ n A_{i} = i \sum ∣ A_{i} ∣ - i < j \sum ∣ A_{i} \cap A_{j} ∣ + i < j < k \sum ∣ A_{i} \cap A_{j} \cap A_{k} ∣ - \dots + (- 1)^{n - 1} ∣ A_{1} \cap \dots \cap A_{n} ∣

Theorem 11 (Derangements).

The number of permutations of

n

elements with no fixed point (a derangement) is

D_{n} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}

n \to \infty

D_{n} / n! \to 1/ e

Theorem 12 (Euler's totient function).

By inclusion-exclusion,

φ (n) = n \prod_{p ∣ n} (1 - \frac{1}{p})

, where the product runs over the distinct prime divisors

p

n

Algorithms:

Fast zeta transform / fast Möbius transform: computes inclusion-exclusion over set functions in $O (n \cdot 2^{n})$ .

For more details:

https://interconnectd.app/articles/8mnGUym2F56td12OtiGf

5. Generating Functions I (Ordinary)

Definition 13 (Ordinary generating function).

The ordinary generating function (OGF) of a sequence

{a_{n}}_{n \geq 0}

is the formal power series

A (x) = n = 0 \sum \infty a_{n} x^{n}

Theorem 14 (Standard OGFs).

$\frac{1}{1 - x} = \sum_{n \geq 0} x^{n}$ (geometric series)
$\frac{1}{( 1 - x ) ^{k}} = \sum_{n \geq 0} (k - 1 n + k - 1) x^{n}$ (combinations with repetition)
$\frac{1}{1 - x - x ^{2}} = \sum_{n \geq 0} F_{n} x^{n}$ (Fibonacci numbers)

Theorem 15 (Operations on generating functions).

Sum: $A (x) + B (x)$ encodes the termwise sum ${a_{n} + b_{n}}$ .
Product (convolution): $A (x) B (x)$ encodes ${\sum_{k = 0}^{n} a_{k} b_{n - k}}$ .
Composition: $A (B (x))$ corresponds to the composition of combinatorial constructions.

Remark 16.

In competitive programming, convolution is commonly accelerated to

O (n lo g n)

using the NTT (number-theoretic transform).

For more details:

https://interconnectd.app/articles/jY8joQWd92UIXEwJmSbI

6. Generating Functions II (Exponential)

Definition 17 (Exponential generating function).

The exponential generating function (EGF) of a sequence

{a_{n}}_{n \geq 0}

\hat{A} (x) = n = 0 \sum \infty a_{n} \frac{x ^{n}}{n !}

EGFs are the natural tool for counting labeled structures.

Theorem 18 (Standard EGFs).

$e^{x} = \sum_{n \geq 0} \frac{x ^{n}}{n !}$ : $a_{n} = 1$ (all labeled sets).
$e^{e^{x} - 1} = \sum_{n \geq 0} B_{n} \frac{x ^{n}}{n !}$ : $B_{n}$ is the $n$ -th Bell number (number of set partitions).
$- ln (1 - x) = \sum_{n \geq 1} (n - 1)! \frac{x ^{n}}{n !}$ : connected permutations (cycles).

Theorem 19 (Exponential formula).

C (x)

is the EGF of a labeled structure

C

, then the EGF of the set construction (unordered collections of

C

-structures) is

e^{C (x)}

Theorem 20 (Product of EGFs and labeled merging).

\hat{A} (x) \cdot \hat{B} (x) = \sum_{n \geq 0} (\sum_{k = 0}^{n} (k n) a_{k} b_{n - k}) \frac{x ^{n}}{n !}

. This corresponds to partitioning the label set into two parts and placing independent structures on each.

For more details:

https://interconnectd.app/articles/nm9HWZkwyxzryHxOrn52

7. Recurrences and Counting

Definition 21 (Linear recurrence).

A constant-coefficient linear recurrence of order

d

is a relation of the form

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{d} a_{n - d}

Theorem 22 (Characteristic equation).

The characteristic equation of the recurrence

a_{n} = c_{1} a_{n - 1} + \dots + c_{d} a_{n - d}

x^{d} - c_{1} x^{d - 1} - \dots - c_{d} = 0

. When the roots

r_{1}, \dots, r_{d}

are all distinct, the general term is

a_{n} = α_{1} r_{1}^{n} + \dots + α_{d} r_{d}^{n}

Theorem 23 (Generating-function method).

The OGF of a linear recurrence of order

d

is a rational function

\frac{P ( x )}{Q ( x )}

, and partial-fraction decomposition yields the closed-form general term.

Example 24 (Fibonacci numbers).

The recurrence

F_{n} = F_{n - 1} + F_{n - 2}

with

F_{0} = 0

F_{1} = 1

has the closed form

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}

, where

φ = \frac{1 + 5}{2}

and

ψ = \frac{1 - 5}{2}

Algorithms:

Matrix exponentiation: computes the $n$ -th term of an order- $d$ linear recurrence in $O (d^{3} lo g n)$ .
Kitamasa's method: achieves $O (d^{2} lo g n)$ , or $O (d lo g d lo g n)$ with FFT, via polynomial arithmetic.

For more details:

https://interconnectd.app/articles/2mSrUhnxI0MsDHc0xNfR

8. Catalan Numbers and Lattice Paths

Definition 25 (Catalan numbers).

The Catalan numbers

C_{n}

are defined by

C_{n} = \frac{1}{n + 1} (n 2 n) = (n 2 n) - (n + 1 2 n)

The first several values are

C_{0} = 1, C_{1} = 1, C_{2} = 2, C_{3} = 5, C_{4} = 14, C_{5} = 42

Theorem 26 (Recurrence for Catalan numbers).

C_{0} = 1

and

C_{n + 1} = \sum_{k = 0}^{n} C_{k} C_{n - k}

. The OGF is

C (x) = \frac{1 - 1 - 4 x}{2 x}

Theorem 27 (Combinatorial interpretations of

C_{n}

C_{n}

counts each of the following:

Dyck paths from $(0, 0)$ to $(2 n, 0)$ .
Full binary trees with $n + 1$ leaves.
Ways to parenthesize a product of $n$ factors.
Triangulations of a convex $(n + 2)$ -gon.
Non-crossing partitions of an $n$ -element set.

Theorem 28 (Reflection principle).

Among lattice paths from

(0, 0)

(m, n)

using unit right and up steps, the number that never cross the diagonal

y = x

is obtained by subtracting the “ bad”{} paths—counted via reflection—from the total

(m m + n)

Theorem 29 (Ballot problem).

Suppose candidate

A

receives

a

votes and candidate

B

receives

b

votes, with

a > b

. The probability that

A

leads throughout the entire counting process is

\frac{a - b}{a + b}

For more details:

https://interconnectd.app/articles/S8oJ7jobi5Ym6b6agG1r

9. The Pigeonhole Principle and Ramsey Theory

Theorem 30 (Pigeonhole principle).

n + 1

or more objects are placed into

n

boxes, at least one box contains two or more objects. Generalization: if

kn + 1

objects are placed into

n

boxes, at least one box contains

k + 1

or more objects.

Theorem 31 (Erdős–Szekeres theorem).

Every sequence of real numbers of length at least

mn + 1

contains a monotonically increasing subsequence of length

m + 1

or a monotonically decreasing subsequence of length

n + 1

Definition 32 (Ramsey numbers).

The Ramsey number

R (s, t)

is the smallest

n

such that every red-blue

2

-coloring of the edges of

K_{n}

contains either a red

K_{s}

or a blue

K_{t}

Theorem 33 (Ramsey's theorem).

For all positive integers

s, t \geq 2

, the Ramsey number

R (s, t)

is finite. The upper bound

R (s, t) \leq (s - 1 s + t - 2)

holds. In particular,

R (3, 3) = 6

Theorem 34 (Lower bound for Ramsey numbers (Erdős)).

By the probabilistic method,

R (k, k) \geq 2^{k /2}

for all

k \geq 3

Remark 35.

Exact values of Ramsey numbers are known only for very small cases. For instance,

R (5, 5)

is known only to satisfy

43 \leq R (5, 5) \leq 48

For more details:

https://interconnectd.app/articles/nl8Ak8npPSxP9Z04NKgD

10. Burnside's Lemma and Pólya's Enumeration Theorem

Definition 36 (Group action and orbits).

A group

G

acts on a set

X

if there is a map

G \times X \to X

, written

(g, x) \mapsto g \cdot x

, satisfying

e \cdot x = x

and

(g h) \cdot x = g \cdot (h \cdot x)

. The orbit of

x

{g \cdot x ∣ g \in G}

Definition 37 (Fixed-point set).

For

g \in G

, the fixed-point set of

g

Fix (g) = {x \in X ∣ g \cdot x = x}

Theorem 38 (Burnside's lemma (Cauchy–Frobenius)).

If a finite group

G

acts on a finite set

X

, the number of orbits

∣ X / G ∣

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ Fix (g) ∣

Definition 39 (Cycle index).

Let a permutation group

G

act on

{1, \dots, n}

, and suppose a permutation

g \in G

has

j_{1}

fixed points,

j_{2}

two-cycles, and so on. The cycle index of

G

Z (G) = \frac{1}{∣ G ∣} g \in G \sum s_{1}^{j_{1} (g)} s_{2}^{j_{2} (g)} \dots s_{n}^{j_{n} (g)}

Theorem 40 (Pólya's enumeration theorem).

The number of colorings with

k

colors that are inequivalent under

G

equals

Z (G)

evaluated at

s_{i} = k

for all

i

. More generally, setting

s_{i} = w_{1}^{i} + w_{2}^{i} + \dots + w_{k}^{i}

yields the generating function for the distinct color patterns.

For more details:

https://interconnectd.app/articles/GstGj6NtSqVYApi8KlRm

11. Combinatorial Designs and Latin Squares

Definition 41 (Latin square).

n \times n

array in which each row and each column contains every element of

{1, 2, \dots, n}

exactly once is called a Latin square of order

n

Definition 42 (Mutually orthogonal Latin squares (MOLS)).

Two Latin squares

L_{1}, L_{2}

of order

n

are orthogonal if the

n^{2}

pairs

(L_{1} (i, j), L_{2} (i, j))

are all distinct. A set of

k

pairwise orthogonal Latin squares is called a

k

-MOLS.

Theorem 43 (Upper bound on MOLS).

The maximum number of MOLS of order

n

is at most

n - 1

. When

n

is a prime power, this maximum

n - 1

is attained.

Definition 44 (

t

(v, k, λ)

design).

t

(v, k, λ)

design is a collection

B

k

-element subsets (blocks) of a

v

-element set

V

such that every

t

-element subset of

V

is contained in exactly

λ

blocks.

Theorem 45 (Fisher's inequality).

In a

2

(v, k, λ)

design, the number of blocks

b

satisfies

b \geq v

Definition 46 (Steiner triple system).

2

(v, 3, 1)

design is called a Steiner triple system

S (2, 3, v)

. Such a system exists if and only if

v \equiv 1

3 (mod 6)

For more details:

https://interconnectd.app/articles/DidOu1tnntscl8ZGTT2j

12. Partially Ordered Sets and Lattices

Definition 47 (Partially ordered set (poset)).

A partially ordered set (poset) is a pair

(P, \leq)

consisting of a set

P

and a binary relation

\leq

that is reflexive, antisymmetric, and transitive.

Definition 48 (Chains and antichains).

A subset in which every two elements are comparable is called a chain. A subset in which no two elements are comparable is called an antichain.

Theorem 49 (Dilworth's theorem).

In a finite poset, the maximum size of an antichain equals the minimum number of chains needed to partition the poset.

Theorem 50 (Mirsky's theorem).

In a finite poset, the maximum length of a chain equals the minimum number of antichains needed to partition the poset.

Definition 51 (Lattice).

A poset

(L, \leq)

is a lattice if every pair of elements

a, b

has a least upper bound

a \lor b

(join) and a greatest lower bound

a \land b

(meet).

Definition 52 (Möbius function).

The Möbius function

μ : P \times P \to Z

on a finite poset

(P, \leq)

is defined inductively by

μ (x, x) = 1

and, for

x < y

\sum_{x \leq z \leq y} μ (x, z) = 0

Theorem 53 (Möbius inversion formula).

f (x) = \sum_{y \leq x} g (y)

, then

g (x) = \sum_{y \leq x} μ (y, x) f (y)

. The inclusion-exclusion principle is a special case of Möbius inversion on the power-set lattice.

For more details:

https://interconnectd.app/articles/acuWvC8ozxPEOncD8e6A

13. Combinatorics and Algebra

Definition 54 (Young diagrams and Young tableaux).

A partition of

n

is a weakly decreasing sequence

λ = (λ_{1} \geq λ_{2} \geq \dots \geq λ_{k} > 0)

with

∣ λ ∣ = \sum λ_{i} = n

. The corresponding array of boxes is a Young diagram, and a filling of the boxes with numbers is a Young tableau.

Definition 55 (Standard Young tableau (SYT)).

A standard Young tableau of shape

λ

is a filling of the Young diagram with

1, 2, \dots, n

(each used exactly once) such that entries increase strictly along every row and every column.

Theorem 56 (Hook-length formula).

The number

f^{λ}

of standard Young tableaux of shape

λ

f^{λ} = \frac{n !}{\prod _{u \in λ} h ( u )}

where

h (u)

is the hook length of the box

u

(the number of boxes directly to its right, directly below it, plus one for the box itself).

Theorem 57 (RSK correspondence).

There is a bijection, called the Robinson–Schensted–Knuth correspondence, between permutations of

{1, \dots, n}

and pairs

(P, Q)

of standard Young tableaux of the same shape. An immediate consequence is

\sum_{λ ⊢ n} (f^{λ})^{2} = n!

Definition 58 (Symmetric polynomials).

A polynomial invariant under all permutations of its variables is called a symmetric polynomial. The elementary symmetric polynomials

e_{k}

and the complete homogeneous symmetric polynomials

h_{k}

form fundamental generating sets.

Theorem 59 (Schur polynomials).

Schur polynomials

s_{λ}

, defined via semi-standard Young tableaux, form a basis of the ring of symmetric polynomials. The structure constants for multiplication of Schur polynomials (Littlewood–Richardson coefficients) arise in representation theory and intersection theory.

For more details:

https://interconnectd.app/articles/r5AaDr1oKse6YrI0MpMr

14. Theorem and Algorithm Directory

A one-line summary of the principal theorems and algorithms encountered in discrete mathematics and competitive programming.

Fundamental counting theorems:

Binomial theorem: $(x + y)^{n} = \sum (k n) x^{k} y^{n - k}$
Vandermonde's convolution: $(r m + n) = \sum_{k} (k m) (r - k n)$
Inclusion-exclusion: $∣ ⋃ A_{i} ∣ = \sum ∣ A_{i} ∣ - \sum ∣ A_{i} \cap A_{j} ∣ + \dots$
Derangements: $D_{n} = n! \sum_{k = 0}^{n} (- 1)^{k} / k!$
Catalan numbers: $C_{n} = \frac{1}{n + 1} (n 2 n)$
Exponential formula: EGF of the set construction $= e^{C (x)}$
Hook-length formula: $f^{λ} = n! / \prod h (u)$

Existence and structure theorems:

Pigeonhole principle: $n + 1$ objects into $n$ boxes forces at least one box with $\geq 2$
Erdős–Szekeres theorem: a sequence of length $mn + 1$ contains an increasing subsequence of length $m + 1$ or a decreasing one of length $n + 1$
Ramsey's theorem: $R (s, t)$ is finite; $R (s, t) \leq (s - 1 s + t - 2)$
Dilworth's theorem: maximum antichain size $=$ minimum chain partition size
Fisher's inequality: $b \geq v$ in any $2$ -design
RSK correspondence: permutations $\leftrightarrow$ pairs of standard Young tableaux; $\sum (f^{λ})^{2} = n!$

Group actions and symmetry:

Burnside's lemma: number of orbits $= \frac{1}{∣ G ∣} \sum ∣ Fix (g) ∣$
Pólya's enumeration theorem: substitute $s_{i} = k$ in the cycle index
Möbius inversion: generalization of inclusion-exclusion

Principal algorithms:

NTT (number-theoretic transform, convolution): $O (n lo g n)$
Fast zeta transform / Möbius transform: $O (n \cdot 2^{n})$
Matrix exponentiation (linear recurrences): $O (d^{3} lo g n)$
Kitamasa's method: $O (d^{2} lo g n)$ or $O (d lo g d lo g n)$
Binomial coefficient preprocessing ( $(k n) mod p$ ): $O (n)$ preprocessing, $O (1)$ per query
LIS (longest increasing subsequence): $O (n lo g n)$
RSK algorithm: $O (n n)$

Combinatorics Discrete Mathematics Summary Theorem Reference Algorithms Competitive Programming

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs

Folio Official

March 1, 2026

1. Introduction: How to Use This Article

This article provides a single-page panoramic view of undergraduate combinatorics. For each topic we state the key definitions, major theorems, and principal algorithms in concise form.

How to use this page:

Newcomers: read the sections in order to build a coherent picture of the subject.
Review or exam preparation: jump to any section from the table of contents.
Competitive-programming reference: Section 14, “ Theorem and Algorithm Directory,”{} collects all the major results in one list.

The dependency diagram below shows how the main topics are interrelated.

graph TD
    A["Fundamentals of Counting"] --> B["Binomial Coefficients and the Binomial Theorem"]
    A --> C["Inclusion-Exclusion"]
    B --> C
    B --> D["Generating Functions I (Ordinary)"]
    C --> D
    D --> E["Generating Functions II (Exponential)"]
    A --> F["Recurrences and Counting"]
    D --> F
    B --> G["Catalan Numbers and Lattice Paths"]
    D --> G
    F --> G
    A --> H["Pigeonhole Principle and Ramsey Theory"]
    B --> I["Burnside and Pólya Enumeration"]
    A --> J["Combinatorial Designs"]
    C --> K["Posets and Lattices"]
    D --> L["Algebraic Combinatorics"]
    E --> L
    G --> L

    style A fill:#f5f5f5,stroke:#333,color:#000
    style D fill:#f5f5f5,stroke:#333,color:#000
    style G fill:#f5f5f5,stroke:#333,color:#000
    style L fill:#f5f5f5,stroke:#333,color:#000

Remark 1.

2. Fundamentals of Counting

Definition 2 (Rule of sum and rule of product).

Rule of sum: if events

A_{1}, \dots, A_{k}

are pairwise disjoint, the number of ways for at least one of them to occur is

∣ A_{1} ∣ + \dots + ∣ A_{k} ∣

. Rule of product: when independent choices are made in sequence, the total number of outcomes is the product of the number of choices at each stage.

Definition 3 (Permutations and combinations).

The number of permutations (ordered selections) of

r

objects from a set of

n

distinct objects is

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

. The number of combinations (unordered selections) is

(r n) = \frac{n !}{r ! ( n - r )!}

Definition 4 (Permutations and combinations with repetition).

The number of permutations with repetition when choosing

r

objects from

n

types (repetition allowed, order matters) is

n^{r}

. The number of combinations with repetition (multisets) is

(r n + r - 1) = H (n, r)

Theorem 5 (Multinomial coefficient).

The number of ways to partition

n

objects into

k

groups of sizes

n_{1}, \dots, n_{k}

with

n_{1} + \dots + n_{k} = n

(n _{1} , n _{2} , \dots , n _{k} n) = \frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}

For more details:

https://interconnectd.app/articles/zRkJ8HA9YVar72IjiO4c

3. Binomial Coefficients and the Binomial Theorem

Theorem 6 (Binomial theorem).

For any non-negative integer

n

and any

x, y

(x + y)^{n} = k = 0 \sum n (k n) x^{k} y^{n - k}

Theorem 7 (Fundamental identities for binomial coefficients).

Symmetry: $(k n) = (n - k n)$
Pascal's rule: $(k n) = (k - 1 n - 1) + (k n - 1)$
Vandermonde's convolution: $(r m + n) = \sum_{k = 0}^{r} (k m) (r - k n)$
Absorption identity: $k (k n) = n (k - 1 n - 1)$
Row sum: $\sum_{k = 0}^{n} (k n) = 2^{n}$

Theorem 8 (Hockey-stick identity).

i = r \sum n (r i) = (r + 1 n + 1)

Definition 9 (Generalized binomial coefficient).

For a real number

α

and a non-negative integer

k

, define

(k α) = \frac{α ( α - 1 ) \dots ( α - k + 1 )}{k !}

. This extends the binomial theorem to a formal power series.

For more details:

https://interconnectd.app/articles/Wa9bXQsgM1i1BPbKwiDj

4. The Inclusion-Exclusion Principle

Theorem 10 (Inclusion-exclusion principle).

For finite sets

A_{1}, A_{2}, \dots, A_{n}

i = 1 ⋃ n A_{i} = i \sum ∣ A_{i} ∣ - i < j \sum ∣ A_{i} \cap A_{j} ∣ + i < j < k \sum ∣ A_{i} \cap A_{j} \cap A_{k} ∣ - \dots + (- 1)^{n - 1} ∣ A_{1} \cap \dots \cap A_{n} ∣

Theorem 11 (Derangements).

The number of permutations of

n

elements with no fixed point (a derangement) is

D_{n} = n! k = 0 \sum n \frac{( - 1 ) ^{k}}{k !}

n \to \infty

D_{n} / n! \to 1/ e

Theorem 12 (Euler's totient function).

By inclusion-exclusion,

φ (n) = n \prod_{p ∣ n} (1 - \frac{1}{p})

, where the product runs over the distinct prime divisors

p

n

Algorithms:

Fast zeta transform / fast Möbius transform: computes inclusion-exclusion over set functions in $O (n \cdot 2^{n})$ .

For more details:

https://interconnectd.app/articles/8mnGUym2F56td12OtiGf

5. Generating Functions I (Ordinary)

Definition 13 (Ordinary generating function).

The ordinary generating function (OGF) of a sequence

{a_{n}}_{n \geq 0}

is the formal power series

A (x) = n = 0 \sum \infty a_{n} x^{n}

Theorem 14 (Standard OGFs).

$\frac{1}{1 - x} = \sum_{n \geq 0} x^{n}$ (geometric series)
$\frac{1}{( 1 - x ) ^{k}} = \sum_{n \geq 0} (k - 1 n + k - 1) x^{n}$ (combinations with repetition)
$\frac{1}{1 - x - x ^{2}} = \sum_{n \geq 0} F_{n} x^{n}$ (Fibonacci numbers)

Theorem 15 (Operations on generating functions).

Sum: $A (x) + B (x)$ encodes the termwise sum ${a_{n} + b_{n}}$ .
Product (convolution): $A (x) B (x)$ encodes ${\sum_{k = 0}^{n} a_{k} b_{n - k}}$ .
Composition: $A (B (x))$ corresponds to the composition of combinatorial constructions.

Remark 16.

In competitive programming, convolution is commonly accelerated to

O (n lo g n)

using the NTT (number-theoretic transform).

For more details:

https://interconnectd.app/articles/jY8joQWd92UIXEwJmSbI

6. Generating Functions II (Exponential)

Definition 17 (Exponential generating function).

The exponential generating function (EGF) of a sequence

{a_{n}}_{n \geq 0}

\hat{A} (x) = n = 0 \sum \infty a_{n} \frac{x ^{n}}{n !}

EGFs are the natural tool for counting labeled structures.

Theorem 18 (Standard EGFs).

$e^{x} = \sum_{n \geq 0} \frac{x ^{n}}{n !}$ : $a_{n} = 1$ (all labeled sets).
$e^{e^{x} - 1} = \sum_{n \geq 0} B_{n} \frac{x ^{n}}{n !}$ : $B_{n}$ is the $n$ -th Bell number (number of set partitions).
$- ln (1 - x) = \sum_{n \geq 1} (n - 1)! \frac{x ^{n}}{n !}$ : connected permutations (cycles).

Theorem 19 (Exponential formula).

C (x)

is the EGF of a labeled structure

C

, then the EGF of the set construction (unordered collections of

C

-structures) is

e^{C (x)}

Theorem 20 (Product of EGFs and labeled merging).

\hat{A} (x) \cdot \hat{B} (x) = \sum_{n \geq 0} (\sum_{k = 0}^{n} (k n) a_{k} b_{n - k}) \frac{x ^{n}}{n !}

. This corresponds to partitioning the label set into two parts and placing independent structures on each.

For more details:

https://interconnectd.app/articles/nm9HWZkwyxzryHxOrn52

7. Recurrences and Counting

Definition 21 (Linear recurrence).

A constant-coefficient linear recurrence of order

d

is a relation of the form

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{d} a_{n - d}

Theorem 22 (Characteristic equation).

The characteristic equation of the recurrence

a_{n} = c_{1} a_{n - 1} + \dots + c_{d} a_{n - d}

x^{d} - c_{1} x^{d - 1} - \dots - c_{d} = 0

. When the roots

r_{1}, \dots, r_{d}

are all distinct, the general term is

a_{n} = α_{1} r_{1}^{n} + \dots + α_{d} r_{d}^{n}

Theorem 23 (Generating-function method).

The OGF of a linear recurrence of order

d

is a rational function

\frac{P ( x )}{Q ( x )}

, and partial-fraction decomposition yields the closed-form general term.

Example 24 (Fibonacci numbers).

The recurrence

F_{n} = F_{n - 1} + F_{n - 2}

with

F_{0} = 0

F_{1} = 1

has the closed form

F_{n} = \frac{φ ^{n} - ψ ^{n}}{5}

, where

φ = \frac{1 + 5}{2}

and

ψ = \frac{1 - 5}{2}

Algorithms:

Matrix exponentiation: computes the $n$ -th term of an order- $d$ linear recurrence in $O (d^{3} lo g n)$ .
Kitamasa's method: achieves $O (d^{2} lo g n)$ , or $O (d lo g d lo g n)$ with FFT, via polynomial arithmetic.

For more details:

https://interconnectd.app/articles/2mSrUhnxI0MsDHc0xNfR

8. Catalan Numbers and Lattice Paths

Definition 25 (Catalan numbers).

The Catalan numbers

C_{n}

are defined by

C_{n} = \frac{1}{n + 1} (n 2 n) = (n 2 n) - (n + 1 2 n)

The first several values are

C_{0} = 1, C_{1} = 1, C_{2} = 2, C_{3} = 5, C_{4} = 14, C_{5} = 42

Theorem 26 (Recurrence for Catalan numbers).

C_{0} = 1

and

C_{n + 1} = \sum_{k = 0}^{n} C_{k} C_{n - k}

. The OGF is

C (x) = \frac{1 - 1 - 4 x}{2 x}

Theorem 27 (Combinatorial interpretations of

C_{n}

C_{n}

counts each of the following:

Dyck paths from $(0, 0)$ to $(2 n, 0)$ .
Full binary trees with $n + 1$ leaves.
Ways to parenthesize a product of $n$ factors.
Triangulations of a convex $(n + 2)$ -gon.
Non-crossing partitions of an $n$ -element set.

Theorem 28 (Reflection principle).

Among lattice paths from

(0, 0)

(m, n)

using unit right and up steps, the number that never cross the diagonal

y = x

is obtained by subtracting the “ bad”{} paths—counted via reflection—from the total

(m m + n)

Theorem 29 (Ballot problem).

Suppose candidate

A

receives

a

votes and candidate

B

receives

b

votes, with

a > b

. The probability that

A

leads throughout the entire counting process is

\frac{a - b}{a + b}

For more details:

https://interconnectd.app/articles/S8oJ7jobi5Ym6b6agG1r

9. The Pigeonhole Principle and Ramsey Theory

Theorem 30 (Pigeonhole principle).

n + 1

or more objects are placed into

n

boxes, at least one box contains two or more objects. Generalization: if

kn + 1

objects are placed into

n

boxes, at least one box contains

k + 1

or more objects.

Theorem 31 (Erdős–Szekeres theorem).

Every sequence of real numbers of length at least

mn + 1

contains a monotonically increasing subsequence of length

m + 1

or a monotonically decreasing subsequence of length

n + 1

Definition 32 (Ramsey numbers).

The Ramsey number

R (s, t)

is the smallest

n

such that every red-blue

2

-coloring of the edges of

K_{n}

contains either a red

K_{s}

or a blue

K_{t}

Theorem 33 (Ramsey's theorem).

For all positive integers

s, t \geq 2

, the Ramsey number

R (s, t)

is finite. The upper bound

R (s, t) \leq (s - 1 s + t - 2)

holds. In particular,

R (3, 3) = 6

Theorem 34 (Lower bound for Ramsey numbers (Erdős)).

By the probabilistic method,

R (k, k) \geq 2^{k /2}

for all

k \geq 3

Remark 35.

Exact values of Ramsey numbers are known only for very small cases. For instance,

R (5, 5)

is known only to satisfy

43 \leq R (5, 5) \leq 48

For more details:

https://interconnectd.app/articles/nl8Ak8npPSxP9Z04NKgD

10. Burnside's Lemma and Pólya's Enumeration Theorem

Definition 36 (Group action and orbits).

A group

G

acts on a set

X

if there is a map

G \times X \to X

, written

(g, x) \mapsto g \cdot x

, satisfying

e \cdot x = x

and

(g h) \cdot x = g \cdot (h \cdot x)

. The orbit of

x

{g \cdot x ∣ g \in G}

Definition 37 (Fixed-point set).

For

g \in G

, the fixed-point set of

g

Fix (g) = {x \in X ∣ g \cdot x = x}

Theorem 38 (Burnside's lemma (Cauchy–Frobenius)).

If a finite group

G

acts on a finite set

X

, the number of orbits

∣ X / G ∣

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ Fix (g) ∣

Definition 39 (Cycle index).

Let a permutation group

G

act on

{1, \dots, n}

, and suppose a permutation

g \in G

has

j_{1}

fixed points,

j_{2}

two-cycles, and so on. The cycle index of

G

Z (G) = \frac{1}{∣ G ∣} g \in G \sum s_{1}^{j_{1} (g)} s_{2}^{j_{2} (g)} \dots s_{n}^{j_{n} (g)}

Theorem 40 (Pólya's enumeration theorem).

The number of colorings with

k

colors that are inequivalent under

G

equals

Z (G)

evaluated at

s_{i} = k

for all

i

. More generally, setting

s_{i} = w_{1}^{i} + w_{2}^{i} + \dots + w_{k}^{i}

yields the generating function for the distinct color patterns.

For more details:

https://interconnectd.app/articles/GstGj6NtSqVYApi8KlRm

11. Combinatorial Designs and Latin Squares

Definition 41 (Latin square).

n \times n

array in which each row and each column contains every element of

{1, 2, \dots, n}

exactly once is called a Latin square of order

n

Definition 42 (Mutually orthogonal Latin squares (MOLS)).

Two Latin squares

L_{1}, L_{2}

of order

n

are orthogonal if the

n^{2}

pairs

(L_{1} (i, j), L_{2} (i, j))

are all distinct. A set of

k

pairwise orthogonal Latin squares is called a

k

-MOLS.

Theorem 43 (Upper bound on MOLS).

The maximum number of MOLS of order

n

is at most

n - 1

. When

n

is a prime power, this maximum

n - 1

is attained.

Definition 44 (

t

(v, k, λ)

design).

t

(v, k, λ)

design is a collection

B

k

-element subsets (blocks) of a

v

-element set

V

such that every

t

-element subset of

V

is contained in exactly

λ

blocks.

Theorem 45 (Fisher's inequality).

In a

2

(v, k, λ)

design, the number of blocks

b

satisfies

b \geq v

Definition 46 (Steiner triple system).

2

(v, 3, 1)

design is called a Steiner triple system

S (2, 3, v)

. Such a system exists if and only if

v \equiv 1

3 (mod 6)

For more details:

https://interconnectd.app/articles/DidOu1tnntscl8ZGTT2j

12. Partially Ordered Sets and Lattices

Definition 47 (Partially ordered set (poset)).

A partially ordered set (poset) is a pair

(P, \leq)

consisting of a set

P

and a binary relation

\leq

that is reflexive, antisymmetric, and transitive.

Definition 48 (Chains and antichains).

A subset in which every two elements are comparable is called a chain. A subset in which no two elements are comparable is called an antichain.

Theorem 49 (Dilworth's theorem).

In a finite poset, the maximum size of an antichain equals the minimum number of chains needed to partition the poset.

Theorem 50 (Mirsky's theorem).

In a finite poset, the maximum length of a chain equals the minimum number of antichains needed to partition the poset.

Definition 51 (Lattice).

A poset

(L, \leq)

is a lattice if every pair of elements

a, b

has a least upper bound

a \lor b

(join) and a greatest lower bound

a \land b

(meet).

Definition 52 (Möbius function).

The Möbius function

μ : P \times P \to Z

on a finite poset

(P, \leq)

is defined inductively by

μ (x, x) = 1

and, for

x < y

\sum_{x \leq z \leq y} μ (x, z) = 0

Theorem 53 (Möbius inversion formula).

f (x) = \sum_{y \leq x} g (y)

, then

g (x) = \sum_{y \leq x} μ (y, x) f (y)

. The inclusion-exclusion principle is a special case of Möbius inversion on the power-set lattice.

For more details:

https://interconnectd.app/articles/acuWvC8ozxPEOncD8e6A

13. Combinatorics and Algebra

Definition 54 (Young diagrams and Young tableaux).

A partition of

n

is a weakly decreasing sequence

λ = (λ_{1} \geq λ_{2} \geq \dots \geq λ_{k} > 0)

with

∣ λ ∣ = \sum λ_{i} = n

. The corresponding array of boxes is a Young diagram, and a filling of the boxes with numbers is a Young tableau.

Definition 55 (Standard Young tableau (SYT)).

A standard Young tableau of shape

λ

is a filling of the Young diagram with

1, 2, \dots, n

(each used exactly once) such that entries increase strictly along every row and every column.

Theorem 56 (Hook-length formula).

The number

f^{λ}

of standard Young tableaux of shape

λ

f^{λ} = \frac{n !}{\prod _{u \in λ} h ( u )}

where

h (u)

is the hook length of the box

u

(the number of boxes directly to its right, directly below it, plus one for the box itself).

Theorem 57 (RSK correspondence).

There is a bijection, called the Robinson–Schensted–Knuth correspondence, between permutations of

{1, \dots, n}

and pairs

(P, Q)

of standard Young tableaux of the same shape. An immediate consequence is

\sum_{λ ⊢ n} (f^{λ})^{2} = n!

Definition 58 (Symmetric polynomials).

A polynomial invariant under all permutations of its variables is called a symmetric polynomial. The elementary symmetric polynomials

e_{k}

and the complete homogeneous symmetric polynomials

h_{k}

form fundamental generating sets.

Theorem 59 (Schur polynomials).

Schur polynomials

s_{λ}

For more details:

https://interconnectd.app/articles/r5AaDr1oKse6YrI0MpMr

14. Theorem and Algorithm Directory

A one-line summary of the principal theorems and algorithms encountered in discrete mathematics and competitive programming.

Fundamental counting theorems:

Binomial theorem: $(x + y)^{n} = \sum (k n) x^{k} y^{n - k}$
Vandermonde's convolution: $(r m + n) = \sum_{k} (k m) (r - k n)$
Inclusion-exclusion: $∣ ⋃ A_{i} ∣ = \sum ∣ A_{i} ∣ - \sum ∣ A_{i} \cap A_{j} ∣ + \dots$
Derangements: $D_{n} = n! \sum_{k = 0}^{n} (- 1)^{k} / k!$
Catalan numbers: $C_{n} = \frac{1}{n + 1} (n 2 n)$
Exponential formula: EGF of the set construction $= e^{C (x)}$
Hook-length formula: $f^{λ} = n! / \prod h (u)$

Existence and structure theorems:

Pigeonhole principle: $n + 1$ objects into $n$ boxes forces at least one box with $\geq 2$
Erdős–Szekeres theorem: a sequence of length $mn + 1$ contains an increasing subsequence of length $m + 1$ or a decreasing one of length $n + 1$
Ramsey's theorem: $R (s, t)$ is finite; $R (s, t) \leq (s - 1 s + t - 2)$
Dilworth's theorem: maximum antichain size $=$ minimum chain partition size
Fisher's inequality: $b \geq v$ in any $2$ -design
RSK correspondence: permutations $\leftrightarrow$ pairs of standard Young tableaux; $\sum (f^{λ})^{2} = n!$

Group actions and symmetry:

Burnside's lemma: number of orbits $= \frac{1}{∣ G ∣} \sum ∣ Fix (g) ∣$
Pólya's enumeration theorem: substitute $s_{i} = k$ in the cycle index
Möbius inversion: generalization of inclusion-exclusion

Principal algorithms:

NTT (number-theoretic transform, convolution): $O (n lo g n)$
Fast zeta transform / Möbius transform: $O (n \cdot 2^{n})$
Matrix exponentiation (linear recurrences): $O (d^{3} lo g n)$
Kitamasa's method: $O (d^{2} lo g n)$ or $O (d lo g d lo g n)$
Binomial coefficient preprocessing ( $(k n) mod p$ ): $O (n)$ preprocessing, $O (1)$ per query
LIS (longest increasing subsequence): $O (n lo g n)$
RSK algorithm: $O (n n)$

Combinatorics Discrete Mathematics Summary Theorem Reference Algorithms Competitive Programming

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

1. Introduction: How to Use This Article

2. Fundamentals of Counting

3. Binomial Coefficients and the Binomial Theorem

4. The Inclusion-Exclusion Principle

5. Generating Functions I (Ordinary)

6. Generating Functions II (Exponential)

7. Recurrences and Counting

8. Catalan Numbers and Lattice Paths

9. The Pigeonhole Principle and Ramsey Theory

10. Burnside's Lemma and Pólya's Enumeration Theorem

11. Combinatorial Designs and Latin Squares

12. Partially Ordered Sets and Lattices

13. Combinatorics and Algebra

14. Theorem and Algorithm Directory

Share your expertise with the world

More from Folio Official

Graph Theory: A Complete Summary of Definitions, Theorems, and Proofs

Number Theory: A Complete Summary of Definitions, Theorems, and Proofs

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

1. Introduction: How to Use This Article

2. Fundamentals of Counting

3. Binomial Coefficients and the Binomial Theorem

4. The Inclusion-Exclusion Principle

5. Generating Functions I (Ordinary)

6. Generating Functions II (Exponential)

7. Recurrences and Counting

8. Catalan Numbers and Lattice Paths

9. The Pigeonhole Principle and Ramsey Theory

10. Burnside's Lemma and Pólya's Enumeration Theorem

11. Combinatorial Designs and Latin Squares

12. Partially Ordered Sets and Lattices

13. Combinatorics and Algebra

14. Theorem and Algorithm Directory

Share your expertise with the world

More from Folio Official

Graph Theory: A Complete Summary of Definitions, Theorems, and Proofs

Number Theory: A Complete Summary of Definitions, Theorems, and Proofs

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums