数え上げとDPの深い関係 ― 組合せ論が競プロの「解法」になるとき

DP（動的計画法）は漸化式のボトムアップ計算であり，母関数はDPの解析解です．ナップサック問題と母関数の対応，畳み込みとFFTの関係を解説し，シリーズ全体を振り返ります．

Folio公式

2026年2月27日

このシリーズの最終回として，組合せ論と競プロの最重要テクニックであるDP（動的計画法）の関係を掘り下げ，7回の記事を振り返ります．DP と組合せ論は表裏一体であり，その関係を理解することで，問題へのアプローチが格段に広がります．

1 DPは漸化式のボトムアップ計算

注意 1.

DP の本質は漸化式を小さい方から順に計算することです．「DP を書く」とは「漸化式を立てて，添字の小さい順に値を埋めていく」ことに他なりません．

例 2 (パスカルの三角形＝DPテーブル).

第2回で見たパスカルの恒等式

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

は漸化式です．これをテーブルに記入していくのはまさに DP です．

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

初期条件

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

から出発して，

n = 0, 1, 2, \dots

の順に埋めます．これがパスカルの三角形の構成です．

注意 3.

逆に言えば，二項係数の公式 $(r n) = \frac{n !}{r ! ( n - r )!}$ はDPの「閉じた形」です．漸化式を解析的に解いた結果が公式であり，公式がなければ DP で数値的に計算するというのが，組合せ論と計算の関係です．

2 ナップサック問題と母関数

例 4 (0-1 ナップサック問題).

n

個の品物（重さ

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

，価値

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

）から容量

W

のナップサックに入る組合せを選ぶ問題です．数え上げ版（条件を満たす組合せの数）を考えましょう．

DP の遷移は

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

です．

dp [i] [j]

は「

i

番目までの品物を使って重さちょうど

j

にする方法の数」です．

注意 5.

この DP を母関数の言葉で書き直すと，各品物

i

に対応する多項式は

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

であり，答えの母関数は

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

の

x^{W}

の係数です．DP テーブルの逐次更新は，この積を1つずつ掛けていく操作に対応します．

定理 6 (DP と母関数の対応).

DP の漸化式は母関数の積（畳み込み）に対応します．具体的には：

DP テーブルの各行は多項式の係数列
DP の遷移（前の行の値を使って次の行を計算）は多項式の掛け算
DP テーブル全体は母関数の逐次展開

3 畳み込みと FFT

第4回で見たように，母関数の積は畳み込みに対応します．

定義 7 (畳み込み).

数列

{a_{n}}

と

{b_{n}}

の畳み込み

{c_{n}}

は

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

です．

素朴に計算すると $O (n^{2})$ ですが，FFT（高速フーリエ変換）を使えば $O (n lo g n)$ で計算できます．

注意 8 (FFT の直感).

FFT の核心アイデアは「多項式の積は，点値表現では各点で値を掛けるだけ」ということです：

係数表現 → 点値表現（ $O (n lo g n)$ ，FFT）
点値表現で各点の値を掛け算（ $O (n)$ ）
点値表現 → 係数表現（ $O (n lo g n)$ ，逆FFT）

全体で

O (n lo g n)

です．

例 9 (AtCoder での畳み込み).

AtCoder では NTT（数論変換：mod

p

での FFT）を使った畳み込みが頻出します．例えば「

N

個のサイコロを振って和が

S

になる確率」は，各サイコロの確率分布の畳み込みで求められ，NTT で高速化できます．

4 シリーズ全体の振り返り

8回にわたるシリーズを俯瞰すると，組合せ論の各トピックが有機的につながっていることが見えてきます．

注意 10 (各記事のつながり).

数え上げの基本（加法・乗法原理）→ すべての出発点．集合の濃度という視点
二項係数（パスカルの恒等式・二項定理）→ 最も基本的な数え上げの道具．DP テーブル＝パスカルの三角形
包除原理（足して引いて）→ 「全体から引く」数え上げ技法．二項定理 $(1 - 1)^{m} = 0$ が本質
母関数（数列→関数）→ 漸化式を代数方程式に変換．DP の「解析版」
カタラン数（反射原理・全単射）→ 母関数の二次方程式から導出．格子経路と括弧列の全単射
鳩の巣原理（存在証明）→ 構成的でない推論の力．ラムゼー理論への入口
バーンサイド（対称性）→ 群作用による数え上げ．固定点数の平均
DP と組合せ論（本記事）→ 漸化式＝DP，母関数＝解析解，畳み込み＝FFT

5 組合せ論の先にある世界

注意 11.

この入門シリーズでは扱いきれなかったトピックが数多くあります：

代数的組合せ論：群の表現論と対称関数，ヤング図形と Robinson-Schensted 対応
確率的組合せ論：ランダムグラフ（Erdos-Renyi モデル），確率的存在証明（Lovasz Local Lemma）
加法的組合せ論：Szemeredi の定理，和集合の構造
極値組合せ論：Turan の定理，Kruskal-Katona の定理
マトロイド理論：グラフ理論シリーズの第4回でも触れた構造が，組合せ最適化の基盤を成します

6 まとめ

DP は漸化式のボトムアップ計算であり，パスカルの三角形はその原型です
ナップサック問題の DP は母関数の逐次的な掛け算に対応します
畳み込みは母関数の積であり，FFT で $O (n lo g n)$ に高速化できます
組合せ論の各トピック（二項係数・包除原理・母関数・カタラン数・バーンサイド）は DP と深くつながっています
組合せ論の先には代数的組合せ論，確率的組合せ論，極値組合せ論など広大な世界が広がっています

8回にわたる組合せ論「教科書の行間」シリーズはこれで完結です．「数える」という最も原始的な数学的行為が，集合論・代数・解析・アルゴリズムのすべてに通じていることを感じていただけたなら幸いです．

組合せ論離散数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 フォロワー·105 記事

数え上げとDPの深い関係 ― 組合せ論が競プロの「解法」になるとき

1 DPは漸化式のボトムアップ計算

2 ナップサック問題と母関数

3 畳み込みと FFT

4 シリーズ全体の振り返り

5 組合せ論の先にある世界

6 まとめ

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

Folio公式の他の記事

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