組合せ論まとめ：定義・定理・アルゴリズムを一覧で整理【離散数学・競技プログラミング】

組合せ論の全体像を一記事で．数え上げの基礎からカタラン数・ラムゼー理論・代数的組合せ論まで，離散数学と競技プログラミングに必要な定義・定理・アルゴリズムを体系的にまとめた．各トピックの依存関係図付き．

2026年2月27日

1. はじめに：この記事の使い方

この記事は，学部レベルの組合せ論を一記事で俯瞰することを目的とする．各トピックについて，定義・主要定理・アルゴリズムを簡潔にまとめる．

使い方：

初学者 → セクション順に読み進め，組合せ論の全体像を掴むとよい
復習・試験対策 → 目次から必要なセクションへジャンプされたい
競プロの確認 → セクション14「定理・アルゴリズム一覧」で主要結果を一覧できる

以下の依存関係図は，各トピックがどのように繋がっているかを示す．

graph TD
    A["数え上げの基礎"] --> B["二項係数と二項定理"]
    A --> C["包除原理"]
    B --> C
    B --> D["母関数I（通常型）"]
    C --> D
    D --> E["母関数II（指数型）"]
    A --> F["漸化式と数え上げ"]
    D --> F
    B --> G["カタラン数と格子経路"]
    D --> G
    F --> G
    A --> H["鳩の巣・ラムゼー理論"]
    B --> I["バーンサイド・ポリア"]
    A --> J["組合せデザイン"]
    C --> K["半順序集合と束"]
    D --> L["代数的組合せ論"]
    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

注意 1.

本記事は「組合せ論の教科書」シリーズの各記事と連携している．各セクション末尾のリンクから，体系的な解説・証明に進むことができる．

2. 数え上げの基礎

定義 2 (和の法則・積の法則).

和の法則：互いに排反な事象

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

の少なくとも1つが起こる場合の数は

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

である．積の法則：独立な選択を順に行うとき，場合の数は各段階の場合の数の積である．

定義 3 (順列・組合せ).

n

個の異なるものから

r

個を選んで並べる順列（permutation）の数は

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

である．順序を考えない組合せ（combination）の数は

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

である．

定義 4 (重複順列・重複組合せ).

n

種類のものから重複を許して

r

個選んで並べる重複順列の数は

n^{r}

である．順序を考えない重複組合せの数は

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

である．

定理 5 (多項係数).

n

個のものを

k

群に分ける（各群のサイズが

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

，

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

）方法の数は

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

→ 詳しくは：

https://interconnectd.app/articles/NSCVeBcqW4bXMAfJ55ki

3. 二項係数と二項定理

定理 6 (二項定理).

任意の非負整数

n

と

x, y

に対して

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

定理 7 (二項係数の基本恒等式).

対称性： $(k n) = (n - k n)$
パスカルの三角形： $(k n) = (k - 1 n - 1) + (k n - 1)$
Vandermondeの畳み込み： $(r m + n) = \sum_{k = 0}^{r} (k m) (r - k n)$
吸収恒等式： $k (k n) = n (k - 1 n - 1)$
行の和： $\sum_{k = 0}^{n} (k n) = 2^{n}$

定理 8 (上限付き和の公式（ホッケースティック恒等式）).

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

定義 9 (一般化二項係数).

実数

α

と非負整数

k

に対して

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

と定める．これにより二項定理は冪級数に拡張される．

→ 詳しくは：

https://interconnectd.app/articles/k0GmsScwb3gKbS4E6WUM

4. 包除原理

定理 10 (包除原理).

有限集合

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} ∣

定理 11 (完全順列（攪乱順列）).

n

個の元の置換で不動点を持たないもの（完全順列，derangement）の数

D_{n}

は

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

n \to \infty

で

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

である．

定理 12 (オイラーのトーシェント関数).

包除原理を用いて

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

が導かれる．ここで積は

n

の相異なる素因数

p

を動く．

アルゴリズム：

高速ゼータ変換 / 高速メビウス変換：集合関数の包除を $O (n \cdot 2^{n})$ で計算

→ 詳しくは：

https://interconnectd.app/articles/zo5vkgUVJPFIAYBEf0S0

5. 母関数 I（通常型）

定義 13 (通常型母関数).

数列

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

の通常型母関数（OGF）は形式的冪級数

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

である．

定理 14 (基本的なOGF).

$\frac{1}{1 - x} = \sum_{n \geq 0} x^{n}$ （等比級数）
$\frac{1}{( 1 - x ) ^{k}} = \sum_{n \geq 0} (k - 1 n + k - 1) x^{n}$ （重複組合せ）
$\frac{1}{1 - x - x ^{2}} = \sum_{n \geq 0} F_{n} x^{n}$ （フィボナッチ数）

