数え上げ組合せ論
概要
数え上げ組合せ論（かぞえあげくみあわせろん、enumerative combinatorics）とは、組合せ論の一分野で、特に有限集合の要素の数を「数え上げる」ことをその目的とするものである。
概要
なんらかの(興味深い)有限集合 $X$ が与えられたとき、$X$ を調べるうえで重要な情報であり、かつ最も素朴なとして、「$X$ の要素の個数」が挙げられる。
たとえば、$n$ 元集合 $F$ が与えられたとき、$X$ を $F$ から $F$ への集合としての同型(全単射)全体の集合としてとると、$X$ に要素がいくつあるのかという素朴な疑問が生じる。この場合については、$|X|=n!$ と(比較的簡単に) $X$ の要素の個数を記述することができる。
しかし、一般に数学において現れる有限集合に対して、その要素の個数を簡単に記述できるとは限らず、またそもそも個数を決定すること自体が難しい場合がある(例として、「$n$ 元集合上に位相構造が何種類入るか」「$n$ 以下の素数の個数はいくつか」「$n$ を平方数の和で表す方法は何通りか」などの問いが挙げられる)。
このような問題を解決するために様々な手法が開発・整備されてきた。そのなかでもいくつかの基本的もしくは重要なものについて概説をおこなう。
鳩ノ巣原理
鳩ノ巣原理 (pigeon-hole principle) とは、「$n$ 元集合を $m$ 個の部分集合に分割したとき、いずれかは $\frac{n}{m}$ 個以上の要素を持つ」という原理のことである。つまり、
$n\geq 0$, $m>0$ となる整数 $n$ と、$\# S\geq n$ となる集合 $S$ をとり、
$$S=\cup_{i=1}^m S_i$$
となるように集合 $S_1, \ldots, S_m$ をとる（なお、$S_i\cup S_j=\emptyset$ でなくてもよい）。このとき
$$\# S_k\geq \frac{n}{m}$$
となる $k\in \{1, \ldots, n\}$ が存在する。
$i=1, \ldots, m$ について
$$\# S_k<\frac{n}{m}$$
が成り立つとき
$$\# S\leq \sum_{i=1}^m \#S_k < n$$
となって仮定に反する。
以下に鳩ノ巣原理の具体的な問題に適用された例を挙げる。
ある自然数 $n$ とFibonacci数列 $a_1=1$, $a_2=1$, $a_3=2$, $a_4=3$, $\ldots$ について、$a_i$ を $n$ で割った余りは $i$ について周期的であり、その最小周期 $P_n$ は $n^2$ 以下である。
整数 $1\leq i$ について $a_i$ を $n$ で割った余りを $b_i$ とおくと、$(b_i,b_{i+1})$ として取りうる値は高々 $n^2$ 種類である。ここで、$(b_d,b_{d+1})=(0,1)$ ならば、$P_n$ は $d$ の約数となる。
$1\leq i \leq n^2$ について $(b_i,b_{i+1})=(0,1)$ ならば、鳩ノ巣原理より、ある $1\leq j \lt k\leq n^2$ であって $(b_j,b_{j+1})=(b_k,b_{k+1})$ なるものを取れる。このとき $P_n$ は $k-j$ の約数である。よって $P_j \leq n^2$ が成り立つ。
正 $432$ 角形の頂点を $4$ 色(色の名前を $R$, $W$, $B$, $Y$ とよぶ)に色分けし、ちょうど $108$ 個の頂点が各々の色で塗られているようにする。このとき、色 $R$ (resp. $W$, $B$, $Y$)が塗られた頂点のみを頂点として持つ三角形を $R$ (resp. $W$, $B$, $Y$)的な三角形ということにする。このとき、$R$ 的な三角形とも $W$ 的な三角形とも $B$ 的な三角形とも $Y$ 的な三角形とも合同であるような三角形が存在する。
色 $R$ で塗られた頂点全体の集合を $V_R$ と表記し、同様に $V_W$, $V_B$, $V_Y$ を定める。また、頂点の集合 $V$ について、$V[n]$ で「$V$ に含まれる頂点の右に $n$ 個隣にある頂点」の集合を表すものとする。
このとき、$\sum_{0\leq i \leq 431}|V_R\cap V_W[i]|=108\times 108$ が成り立つ。ここで、$V_R\cap V_W$ は空集合であるため、ある $1\leq i \leq 431$ であって $V_R\cap V_W[i]$ が $28$ 元以上であるものが取れる。このような $i$ をひとつ取り、$V_R\cap V_W[i]$ を $V_R^\prime$ とおく。
同様に、$\sum_{0\leq j \leq 431}|V_R^\prime\cap V_B[j]|=28\times 108$ が成り立つ。ここで、$V_R^\prime\cap V_B$ は空集合であるため、ある $1\leq j \leq 431$ であって $V_R^\prime\cap V_B[j]$ が $8$ 元以上であるものが取れる。このような $j$ をひとつ取り、$V_R\prime\cap V_B[j]$ を $V_R^{\prime\prime}$ とおく。
同様に、$\sum_{0\leq k \leq 431}|V_R^{\prime\prime}\cap V_Y[k]|=8\times 108$ が成り立つ。ここで、$V_R^{\prime\prime}\cap V_Y$ は空集合であるため、ある $1\leq j \leq 431$ であって $V_R^{\prime\prime}\cap V_Y[k]$ が $3$ 元以上であるものが取れる。このような $k$ をひとつ取り、$V_R^{\prime\prime}\cap V_Y[k]$ を $V_R^{\prime\prime\prime}$ とおく。$V_R^{\prime\prime\prime}$ の頂点からなる三角形が求めるものである。
母関数
しばしば組合せ論においては自然数 $i$ によってパラメータ付けられた有限集合の族 $\{S_i\}_{i \in\mathbb{N}_0}$ が現れる。このとき、$S_i$ の要素の個数を $\#S_i$ を統一的に扱う方法が求められる。そのような道具として、母関数なるものが挙げられる。
有限集合の族 $\{X_i\}_{i \in\mathbb{N}_0}$ についての母関数 (generating function) とは、形式的冪級数 $$ \sum_{i=0}^\infty \#S_i X^i $$ のことである。
Möbius関数
有限半順序集合 $P$ に対して、以下の性質を満たすような関数 $\mu\colon P\times P \to \mathbb{Z}$ がただひとつ存在することが知られている。
- $p, q\in P, p\leq q$ について、$\sum_{p\leq r \leq q} \mu(p,r)=\delta_{p,q}$,
- $p, q\in P, p>q$ について、$\mu(p,q)=0$.
ただし、ここで $\delta_{p,q}$ は、クロネッカーのデルタ
$$\delta_{p, q}=\begin{cases}1 & (p=q) \\ 0 & (p\neq q)\end{cases}$$
を指す。このような関数 $\mu$ を $P$ についてのメビウス関数 (Möbius function) という。
$P$ が引き続く整数からなる集合で、大小関係を順序関係にもつとする。このとき
$$\mu(n, n)=1, \mu(n, n+1)=-1, \mu(n, n+k)=0 (k\geq 2)$$
は上記の条件を満足するので、$P$ 上のMöbius関数となる。
逆に、$P$ 上の大小関係を順序関係とするMöbius関数はこの形のものに一意的に定まる。実際、上記の条件から $\mu(n, n)=1, \mu(n, n+1)=-\mu(n, n)=-1$ でなければならない。$k\geq 2$ に対しては $\sum_{r=0}^k \mu(n, n+r)=0$ より $\mu(n, n+k)=0$ となる。
この構成は、$P$ が有限集合でない場合、たとえば $P$ が 自然数全体 $\N=\{0, 1, \ldots \}$ あるいは整数全体 $\Z=\{0, \pm 1, \pm 2, \ldots\}$ の集合であるときにも可能である。
$S$ が引き続く整数からなる集合で、$S$ の順序関係 $\leq_S$ が大小関係により定まるとき $P=S^m$ あるいは、$S^\infty$ の部分集合で、有限個の要素を除いて $0$ であるもの全体の集合
$$P=S^{<\infty}=\{(a_0, a_1, \ldots): a_i\in S, \exists m_0[m\geq m_0\Longrightarrow a_m=0]\}$$
について、$\mathbf{a}=(a_0, a_1, \ldots), \mathbf{b}=(b_0, b_1, \ldots)$ の大小関係を
$$\mathbf{a}\leq \mathbf{b}\Longleftrightarrow \forall i [a_i\leq_S b_i]$$
により定めると、
$$\mu((a_0, a_1, \ldots, a_i, \ldots), (b_0, b_1, \ldots, b_i, \ldots))=\left\{\begin{array}{cl}0 & (\exists i[b_i\geq a_i+2])\\
(-1)^k & (\forall i[a_i\leq b_i\leq a_i+1]\land \#\{b_i=a_i+1\}=k)\end{array}\right.$$
はMöbius関数となる。
この場合も、逆に、上記の順序関係に関する$P$ 上のMöbius関数はこの形のものに一意的に定まることも示せる。
$N>0$ に対して
$$N=2^{e_1} 3^{e_2} \cdots$$
と素因数分解し、$P=\N^{<\infty}$ において
例2
で構成したMöbius関数 $\mu_P$ を用いて
$$\mu(N)=\mu_P((0, 0, \ldots), (e_1, e_2, \ldots))$$
と定めると、$N$ の相異なる素因数の個数が $k$ のとき
$$N=\left\{\begin{array}{cl} (-1)^k& (\forall i[e_i\leq 1])\\
0 & (\exists i[e_i\geq 2])\end{array}\right.$$
となって、通常のMöbius関数を与える。
包含と除去の原理（一般形）
半順序集合 $P$ がMöbius関数をもち、集合 $S$ から $P$ への写像 $f: S\rightarrow P$ が存在し、$f(x)\geq p_0 (x\in S)$ となる $p_0\in P$ が存在するとする。このとき、定義から
$$\begin{split}
\#\{x\in S: f(x)=p_0\}= & \sum_{x\in S}\sum_{p_0\leq q\leq f(x)} \mu(p_0, q) \\
= & \sum_{q\in P} \mu(p_0, q)\sum_{x\in S, f(x)\geq q}1 \\
= & \sum_{q\in P} \mu(p_0, q)\#\{x\in S: f(x)\geq q\}
\end{split}$$
となる。これは次に述べる包含と除去の原理 (inclusion-exclusion principle) の一般化となる。
$S_1, S_2, \ldots$ がある与えられた集合 $A$ の部分集合で、どのような $x\in A$ についても、 $x$ を含む $S_i$ は有限個しか存在しないとし、$x$ を含む $S_i$ の個数を $\nu(x)$ とおく。
$$\mu(x)=(-1)^{\nu(x)}$$
は、Möbius関数に対応する。
$f_i(x)=\chi_{S_i}(x)$ を $S_i$ に関する特性関数とし
$$f(x)=(f_0(x), f_1(x), \ldots)$$
とおくと、どのような $x\in A$ についても、 $x$ を含む $S_i$ は有限個しか存在しないので、有限個の $i$ を除いて $f_i(x)=0$ となる。よって $f$ は $A$ から $P$ への写像となっている。
$P=\{0, 1\}^{<\infty}$ は
例2
で構成したMöbius関数 $\mu_P$をもつが、
$$\mu(x)=\mu_P((0, 0, \ldots), f(x))$$
となる。
さらに、正の整数の集合 $I\subset\N_{>0}$ に対して
$$S_I=\cap_{i\in I}S_i$$
とおく。
$q=(q_1, q_2, \ldots)\in \{0, 1\}^{<\infty}$ に対して
$$J(q)=\{i: q_i=1\}$$
とおくと、
$$f(x)\geq q\Longleftrightarrow \forall(i\in J(q))[x\in S_i]\Longleftrightarrow x\in S_{J(q)}$$
となる。
$\mu_P(p, q)$ を $P=\{0, 1\}^{<\infty}$ に関するMöbius関数とし、$p_0=(0, 0, \ldots)$ とおくと
$$\mu_P(p_0, q)=(-1)^{\# J(q)}$$
となるので、通常の包含と除去の原理
$$\#(A\backslash (S_1\cup S_2\cup \cdots))=\sum_{I\subset \N_{>0}, \# I<\infty}(-1)^{\# I} \# S_I$$
が成り立つ。
$p_1, p_2, \ldots, p_k$ を相異なる素数、$S$ を $x\leq N$ となる整数で $p_1, p_2, \ldots, p_k$ のいずれとも互いに素な整数の集合とする。
$A_{p_i}=S_i$ を $N$ 以下の整数のうち $p_i$ の倍数全体の集合とし、平方因数をもたず、素因数が $p_1, p_2, \ldots, p_k$ のいずれかである整数 $d$ に対して
$$A_d=\cap_{p\mid d} A_p$$ とおくと $I\subset \{1, 2, \ldots, k\}, d=\prod_{i\in I} p_i$ に対して $S_I=A_d, (-1)^{\# I}=\mu(d)$ となるから
$$\# S=\sum_d \mu(d) \# A_d$$
が成り立つ。
素因数分解の一意性
から $A_d$ は $N$ 以下の整数のうち、$d$ の倍数全体の集合と一致する。よって
$$\# A_d=\floor{\frac{N}{d}}$$
となる。
$d>N$ のとき $A_d$ は空集合となるから、 $T$ を $N$ 以下の整数で平方因数をもたず、素因数が $p_1, p_2, \ldots, p_k$ のいずれかである整数全体の集合とすると
$$\# S=\sum_{d\in T} \mu(d)\floor{\frac{N}{d}}$$
が成り立つ。
とくに $p_1, p_2, \ldots, p_k\leq M$ となる $M< N$ が存在するとき $M< p\leq N$ となる素数 $p$ は $p_1, p_2, \ldots, p_k$ と互に素でなければならないから
$$\pi(N)-\pi(M)\leq \# S=\sum_{d\in T} \mu(d)\floor{\frac{N}{d}}$$
となる。さらに、$M=\sqrt{N}$ で $p_1, p_2, \ldots, p_k$ が $\sqrt{N}$ 以下の素数全体のときは等号が成り立つ。
この公式はこのままでは、与えられた整数以下の素数の個数を調べる上ではほとんど役に立たない。右辺の和に含まれる項の数が多すぎるからである。
しかし、形を変えた不等式を示すことで、特殊な形の素数や、素因数の個数の少ない整数の個数を評価することが可能となる。
この方法は篩法と呼ばれ、20世紀になってBrunがそのような方法を開発した後、大きく発展した。
