組合せ論
概要
組合せ論（combinatorics）とは、有限集合の上に関係や部分集合の族を与えた組合せ構造（集合族、グラフ、順列、分割、半順序集合、マトロイドなど）について、条件を満たすものの個数、存在、大きさの最大・最小、必ず現れる部分構造を調べる数学の分野である。数え上げ組合せ論、グラフ理論、極値組合せ論、Ramsey 理論、確率的方法、代数的組合せ論などの小分野からなり、全単射、二重数え上げ、鳩の巣原理、母関数、線形代数、確率が主な道具である。代表例として、会員数が奇数で、どの 2 つも共通の会員数が偶数であるような $n$ 人の町のクラブは高々 $n$ 個しか作れないこと（Oddtown の定理）が、2 元体の上のベクトルの一次独立性から証明できる。
組合せ論（combinatorics）は、有限個のものの並べ方・選び方・つなぎ方を研究する数学の分野である。$n$ 人から委員を何通り選べるか、どの 2 人も知り合いか他人かのどちらかである 6 人の中に、互いに知り合いの 3 人か互いに他人の 3 人が必ずいるか、地図を 4 色で塗り分けられるか、といった問いがこの分野に属する。対象は有限であり、原理的にはすべての場合を調べれば答えが出るが、場合の数はすぐに膨大になるので、調べ尽くさずに答えを出す構造と方法を見つけることが組合せ論の中心になる。
この記事では、組合せ論の対象と主な問いを定義とともに述べ、小分野と代表的な定理を、それを扱う記事とともに一覧にする。続いて、線形代数を使う組合せ論の典型例として Oddtown の定理を完全に証明し、仮定を 1 つずつ外した反例を示す。最後に、学ぶ順に記事を並べた道筋を示す。
定義
組合せ論の対象は、有限集合の上に関係や部分集合の族などを与えた構造である。代表的なものを挙げる。
- 部分集合と集合族：有限集合 $X$ の部分集合を集めた族 $\mathcal{F}\subset2^X$（集合族、ハイパーグラフ）。
- グラフ：頂点の集合と、2 頂点を結ぶ辺の集合（グラフ）。
- 順列と置換：有限集合の元の並べ方、自分自身への全単射（順列、対称群）。
- 分割：集合を空でない部分に分けること、自然数を自然数の和に分けること（分割数）。
- 半順序集合とマトロイド：大小関係や独立性を公理化した構造（半順序集合、マトロイド）。
有限集合 $X$ と、$X$ の上の有限個の関係（直積 $X^r$ の部分集合）および $X$ の部分集合の有限個の族の組を、$X$ の上の 組合せ構造 という。組合せ構造について、与えられた条件を満たすものの個数（数え上げ）、存在、大きさの最大・最小（極値）、全体の形（構造）を調べる数学の分野を 組合せ論（combinatorics）という。
グラフ $G=(V,E)$ は、頂点集合 $V$ の 2 元部分集合の族 $E$ を与えた組合せ構造である。集合族 $\mathcal{F}$ はそれ自身が組合せ構造である。組合せ論の考え方は、無限集合（無限グラフや無限の Ramsey 理論）にも広がる。
離散数学 は、組合せ論に加えて論理と計算、符号と暗号、初等整数論なども含む、より広い分野の名前である。「組合せ」の語は、$n$ 元集合から $k$ 個を選ぶ選び方（その個数は 二項係数 $\binom nk$）の意味でも使われる。
組合せ論の主な問い
- 数える。 条件を満たす構造の個数を求める。$n$ 元集合の部分集合は $2^n$ 個、$n$ 頂点のラベル付きの木は $n^{n-2}$ 個ある（Cayleyの公式）。閉じた式、漸化式、母関数、漸近評価などで答える（数え上げ組合せ論）。
- 存在を示す。 条件を満たす構造があるかを決める。二部グラフが一方の側を覆うマッチングをもつための条件（Hallの結婚定理）や、平面グラフが 4 色で塗れること（四色定理）がこの型である。構造を作らずに、数え上げや確率で存在を示すこともある（確率的方法）。
- 最大・最小を求める。 条件を満たす構造がどこまで大きくなれるかを問う。三角形を含まない $n$ 頂点のグラフの辺は $\lfloor n^2/4\rfloor$ 本以下である（Mantelの定理、Turánの定理）。下の Oddtown の定理もこの型である。
- 必ず現れる構造を見つける。 十分大きな構造には、どう分けても規則的な部分が現れる（Ramseyの定理、van der Waerdenの定理、Ramsey理論）。
頂点 $1,2,3,4$ の上のグラフ（頂点は区別する）を例にとる。
- 数える：2 頂点の組は $\binom42=6$ 個あり、各組に辺を引くか引かないかを選ぶので、グラフは $2^6=64$ 個ある。
- 存在：三角形を含まず辺が 4 本のグラフはある。閉路 $1,2,3,4$ がその例である。
- 最大：三角形を含まないグラフの辺は $\lfloor4^2/4\rfloor=4$ 本以下である（Mantelの定理）。直接にも、5 本以上の辺をもつグラフは三角形を含むことが確かめられる（下の確認）。
- 必ず現れる構造：頂点が 6 個の完全グラフの辺を 2 色で塗ると、必ず単色の三角形ができるが、5 個では必ずしもできない（Ramsey数 R(3,3)=6）。
3 の確認：辺が 5 本のグラフは $K_4$ から 1 辺を除いたものである。$K_4$ の 4 つの三角形のうち、除いた辺を含むものは 2 つなので、残る 2 つの三角形はこのグラフに含まれる。辺が 6 本なら $K_4$ そのものである。
小分野
| 小分野 | 主な対象と問い | 記事の例 |
|---|---|---|
| 数え上げ組合せ論 | 有限集合の個数、母関数 | 数え上げ組合せ論, 包含と除去の原理, Catalan数, 分割数 |
| グラフ理論 | 連結性・彩色・平面性・マッチング | グラフ, 彩色数, 平面グラフ, マッチング(グラフ理論) |
| 極値組合せ論 | 条件の下での最大・最小 | 極値グラフ理論, Turánの定理, Dilworthの定理 |
| Ramsey 理論 | 必ず現れる規則的な部分 | Ramsey理論, Ramseyの定理, Schurの定理(和のない集合) |
| 確率的方法 | 確率による存在証明 | 確率的方法, 期待値の線形性と数え上げ |
| 代数的組合せ論 | 対称性・表現・多項式 | Young図形, Schur多項式, Pólyaの数え上げ定理, 行列木定理 |
| マトロイドと対数凹性 | 独立性の公理化、係数の不等式 | マトロイド, 対数凹性, Heron–Rota–Welsh予想, Lorentz多項式 |
| 組合せデザイン | 均整のとれた配置 | Latin方陣 |
| 組合せ論的ゲーム理論 | 有限のゲームの必勝法 | 組合せ論的ゲーム理論 |
代表的な定理
| 定理 | 主張の要点 | 記事 |
|---|---|---|
| 鳩の巣原理 | $n+1$ 個のものを $n$ 個の箱に入れると、2 個以上入る箱がある | 鳩の巣原理 |
| 包除原理 | 和集合の元の個数を共通部分の個数の交代和で表す | 包含と除去の原理 |
| Hall の結婚定理 | 二部グラフの一方の側を覆うマッチングがあるための近傍の個数の条件 | Hallの結婚定理 |
| Dilworth の定理 | 有限半順序集合の反鎖の最大の大きさは、鎖への分割の最小の個数に等しい | Dilworthの定理 |
| Ramsey の定理 | 十分大きい完全グラフの辺を 2 色で塗ると、単色の大きな完全部分グラフがある | Ramseyの定理 |
| Turán の定理 | $K_{r+1}$ を含まない $n$ 頂点のグラフの辺の最大数 | Turánの定理 |
| Cayley の公式 | $n$ 頂点のラベル付きの木は $n^{n-2}$ 個 | Cayleyの公式 |
| 四色定理 | 平面グラフは 4 色で頂点彩色できる | 四色定理 |
| Adiprasito–Huh–Katz の定理 | マトロイドの特性多項式の係数は対数凹 | Heron–Rota–Welsh予想 |
証明の方法
組合せ論では、同じ定理がまったく違う方法で証明されることが多い。よく使われる方法を挙げる。
- 全単射：2 つの集合の間に全単射を作り、個数が等しいことを示す（数え上げ組合せ論 の Catalan 数の閉じた式）。
- 二重数え上げ：同じものを 2 通りに数える（期待値の線形性と数え上げ の命題「二重数え上げ」）。
- 鳩の巣原理と極値原理：最大・最小のものに注目して矛盾を導く（鳩の巣原理、Mantelの定理）。
- 母関数：数列を冪級数の係数とみて代数・解析で扱う（母関数）。
- 線形代数の方法：組合せ構造をベクトルに置き換え、一次独立なベクトルの個数が次元以下であることで上界を得る（下の Oddtown の定理）。
- 確率的方法：ランダムな構造の期待値や確率を計算して存在を示す（確率的方法）。
- 代数と幾何の方法：多項式やコホモロジー環の性質から不等式を導く（Heron–Rota–Welsh予想、Lorentz多項式）。
代表例：Oddtown の定理
ある町の $n$ 人の住民がクラブを作る。どのクラブの会員数も奇数で、どの 2 つのクラブも共通の会員の数が偶数（$0$ でもよい）であるとき、クラブはいくつまで作れるか。これは集合族の大きさの最大を問う極値の問題である。答えは $n$ であり、証明は組合せ構造を 2 元体の上のベクトルに置き換えて、一次独立なベクトルの個数を数える。
$X=\{1,\dots,n\}$ とする。2 元体 $\mathbb{F}_2=\{0,1\}$（$2$ を法とする足し算と掛け算。有限体）の上の $n$ 次元の数ベクトル空間 $\mathbb{F}_2^n$ を考える。部分集合 $S\subset X$ の 特性ベクトル を、第 $i$ 成分が $i\in S$ なら $1$、そうでなければ $0$ のベクトル $\chi_S\in\mathbb{F}_2^n$ とする。$x,y\in\mathbb{F}_2^n$ について $x\cdot y:=\sum_ix_iy_i\in\mathbb{F}_2$ とおくと、$\chi_S\cdot\chi_T$ は $\lvert S\cap T\rvert$ を $2$ で割った余りである。
$\mathcal{F}=\{C_1,\dots,C_m\}$ を $n$ 元集合 $X$ の相異なる部分集合の族とし、次の 2 条件を満たすとする。
(a) 各 $\lvert C_i\rvert$ は奇数である。
(b) $i\ne j$ なら $\lvert C_i\cap C_j\rvert$ は偶数である。
このとき $m\le n$ である。
特性ベクトル $\chi_{C_1},\dots,\chi_{C_m}\in\mathbb{F}_2^n$ が $\mathbb{F}_2$ 上一次独立であることを示す。$\lambda_1,\dots,\lambda_m\in\mathbb{F}_2$ が $\sum_i\lambda_i\chi_{C_i}=0$ をみたすとする。両辺と $\chi_{C_j}$ の $\cdot$ をとると、$\cdot$ は各変数について線形なので
$$
0=\sum_{i=1}^m\lambda_i\,(\chi_{C_i}\cdot\chi_{C_j})=\lambda_j
$$
となる。実際、(a) により $\chi_{C_j}\cdot\chi_{C_j}=\lvert C_j\rvert\bmod2=1$ であり、(b) により $i\ne j$ なら $\chi_{C_i}\cdot\chi_{C_j}=0$ である。よってすべての $\lambda_j$ が $0$ で、$\chi_{C_1},\dots,\chi_{C_m}$ は一次独立である。$\mathbb{F}_2^n$ は $n$ 次元なので、基底と次元 の命題「有限次元空間における独立系と生成系」の 1 により $m\le n$ である。$\square$
この定理と証明は Sta13 §12.2 の Theorem 12.2（pp. 233–234）にあり、そこでは定理が Berlekamp によることが述べられている（同 p. 250）。同所は、線形代数を使わない証明は易しくないと注意している（p. 234）。
1 元集合の族 $\{1\},\{2\},\dots,\{n\}$ は、各会員数が $1$、共通部分が空で (a)(b) をみたし、$m=n$ である。もう少し大きいクラブの例として、$n=4$ で $\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}$ をとると、会員数はどれも $3$、2 つの共通部分の大きさはどれも $2$ で、やはり $m=4=n$ に達する。
会員数の条件を「偶数」に替えると、答えは大きく変わる。
$\mathcal{F}$ を $n$ 元集合 $X$ の相異なる部分集合の族とし、各 $C\in\mathcal{F}$ の $\lvert C\rvert$ と、相異なる $C,D\in\mathcal{F}$ の $\lvert C\cap D\rvert$ がすべて偶数であるとする。このとき $\lvert\mathcal{F}\rvert\le2^{\lfloor n/2\rfloor}$ であり、この上界に達する族がある。
$W\subset\mathbb{F}_2^n$ を $\chi_C$（$C\in\mathcal{F}$）が張る部分空間とする。仮定により生成元どうしの $\cdot$ はすべて $0$ で（自分自身との値も $\lvert C\rvert\bmod2=0$）、$\cdot$ は各変数について線形なので、すべての $u,v\in W$ で $u\cdot v=0$ である。$k:=\dim W$ とし、$W$ の基底 $w_1,\dots,w_k$ を行とする $k\times n$ 行列を $R$ とする。$R$ の行は一次独立なので、行列の階数 の定理「列階数と行階数は等しい」により $\operatorname{rank}R=k$ である。線形代数学 の定理「次元定理」により、$R$ の核 $W^{\perp}:=\{x\in\mathbb{F}_2^n\mid w_i\cdot x=0\ (1\le i\le k)\}$ の次元は $n-k$ である。$W\subset W^{\perp}$ なので $k\le n-k$、すなわち $k\le\lfloor n/2\rfloor$ である。相異なる $C$ の特性ベクトルは相異なる $W$ の元なので、$\lvert\mathcal{F}\rvert\le\lvert W\rvert=2^k\le2^{\lfloor n/2\rfloor}$ である。
上界に達する族は、$h:=\lfloor n/2\rfloor$ とし、住民のうち $2h$ 人を $\{1,2\},\{3,4\},\dots,\{2h-1,2h\}$ の $h$ 組に分けて、組の和集合を全部（空集合を含めて $2^h$ 個）とればよい。各和集合の大きさは偶数で、2 つの和集合の共通部分は共通の組の和集合なので、その大きさも偶数である。$\square$
2 つの定理を比べると、各クラブの会員数を奇数にするか偶数にするかの違いで、最大の個数が $n$ と $2^{\lfloor n/2\rfloor}$ に分かれる。奇数の条件は「特性ベクトルの間の $\cdot$ の表が単位行列になる」ことを意味し、ベクトルを一次独立にする。偶数の条件は「表が零行列になる」ことを意味し、ベクトルの張る空間 $W$ が $W\subset W^{\perp}$ をみたすことになって、次元が半分以下に抑えられる。
どちらの証明も、条件の偶奇だけを見て $\mathbb{F}_2$ の上の線形代数に移し、次元で上界を得ている。部分集合の族を接続行列やベクトルに置き換えて次元や階数で上界を得る方法は、実数の上でも使われる。どの 2 つの共通部分もちょうど $\lambda$ 個（$1\le\lambda< b$）であるような $b$ 元集合の相異なる部分集合は高々 $b$ 個しかないという非一様な Fisher の不等式（Bose による一般化）がその例である（Sta13 §12.4 の Theorem 12.4、pp. 236–238。この記事では証明しない）。
反例：仮定を外すと崩れること
thm-comb-oddtown の仮定 (a)(b) を 1 つずつ外すと、族の大きさは $n$ を超え、$n$ について指数的に大きくなりうる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| (a) 会員数が奇数 | $n=2h$ のとき、住民を $\{1,2\},\{3,4\},\dots,\{2h-1,2h\}$ の $h$ 組に分け、組の和集合を全部とる（空集合を含めて $2^h$ 個） | 会員数も共通部分の大きさも偶数で (b) をみたすが、$2^h$ 個のクラブがあり、$h\ge3$ で $2^h>n$ となる |
| (b) 共通部分が偶数 | 会員数が奇数の部分集合をすべてとる（$2^{n-1}$ 個） | (a) をみたすが、$n\ge3$ で $2^{n-1}>n$ となる |
1 行目の族は thm-comb-eventown で上界に達する族であり、(b) をみたすことはそこで確かめた。2 行目の $2^{n-1}$ は、$X$ の部分集合のうち元の個数が奇数のものの個数である（二項定理 で $(1+1)^n$ と $(1-1)^n$ の差の半分）。どちらの反例でも、特性ベクトルは一次独立でなくなっている。たとえば 1 行目で $\chi_{\{1,2\}}\cdot\chi_{\{1,2\}}=0$ なので、prf-comb-oddtown の計算で $\lambda_j$ を取り出せない。
ほかの分野とのつながり
組合せ論は、ほかの分野の道具を使い、またほかの分野に問題と道具を提供する。
- 整数論：整数の集合の中の規則的な部分を問う問題は、Ramsey 理論の形をとる。上密度が正である正の整数の集合は、任意の長さの等差数列を含む（Szemerédiの定理）。この定理は、$\{1,\dots,N\}$ の部分集合で $k$ 項の等差数列を含まないものの大きさについての有限の主張と同値であり（Szemerédiの定理 の命題「2つの形の同値性」）、組合せ論の問題として扱われる。
- 代数：対称群の表現や対称多項式は、Young 図形と盤の数え上げで記述される（Young図形、Schur多項式）。
- 幾何と位相：曲面に描いたグラフの頂点・辺・面を数えると曲面の Euler 標数がわかる（位相的グラフ理論、Euler標数）。逆に、マトロイドの不等式は代数幾何の Hodge 理論の考え方で証明された（Heron–Rota–Welsh予想）。
- 計算と情報：有限個の候補から最良のものを効率よく選ぶ問題（組合せ最適化）や、誤りを訂正できる符号の構成（誤り訂正符号）は、組合せ構造の問題である。
学ぶ順の道筋
組合せ論の基礎は、次の順に記事をたどると学べる。
- 数え上げの基礎：有限集合 → 数え上げ組合せ論 → 二項係数 → 包含と除去の原理 → 鳩の巣原理 → 母関数。
- グラフ：グラフ → 連結グラフ → 木(グラフ) → 閉路 → Euler閉路 → 彩色数 → 平面グラフ。連結性の構造は 連結度(グラフ) と ブロック(グラフ)。
- 極値と Ramsey：Mantelの定理 → Turánの定理 → Ramseyの定理 → 確率的方法。
- 順序と独立性：半順序集合 → Dilworthの定理 → マトロイド → 対数凹性 → Heron–Rota–Welsh予想 → Lorentz多項式。
- 代数的組合せ論：対称群 → Young図形 → Schur多項式、および 行列木定理。
1 と 2 は互いに独立に読め、3 以降は 1・2 の両方を使う。代表例の Oddtown の定理は、一次独立と次元という線形代数の基本（基底と次元）だけで証明できる。
歴史
組合せ論の問いは古くからあり、二項係数の表や順列の数え方は多くの文化で知られていた。Euler による Königsberg の橋の問題（1736 年）はグラフ理論の出発点とされ（一筆書きとグラフ）、Euler は自然数の分割も母関数で調べた。20 世紀には Ramsey の定理、Hall の結婚定理、Erdős による確率的方法が現れ、個々の問題を解く技術から体系的な分野へ発展した。21 世紀には、代数幾何の Hodge 理論の考え方を移植して対数凹性の予想が解かれるなど、他の分野との結びつきが深まっている（Heron–Rota–Welsh予想）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