定理 15 (母関数の演算).

和： $A (x) + B (x)$ は数列の和 ${a_{n} + b_{n}}$ に対応
積（畳み込み）： $A (x) B (x)$ は ${\sum_{k = 0}^{n} a_{k} b_{n - k}}$ に対応
合成： $A (B (x))$ は組合せ的構成の合成に対応

注意 16.

競技プログラミングでは畳み込みをNTT（数論変換）で

O (n lo g n)

に高速化する．

→ 詳しくは：

https://interconnectd.app/articles/vD7qgQ3oh7Mwj9jSexz3

6. 母関数 II（指数型）

定義 17 (指数型母関数).

数列

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

の指数型母関数（EGF）は

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

である．ラベル付き構造の数え上げに適する．

定理 18 (基本的なEGF).

$e^{x} = \sum_{n \geq 0} \frac{x ^{n}}{n !}$ ： $a_{n} = 1$ （全ラベル付き集合）
$e^{e^{x} - 1} = \sum_{n \geq 0} B_{n} \frac{x ^{n}}{n !}$ ： $B_{n}$ はベル数（集合の分割数）
$- ln (1 - x) = \sum_{n \geq 1} (n - 1)! \frac{x ^{n}}{n !}$ ：連結置換（巡回置換）

定理 19 (指数公式).

ラベル付き構造

C

の EGF が

C (x)

のとき，

C

の集合（Set 構成）の EGF は

e^{C (x)}

である．

定理 20 (EGFの積とラベル付き合併).

\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 !}

．これはラベル集合を2つに分割して独立に構造を構成する操作に対応する．

→ 詳しくは：

https://interconnectd.app/articles/ve1PbtKUHIeo7Wr6txNz

7. 漸化式と数え上げ

定義 21 (線形漸化式).

定数係数

d

階線形漸化式とは

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

の形の関係式である．

定理 22 (特性方程式).

漸化式

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

の特性方程式は

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

である．根

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

がすべて異なるとき，一般項は

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

と書ける．

定理 23 (母関数による解法).

d

階線形漸化式の OGF は有理関数

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

となり，部分分数分解から一般項が求まる．

例 24 (フィボナッチ数).

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

，

F_{0} = 0

，

F_{1} = 1

の一般項は

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

（

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

，

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

）である．

アルゴリズム：

行列累乗： $d$ 階線形漸化式の第 $n$ 項を $O (d^{3} lo g n)$ で計算
Kitamasa法：多項式演算で $O (d^{2} lo g n)$ または $O (d lo g d lo g n)$ （FFT使用時）

→ 詳しくは：

https://interconnectd.app/articles/Y4ikULaijwNmUXApIvfo

8. カタラン数と格子経路

定義 25 (カタラン数).

カタラン数

C_{n}

は以下で定義される：

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

最初のいくつかの値は

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

である．

定理 26 (カタラン数の漸化式).

C_{0} = 1

，

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

．OGF は

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

である．

定理 27 (カタラン数の組合せ的解釈).

C_{n}

は以下のいずれの数とも等しい：

$(0, 0)$ から $(2 n, 0)$ への山道（Dyck path）の数
$n + 1$ 個の葉をもつ完全二分木の数
$n$ 個の因子の括弧付けの数
$n + 2$ 角形の三角形分割の数
$n$ 個の要素に対する非交差分割の数

定理 28 (反射原理（鏡映法）).

(0, 0)

から

(m, n)

への格子経路（右・上移動）のうち，対角線

y = x

を超えないものの数は，全経路数

(m m + n)

から「悪い経路」の数を反射で数えることで得られる．

定理 29 (バロット問題).

候補者

A

が

a

票，

B

が

b

票を得て

A

が勝った（

a > b

）とき，開票の全過程で

A

が常にリードしている確率は

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

である．

→ 詳しくは：

https://interconnectd.app/articles/uW9bGLpvRDBPkZf8kLZI

9. 鳩の巣原理とラムゼー理論

定理 30 (鳩の巣原理).

n + 1

個以上のものを

n

個の箱に入れると，少なくとも1つの箱には2個以上入る．一般化：

kn + 1

個のものを

n

個の箱に入れると，少なくとも1つの箱には

k + 1

個以上入る．

定理 31 (Erdős–Szekeresの定理).

長さ

mn + 1

以上の実数列は，長さ

m + 1

の単調増加部分列または長さ

n + 1

の単調減少部分列を含む．

定義 32 (ラムゼー数).

ラムゼー数

R (s, t)

は，

K_{n}

の辺を赤・青に2色彩色したとき，赤の

K_{s}

または青の

K_{t}

