Combinatorics meets dynamic programming: when counting becomes computation

Dynamic programming is bottom-up evaluation of a recurrence; a generating function is its analytic closed form. We draw the correspondence between the knapsack DP and generating function multiplication, discuss convolution and FFT, and survey the connections across the entire series.

Folio Official

March 1, 2026

This final article in the series examines the intimate relationship between combinatorics and dynamic programming (DP) – the single most important algorithmic technique in competitive programming. DP and combinatorics are two sides of the same coin, and understanding their connection opens a far wider range of problem-solving strategies.

1 DP is bottom-up evaluation of a recurrence

Remark 1.

At its core, DP is nothing more than evaluating a recurrence relation from small indices upward. Writing a DP solution means formulating a recurrence and filling in a table entry by entry, starting from the base cases.

Example 2 (Pascal's triangle as a DP table).

The Pascal identity from the second article,

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

, is a recurrence. Writing it as a DP:

dp [n] [r] = dp [n - 1] [r - 1] + dp [n - 1] [r]

with base cases

dp [n] [0] = dp [n] [n] = 1

. Filling this table for

n = 0, 1, 2, \dots

is precisely the construction of Pascal's triangle.

Remark 3.

Turning this observation around: the closed-form formula $(r n) = \frac{n !}{r ! ( n - r )!}$ is the "analytic solution" of the DP. The recurrence can be solved numerically via DP or analytically via the closed form. When no closed form is available, DP provides the numerical answer; when a closed form exists, it eliminates the need for DP entirely. This is the fundamental relationship between combinatorics and computation.

2 The knapsack problem and generating functions

Example 4 (0–1 knapsack (counting version)).

Given

n

items with weights

w_{1}, \dots, w_{n}

and values

v_{1}, \dots, v_{n}

, consider the counting variant: how many subsets of items have total weight exactly

W

The DP transition is

dp [i] [j] = dp [i - 1] [j] + dp [i - 1] [j - w_{i}],

where

dp [i] [j]

counts the number of subsets of the first

i

items with total weight

j

Remark 5.

In the language of generating functions, each item

i

contributes the polynomial

f_{i} (x) = 1 + x^{w_{i}}

(either we include item

i

, contributing weight

w_{i}

, or we do not). The answer is the coefficient of

x^{W}

in the product

F (x) = i = 1 \prod n (1 + x^{w_{i}}) .

The DP's iterative update – processing items one at a time and updating the weight array – corresponds exactly to multiplying these polynomials one by one.

Theorem 6 (The DP–generating function correspondence).

The recurrence underlying a DP corresponds to the product (convolution) of generating functions. Specifically:

Each row of the DP table is the coefficient sequence of a polynomial.
The DP transition (using the previous row to compute the next) is polynomial multiplication.
The entire DP table is the step-by-step expansion of a generating function product.

3 Convolution and FFT

As discussed in the fourth article, the product of generating functions corresponds to convolution.

Definition 7 (Convolution).

The convolution of sequences

{a_{n}}

and

{b_{n}}

is the sequence

{c_{n}}

defined by

c_{n} = \sum_{k = 0}^{n} a_{k} b_{n - k}

A naive computation takes $O (n^{2})$ time, but the Fast Fourier Transform (FFT) reduces this to $O (n lo g n)$ .

Remark 8 (The idea behind FFT).

The key insight is that polynomial multiplication is trivial in the point-value representation: simply multiply corresponding values. The FFT exploits this by converting between representations efficiently:

Coefficient representation $\to$ point-value representation ( $O (n lo g n)$ , via FFT).
Pointwise multiplication ( $O (n)$ ).
Point-value representation $\to$ coefficient representation ( $O (n lo g n)$ , via inverse FFT).

The overall cost is

O (n lo g n)

Example 9 (Convolution in competitive programming).

In competitive programming, NTT (Number Theoretic Transform – an FFT variant that works modulo a prime) is widely used. For instance, the probability distribution of the sum of

N

independent dice rolls is the

N

-fold convolution of a single die's distribution, and NTT computes it efficiently.

4 A retrospective of the series

Looking back across the eight articles, we can see how the topics in combinatorics form an organically connected whole.

Remark 10 (How the articles connect).

The foundations of counting (addition and multiplication principles) – the starting point. Counting is cardinality.
Binomial coefficients (Pascal's identity, binomial theorem) – the most fundamental counting tool. Pascal's triangle is a DP table.
Inclusion–exclusion (alternating sums) – the technique of "subtract the bad cases." The binomial identity $(1 - 1)^{m} = 0$ is the engine.
Generating functions (sequences as power series) – transforming recurrences into algebra. The analytic counterpart of DP.
Catalan numbers (reflection principle, bijections) – derived from a quadratic equation in the generating function. Bijections between parenthesizations and lattice paths.
The pigeonhole principle (existence proofs) – the power of non-constructive reasoning. The gateway to Ramsey theory.
Burnside's lemma (symmetry and group actions) – counting orbits via fixed-point averages.
DP and combinatorics (this article) – recurrence equals DP, generating function equals closed form, convolution equals FFT.

5 Beyond this introduction

Remark 11.

Many important topics lie beyond the scope of this introductory series:

Algebraic combinatorics: representation theory of groups and symmetric functions, Young tableaux and the Robinson–Schensted correspondence.
Probabilistic combinatorics: random graphs (the Erdos–Renyi model), the probabilistic method, the Lovasz Local Lemma.
Additive combinatorics: Szemeredi's theorem, the structure of sumsets.
Extremal combinatorics: Turan's theorem, the Kruskal–Katona theorem.
Matroid theory: the abstract structure underlying greedy algorithms and combinatorial optimization, touched upon in the graph theory series.

6 Takeaway

DP is bottom-up evaluation of a recurrence; Pascal's triangle is the prototype.
The knapsack DP corresponds to iterative polynomial multiplication in the generating function framework.
Convolution is the product of generating functions, and FFT accelerates it to $O (n lo g n)$ .
The topics of this series – binomial coefficients, inclusion–exclusion, generating functions, Catalan numbers, Burnside's lemma – are all deeply intertwined with DP.
Beyond this series lies a vast landscape: algebraic, probabilistic, additive, and extremal combinatorics.

This concludes the eight-article "Between the Lines" series on combinatorics. The act of counting – the most primitive of mathematical operations – turns out to be a gateway to set theory, algebra, analysis, and algorithms. If this series has conveyed some sense of that unity, it has served its purpose.

Combinatorics Mathematics Between the Lines

Folio Official

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

1 フォロワー·105 記事

Combinatorics meets dynamic programming: when counting becomes computation

1 DP is bottom-up evaluation of a recurrence

2 The knapsack problem and generating functions

3 Convolution and FFT

4 A retrospective of the series

5 Beyond this introduction

6 Takeaway

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry