代数的組合せ論(algebraic combinatorics)とは、有限の組合せ構造についての問題を線形代数・群の作用・表現・対称関数などの代数の道具で解き、逆に代数に現れる量を組合せの対象の個数として記述する分野である。主な主題は、行列による歩道や全域木の数え上げ、群の作用による数え上げ、Young 図形と盤、対称関数、半順序、アソシエーションスキームである。たとえば Young 図形の上で箱を 1 個加える作用素 $U$ と除く作用素 $D$ は $DU-UD=I$ を満たし、この関係だけから標準盤の個数の平方和が $n!$ に等しいことが従う。
代数的組合せ論(algebraic combinatorics)とは、有限の組合せ構造についての問題を線形代数・群の作用・表現・対称関数などの代数の道具で解き、逆に代数に現れる量を組合せの対象の個数として記述する分野である。中心の問いは、数えたいものを行列や作用素の言葉に写せるか、代数の計算で現れる非負整数は何を数えているか、対称性をどう計算に使うか、である。
この記事は分野の地図である。主な問いと代表的な結果を表にして、それぞれの記事へ案内する。続いて、分野の味が分かる例として、Young 図形の上の 2 つの作用素の交換関係だけから $\sum_\lambda(f^\lambda)^2=n!$ を証明する。
分野の出発点は、集合をベクトル空間に置き換え、関係を行列に置き換えることである。
集合 $S$ に対し、$S$ を基底とする実ベクトル空間($S$ の元の有限個の線形結合の全体)を $\mathbb{R}S$ と書く。$S$ と $T$ の間の関係 $R\subset S\times T$ が、各 $s\in S$ について $(s,t)\in R$ となる $t$ を有限個しかもたないとき、線形写像 $\varphi_R\colon\mathbb{R}S\to\mathbb{R}T$ を $\varphi_R(s):=\sum_{(s,t)\in R}t$ で定める。これを $R$ の 線形化 という。
線形化の要点は、写像の合成が「途中の点を数える」ことになる点である。$R\subset S\times T$、$R'\subset T\times U$ について、$\varphi_{R'}\circ\varphi_R(s)$ における $u$ の係数は、$(s,t)\in R$ かつ $(t,u)\in R'$ となる $t$ の個数に等しい。したがって $k$ 回の合成の係数は長さ $k$ の鎖の個数を数える。グラフの隣接関係を線形化したものが 隣接行列 であり、$A^k$ の成分が長さ $k$ の歩道の個数を与えるのはこの特別な場合である(Sta13 Theorem 1.1、p. 10)。
数えたい量を線形写像の行列式・固有値・トレースで表せれば、線形代数の定理がそのまま数え上げの定理になる。逆向きの流れもある。対称多項式や群の表現に現れる係数が非負整数であるとき、それが何かの個数であることを示すと、計算が組合せの操作に置き換わる。Schur多項式 が半標準盤の重みの和で表されることがその典型である。
| 問い | 代表的な結果 | 入る記事 |
|---|---|---|
| 歩道はいくつあるか | $A^k$ の成分が長さ $k$ の歩道の個数で、閉じた歩道の総数は固有値の $k$ 乗和である | 隣接行列 |
| 全域木はいくつあるか | 全域木の個数は Laplacian 行列の余因子に等しい(BH11 Proposition 1.3.4) | 行列木定理 |
| 交わらない道の組はいくつあるか | 道の重みの和を並べた行列の行列式は、頂点を共有しない道の組の符号つきの和に等しい | Lindström–Gessel–Viennotの補題 |
| 対称性を除くといくつあるか | 軌道の個数は固定点の個数の平均である。塗り分けでは巡回指数に重みの冪和を代入すれば目録が得られる | Burnsideの補題、Pólyaの数え上げ定理 |
| 盤はいくつあるか | 標準盤の個数は $n!$ を鉤の長さの積で割ったものである | Young図形 |
| 置換と盤はどう対応するか | RSK 対応は、非負整数の行列と同じ形の半標準盤の組の全単射である | Robinson–Schensted–Knuth対応 |
| 対称多項式の良い基底は何か | Schur 関数は対称関数環の $\mathbb{Z}$ 基底で、Hall 内積の正規直交基底である | 対称関数、Schur多項式、Macdonald多項式 |
| 順序の中の反鎖はどこまで大きいか | $n$ 元集合の反鎖の大きさは $\binom{n}{\lfloor n/2\rfloor}$ 以下である | Spernerの定理、Dilworthの定理 |
| 半順序の上で包除原理はどうなるか | Möbius 関数が反転公式を与える | 数え上げ組合せ論、Möbiusの反転公式 |
| 関係の表はどんな代数をなすか | アソシエーションスキームの関係の行列は可換な Bose–Mesner 代数を張り、Delsarte の線形計画限界を与える | アソシエーションスキーム |
| 集合族の大きさを次元で抑えられるか | $n$ 元集合の部分集合の族で、各元の大きさが奇数、2 つの共通部分の大きさが偶数なら、族の大きさは $n$ 以下である(Oddtown の定理) | 組合せ論 |
| 多面体の格子点はいくつあるか | 格子多面体を $t$ 倍したものの格子点の個数は $t$ の多項式である | Ehrhart多項式 |
| 鏡映の群の組合せは何を数えるか | 対称群の Coxeter 関係式を満たす差分商から Schubert 多項式が定まる | Coxeter系、Schubert多項式 |
これらの主題の教科書的な入口として Sta13 がある。歩道(第 1〜3 章)、Sperner 性(第 4〜6 章)、群の作用による数え上げ(第 7 章)、Young 盤(第 8 章)、行列木定理(第 9 章)、電気回路(第 11 章)を、線形代数を共通の道具として扱っている。
$n$ の分割 $\lambda$ を Young図形 と同一視し、箱の集合の包含で順序を入れる。空の図形 $\emptyset$ も含めた全体を Young 束 $Y$ という。$\lvert\lambda\rvert$ で箱の個数を表す。$\lambda$ を箱を 1 個ずつ増やして作る列($\emptyset\subset\lambda^{(1)}\subset\dots\subset\lambda^{(n)}=\lambda$、$\lvert\lambda^{(i)}\rvert=i$)は、箱に入る順に $1,\dots,n$ を書いたものが標準盤になるので、$\lambda$ の標準盤の個数 $f^\lambda$ はこの列の個数に等しい。
$\lambda\subset\mu$、$\lvert\mu\rvert=\lvert\lambda\rvert+1$ である組の関係を線形化して、線形写像 $U,D\colon\mathbb{R}Y\to\mathbb{R}Y$ を
$$
U\lambda:=\sum_{\mu\supset\lambda,\ \lvert\mu\rvert=\lvert\lambda\rvert+1}\mu,\qquad D\lambda:=\sum_{\nu\subset\lambda,\ \lvert\nu\rvert=\lvert\lambda\rvert-1}\nu
$$
で定める($D\emptyset:=0$)。
$\mathbb{R}Y$ の上で $DU-UD=I$ である。
$\lvert\lambda\rvert=i$ とする。$DU\lambda$ と $UD\lambda$ はどちらも箱 $i$ 個の図形の線形結合なので、箱 $i$ 個の図形 $\mu$ の係数を比べる。
$\mu\ne\lambda$ のとき。$DU\lambda$ の $\mu$ の係数は、$\lambda$ と $\mu$ をともに含む箱 $i+1$ 個の図形の個数である。そのような図形は和集合 $\lambda\cup\mu$ を含むので、$\lvert\lambda\cup\mu\rvert=i+1$ のときに限り、$\lambda\cup\mu$ の 1 個だけある(2 つの Young 図形の和集合と共通部分はまた Young 図形である)。同様に、$UD\lambda$ の $\mu$ の係数は、$\lvert\lambda\cap\mu\rvert=i-1$ のとき $1$、それ以外のとき $0$ である。$\lvert\lambda\cup\mu\rvert+\lvert\lambda\cap\mu\rvert=2i$ なので 2 つの条件は同値であり、2 つの係数は等しい。
$\mu=\lambda$ のとき。$DU\lambda$ の $\lambda$ の係数は箱を加えられる場所の個数で、$UD\lambda$ の $\lambda$ の係数は箱を除ける場所の個数である。$\lambda$ の行の長さの相異なる正の値が $r$ 個あるとする。箱を除けるのは同じ長さの行の並びの最後の行の右端だけなので $r$ 個ある。箱を加えられるのは同じ長さの行の並びの最初の行の右と、最初の空の行だけなので $r+1$ 個ある。差は $1$ である。$\square$
$n\ge0$ について $\displaystyle\sum_{\lvert\lambda\rvert=n}(f^\lambda)^2=n!$ である。
$v_k:=U^k\emptyset$ とおく。$Dv_k=kv_{k-1}$($k\ge1$)を $k$ についての帰納法で示す。$k=1$ なら $DU\emptyset=UD\emptyset+\emptyset=\emptyset$ である。$k\ge2$ なら thm-ac-commutator により
$$
Dv_k=DUv_{k-1}=UDv_{k-1}+v_{k-1}=(k-1)Uv_{k-2}+v_{k-1}=kv_{k-1}
$$
である。したがって $D^nv_n=n!\,\emptyset$ である。
$U^n\emptyset$ の $\lambda$ の係数は $\emptyset$ から $\lambda$ まで箱を 1 個ずつ増やす列の個数なので $f^\lambda$ であり、$v_n=\sum_{\lvert\lambda\rvert=n}f^\lambda\lambda$ である。同様に $D^n\lambda$ は $f^\lambda\emptyset$ である。よって $n!\,\emptyset=D^nv_n=\sum_\lambda f^\lambda\cdot f^\lambda\,\emptyset$ である。$\square$
交換関係は Sta13 Lemma 8.3(pp. 135–136)、平方和は Corollary 8.5(p. 138)にある(そこでは一般の語の場合の定理から導く)。
$U\emptyset=(1)$、$U(1)=(2)+(1,1)$、$U(2)=(3)+(2,1)$、$U(1,1)=(2,1)+(1,1,1)$ なので、$U^3\emptyset=(3)+2\,(2,1)+(1,1,1)$ である。係数の平方の和は $1+4+1=6=3!$ である。
同じ等式は Robinson–Schensted–Knuth対応 の全単射からも、対称群の既約表現の次元の平方和としても得られる。ここでの証明は全単射を作らず、$DU-UD=I$ という 1 つの関係だけで進む。線形化すると、証明が交換関係の計算になる。
thm-ac-commutator は Young 束の性質であり、半順序の一般の性質ではない。$n$ 元集合の部分集合全体(ブール束)で同じように上昇作用素と下降作用素を定めると、$\lvert S\rvert=i$ の $S$ について $US$ は $n-i$ 項、$DS$ は $i$ 項の和である。非対角成分は Young 束のときと同じように打ち消し合い、対角成分の比較から
$$
DU-UD=(n-2i)I
$$
となり(Sta13 Lemma 4.6、p. 52)、右辺は $i$ によって変わる。実際、cor-ac-sum に当たる式も成り立たない。
| 半順序 | 主張 | 反例 |
|---|---|---|
| ブール束 | 階数 $k$ の元への極大鎖の個数の平方和は $k!$ である | 空集合から $S$ への鎖は $\lvert S\rvert!$ 本なので、$n=k=2$ で平方和は $(2!)^2=4\ne2!$ である |
ブール束の式の右辺が $i$ によって変わることも無駄ではなく、$i< n/2$ で $U$ が単射になることが出て、Spernerの定理 の線形代数による証明になる(Sta13 第 4 章、Corollary 4.8、p. 53)。
| 段階 | 記事 | 身につくこと |
|---|---|---|
| 1. 土台 | 組合せ論、数え上げ組合せ論、隣接行列 | 数え上げの基本と、行列で数えること |
| 2. 行列式と対称性 | 行列木定理、Lindström–Gessel–Viennotの補題、Burnsideの補題 → Pólyaの数え上げ定理 | 行列式と群の作用による数え上げ |
| 3. 盤と対称関数 | Young図形 → Robinson–Schensted–Knuth対応、対称多項式 → Schur多項式 → 対称関数 | 盤の組合せと対称関数の基底 |
| 4. 発展 | Macdonald多項式、Coxeter系 → Schubert多項式、アソシエーションスキーム、Ehrhart多項式 | 主題ごとの深い構造 |
段階 2 と段階 3 は独立に読める。段階 3 は 対称群 の基本を使う。
いずれも Sta13(2013 年の版)の時点の記述である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する