が必ず出現する最小の

n

である．

定理 33 (ラムゼーの定理).

任意の正整数

s, t \geq 2

に対して

R (s, t)

は有限である．上界として

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

が知られる．特に

R (3, 3) = 6

である．

定理 34 (ラムゼー数の下界（Erdős）).

確率論的論法により

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

（

k \geq 3

）が示される．

注意 35.

ラムゼー数の正確な値はごく少数しか知られていない．例えば

R (5, 5)

は

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

の範囲しか分かっていない．

→ 詳しくは：

https://interconnectd.app/articles/XsiI9saR8h0dH64M1ujb

10. バーンサイドの補題とポリアの数え上げ定理

定義 36 (群作用と軌道).

群

G

が集合

X

に作用するとは，写像

G \times X \to X

（

(g, x) \mapsto g \cdot x

）が

e \cdot x = x

と

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

を満たすことである．

x

の軌道は

{g \cdot x ∣ g \in G}

である．

定義 37 (不動点集合).

g \in G

に対して

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

を

g

の不動点集合という．

定理 38 (バーンサイドの補題（Cauchy–Frobenius）).

有限群

G

が有限集合

X

に作用するとき，軌道の数

∣ X / G ∣

は

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

定義 39 (巡回指標).

置換群

G

が

{1, \dots, n}

に作用するとき，

g \in G

の巡回型が

j_{1}

個の1-サイクル，

j_{2}

個の2-サイクル，…を持つとする．巡回指標は

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)}

定理 40 (ポリアの数え上げ定理).

k

色で彩色するとき，

G

の作用で同値な彩色の数は

Z (G)

で

s_{i} = k

（

\forall i

）と代入した値に等しい．さらに重み付き版では

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

と代入すればパターンの母関数が得られる．

→ 詳しくは：

https://interconnectd.app/articles/Jn8paejHgnjTYntp3GZY

11. 組合せデザインとラテン方陣

定義 41 (ラテン方陣).

n \times n

の配列で，各行・各列に

{1, 2, \dots, n}

がちょうど1回ずつ現れるものを

n

次のラテン方陣（Latin square）という．

定義 42 (直交ラテン方陣（MOLS）).

2つの

n

次ラテン方陣

L_{1}, L_{2}

が直交するとは，

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

の

n^{2}

個の組がすべて異なることをいう．互いに直交する

k

個のラテン方陣の組を

k

-MOLS という．

定理 43 (MOLSの上界).

n

次の MOLS の最大個数は

n - 1

以下である．

n

が素数冪のとき最大値

n - 1

が達成される．

定義 44 (

t

(v, k, λ)

デザイン).

v

元集合

V

の

k

元部分集合（ブロック）の族

B

で，

V

の任意の

t

元部分集合がちょうど

λ

個のブロックに含まれるものを

t

(v, k, λ)

デザインという．

定理 45 (Fisherの不等式).

2

(v, k, λ)

デザインにおいて，ブロック数

b

は

b \geq v

を満たす．

定義 46 (Steiner三重系).

2

(v, 3, 1)

デザインを Steiner三重系

S (2, 3, v)

という．これが存在する必要十分条件は

v \equiv 1

または

3 (mod 6)

である．

→ 詳しくは：

https://interconnectd.app/articles/Th2k9zGY7e1iIdljsC8C

12. 半順序集合と束

定義 47 (半順序集合（poset）).

集合

P

と二項関係

\leq

の組

(P, \leq)

が半順序集合（poset）であるとは，

\leq

が反射律・反対称律・推移律を満たすことをいう．

定義 48 (鎖と反鎖).

すべての要素が互いに比較可能な部分集合を鎖（chain），互いに比較不能な部分集合を反鎖（antichain）という．

定理 49 (Dilworthの定理).

有限半順序集合において，反鎖の最大サイズ

=

鎖への最小分割数である．

定理 50 (Mirsky の定理).

有限半順序集合において，鎖の最大長

=

反鎖への最小分割数である．

定義 51 (束（lattice）).

半順序集合

(L, \leq)

で，任意の2元

a, b

に対して上限

a \lor b

（結び）と下限

a \land b

（交わり）が存在するものを束（lattice）という．

定義 52 (メビウス関数).

有限半順序集合

(P, \leq)

上のメビウス関数

μ : P \times P \to Z

は，

μ (x, x) = 1

，

x < y

のとき

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

で帰納的に定まる．

定理 53 (メビウスの反転公式).

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

ならば

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

．包除原理はべき集合束上のメビウス反転の特殊ケースである．

→ 詳しくは：

https://interconnectd.app/articles/tc6hpcXOondSu5A2Yt8T

13. 組合せ論と代数

定義 54 (Young図形とYoung盤).

非負整数の単調非増加列

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

（

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

）を

n

の分割（partition）という．対応する箱の配置を Young図形と呼び，箱に数を入れたものをYoung盤（tableau）という．

定義 55 (標準Young盤（SYT）).

Young図形

λ

の各箱に

1, 2, \dots, n

を重複なく入れ，各行・各列で狭義単調増加となるものを標準Young盤という．

定理 56 (フック長の公式).

形

λ

の標準Young盤の総数

f^{λ}

は

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

ここで

h (u)

は箱

u

のフック長（

u

と同じ行の右側

+

同じ列の下側

+ 1

）である．

定理 57 (RSK対応).

{1, \dots, n}

の置換と

(P, Q)

（同じ形の標準Young盤の組）との間にRobinson–Schensted–Knuth対応と呼ばれる全単射が存在する．この対応より

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

が従う．

定義 58 (対称多項式).

変数の置換で不変な多項式を対称多項式という．基本対称多項式

e_{k}

と完全斉次対称多項式

h_{k}

がその基本的な生成系をなす．

定理 59 (Schur多項式).

Schur多項式

s_{λ}

は半標準Young盤によって定義され，対称多項式環の基底をなす．

s_{λ}

の積の展開係数（Littlewood–Richardson係数）は表現論や交差理論と深く関わる．

→ 詳しくは：

https://interconnectd.app/articles/PVQTKpZTRX23VdoC0lnE

14. 定理・アルゴリズム一覧

離散数学と競技プログラミングで登場する主要な定理とアルゴリズムの一行サマリーである．

数え上げの基本定理：

二項定理： $(x + y)^{n} = \sum (k n) x^{k} y^{n - k}$
Vandermondeの畳み込み： $(r m + n) = \sum_{k} (k m) (r - k n)$
包除原理： $∣ ⋃ A_{i} ∣ = \sum ∣ A_{i} ∣ - \sum ∣ A_{i} \cap A_{j} ∣ + \dots$
完全順列： $D_{n} = n! \sum_{k = 0}^{n} (- 1)^{k} / k!$
カタラン数： $C_{n} = \frac{1}{n + 1} (n 2 n)$
指数公式：Set構成の EGF $= e^{C (x)}$
フック長の公式： $f^{λ} = n! / \prod h (u)$

存在定理・構造定理：

鳩の巣原理： $n + 1$ 個 → $n$ 個の箱に少なくとも1つは2個以上
Erdős–Szekeresの定理：長さ $mn + 1$ の列に長さ $m + 1$ の増加列 or 長さ $n + 1$ の減少列
ラムゼーの定理： $R (s, t)$ は有限， $R (s, t) \leq (s - 1 s + t - 2)$
Dilworthの定理：最大反鎖サイズ $=$ 最小鎖分割数
Fisherの不等式： $2$ -デザインのブロック数 $b \geq v$
RSK対応：置換 $\leftrightarrow$ 標準Young盤の組， $\sum (f^{λ})^{2} = n!$

群作用と対称性：

バーンサイドの補題：軌道数 $= \frac{1}{∣ G ∣} \sum ∣ Fix (g) ∣$
ポリアの数え上げ定理：巡回指標で $s_{i} = k$ と代入
メビウスの反転公式：包除原理の一般化

主要アルゴリズム：

NTT（数論変換，畳み込み）： $O (n lo g n)$
高速ゼータ変換 / メビウス変換： $O (n \cdot 2^{n})$
行列累乗（線形漸化式）： $O (d^{3} lo g n)$
Kitamasa法： $O (d^{2} lo g n)$ or $O (d lo g d lo g n)$
二項係数の前処理（ $(k n) mod p$ ）： $O (n)$ 前処理， $O (1)$ クエリ
LIS（最長増加部分列）： $O (n lo g n)$
RSKアルゴリズム： $O (n n)$

組合せ論離散数学まとめ定理一覧アルゴリズム競技プログラミング

Folio公式

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

0 followers·105 articles

組合せ論まとめ：定義・定理・アルゴリズムを一覧で整理【離散数学・競技プログラミング】

1. はじめに：この記事の使い方

2. 数え上げの基礎

3. 二項係数と二項定理

4. 包除原理

5. 母関数 I（通常型）

6. 母関数 II（指数型）

7. 漸化式と数え上げ

8. カタラン数と格子経路

9. 鳩の巣原理とラムゼー理論

10. バーンサイドの補題とポリアの数え上げ定理

11. 組合せデザインとラテン方陣

12. 半順序集合と束

13. 組合せ論と代数

14. 定理・アルゴリズム一覧

Share your expertise with the world

More from Folio公式

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

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

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

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