数え上げ組合せ論

$\newcommand{\NN}{\mathbb{N}}$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\QQ}{\mathbb{Q}}$ $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\CC}{\mathbb{C}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$

数え上げ組合せ論(かぞえあげくみあわせろん、enumerative combinatorics)とは、組合せ論の一分野で、特に有限集合の要素の数を「数え上げる」ことをその目的とするものである。

概要

なんらかの(興味深い)有限集合 $X$ が与えられたとき、$X$ を調べるうえで重要な情報であり、かつ最も素朴なとして、「$X$ の要素の個数」が挙げられる。たとえば、$n$ 元集合 $F$ が与えられたとき、$X$ を $F$ から $F$ への集合としての同型(全単射)全体の集合としてとると、$X$ に要素がいくつあるのかという素朴な疑問が生じる。この場合については、$|X|=n!$ と(比較的簡単に) $X$ の要素の個数を記述することができる。しかし、一般に数学において現れる有限集合に対して、その要素の個数を簡単に記述できるとは限らず、またそもそも個数を決定すること自体が難しい場合がある(例として、「$n$ 元集合上に位相構造が何種類入るか」「$n$ 以下の素数の個数はいくつか」「$n$ を平方数の和で表す方法は何通りか」などの問いが挙げられる)。

このような問題を解決するために様々な手法が開発・整備されてきた。そのなかでもいくつかの基本的もしくは重要なものについて概説をおこなう。

鳩ノ巣原理

鳩ノ巣原理とは、「$n$ 元集合を $m$ 個の部分集合に分割したとき、いずれかは $\frac{n}{m}$ 個以上の要素を持つ」という原理のことである。以下に鳩ノ巣原理の具体的な問題に適用された例を挙げる。

命題 1

ある自然数 $n$ とFibonacci数列 $a_1=1$, $a_2=1$, $a_3=2$, $a_4=3$, $\ldots$ について、$a_i$ を $n$ で割った余りは $i$ について周期的であり、その最小周期 $P_n$ は $n^2$ 以下である。

命題 1の証明：

整数 $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$ が成り立つ。(Q.E.D.)

命題 2

正 $432$ 角形の頂点を $4$ 色(色の名前を $R$, $W$, $B$, $Y$ とよぶ)に色分けし、ちょうど $108$ 個の頂点が各々の色で塗られているようにする。このとき、色 $R$ (resp. $W$, $B$, $Y$)が塗られた頂点のみを頂点として持つ三角形を $R$ (resp. $W$, $B$, $Y$)的な三角形ということにする。このとき、$R$ 的な三角形とも $W$ 的な三角形とも $B$ 的な三角形とも $Y$ 的な三角形とも合同であるような三角形が存在する。

命題 2の証明：

色 $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}$ の頂点からなる三角形が求めるものである。(Q.E.D.)

母関数

しばしば組合せ論においては自然数 $i$ によってパラメータ付けられた有限集合の族 $\{X_i\}_{i \in\mathbb{N}_0}$ が現れる。このとき、$X_i$ の要素の個数を $a(i)$ とおいたとき、$a(i)$ を統一的に扱う方法が求められる。そのような道具として、母関数なるものが挙げられる。有限集合の族 $\{X_i\}_{i \in\mathbb{N}_0}$ についての母関数とは、形式的冪級数 $$ \sum_{i=0}^\infty a(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}$ は、クロネッカーのデルタを指す。このような関数 $\mu$ を $P$ についてのMöbius関数という。

例1

$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$ が 自然数全体 $\NN=\{0, 1, \ldots \}$ あるいは整数全体 $\ZZ=\{0, \pm 1, \pm 2, \ldots\}$ の集合であるときにも可能である。

例2

$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関数となる。 実際 $t$ を $b_i>a_i$ となる最大の $i$ とすると $$\begin{split} \sum_{\mathbf{a}\leq\mathbf{c}\leq\mathbf{b}}\mu(\mathbf{a}, \mathbf{c})= & \sum_{k=0}^{b_t-a_t} \sum_{a_i\leq c_i\leq b_i (0\leq i\leq t-1)}\mu(\mathbf{a}, (c_0, c_1, \ldots, c_{t-1}, a_t+k, a_{t+1}, \ldots)) \\ = & \sum_{a_i\leq c_i\leq b_i (0\leq i\leq t-1)}\mu(\mathbf{a}, (c_0, c_1, \ldots, c_{t-1}, a_t, a_{t+1}, \ldots))+\mu(\mathbf{a}, (c_0, c_1, \ldots, c_{t-1}, a_t+1, a_{t+1}, \ldots)) \\ \end{split}$$ となるが、$c_i\geq a_i+2$ となる $i$ が存在するときは$2$行目の和のなかの$\mu$関数の値はともに $0$ となり、 すべての $i=0, 1, \ldots, t-1$ に対して $a_i\leq c_i\leq a_i+1$ となるときは$2$行目の和のなかの$\mu$関数の値は互いに反対符号をとる。よって$2$行目の和の被加数はつねに $0$ となるから $$\sum_{\mathbf{a}\leq\mathbf{c}\leq\mathbf{b}}\mu(\mathbf{a}, \mathbf{c})=0$$ となる。

逆に、$P$ 上のMöbius関数はこの形のものに一意的に定まることも示せる。

まず、すべての $i$ について $a_i\leq b_i\leq a_i+1$ が成り立っている場合について考える。$b_i=a_i+1$ となる $i$ の個数を $k$ として、$k$ に関する帰納法で示す。 $k=1$ の場合は例1と同様に明らかである。$k=0, 1, \ldots, \ell-1$ について上記の等式が成り立つとする。 $\ell$ 個の $i$ について $b_i=a_i+1$ が成り立ち、その他の $i$ について $b_i=a_i$ となっているとする。 $$T=\{i: b_i=a_i+1\}$$ とおくと $$\# T=\ell$$ となる。 $$\mathbf{a}\leq \mathbf{c}\leq \mathbf{b}$$ となる $\mathbf{c}=(c_0, c_1, \ldots)$ をとる。 $$U=\{i: c_i=a_i+1\}$$ とおくと $$U\subset T, 0\leq \#U\leq \ell$$ となる。かつ帰納法の仮定より $U\neq T$ のとき $$\mu(\mathbf{a}, \mathbf{c})=(-1)^{\#U}$$ となる。また $\# U=r$ となる $\mathbf{c}$ の個数は $\binom{\ell}{r}$ に一致する。 $$\sum_{\mathbf{a}\leq\mathbf{c}\leq\mathbf{b}}\mu(\mathbf{a}, \mathbf{c})=0$$ かつ $$\begin{split} \sum_{\mathbf{a}\leq\mathbf{c}\leq\mathbf{b}}\mu(\mathbf{a}, \mathbf{c})= & \sum_{r=0}^k \sum_{\mathbf{a}\leq\mathbf{c}\leq\mathbf{b}, \# U=r}\mu(\mathbf{a}, \mathbf{c}) \\ = & \mu(\mathbf{a}, \mathbf{b})+\sum_{r=0}^{k-1} \sum_{\mathbf{a}\leq\mathbf{c}\leq\mathbf{b}, \# U=r}\mu(\mathbf{a}, \mathbf{c}) \\ = & \mu(\mathbf{a}, \mathbf{b})+\sum_{r=0}^{k-1} \sum_{\mathbf{a}\leq\mathbf{c}\leq\mathbf{b}, \# U=r}(-1)^r \\ = & \mu(\mathbf{a}, \mathbf{b})+\sum_{r=0}^{k-1} (-1)^r\binom{k}{r} \\ \end{split}$$ より $$\mu(\mathbf{a}, \mathbf{b})=-\sum_{r=0}^{k-1} (-1)^r\binom{k}{r}=(-1)^k-(1-1)^k=(-1)^k$$ となる。

つぎに $b_i\geq a_i+2$ となる $i$ が存在するとする。$b_i$ は有限個を除いて $0$ だから $$t=\sum_i (b_i-a_i)$$ が存在する。$t$ に関する帰納法で $\mu(\mathbf{a}, \mathbf{b})=0$ を証明する。

$b_i\geq a_i+2$ となる $i$ が存在し、$j\neq i$ について $a_j=b_j$ となるときは例1と同様に $$\mu((a_0, a_1, \ldots, a_i, \ldots), (a_0, a_1, \ldots, b_i, \ldots))=0$$ が成り立つ。

一般の場合 $$c_i=a_i (a_i=b_i), a_i+1 (b_i>a_i)$$ により $\mathbf{c}=(c_0, c_1, \ldots)$ を定め、 $$U=\{\mathbf{d}: \mathbf{a}\leq\mathbf{d}\leq\mathbf{b}, \mathbf{d}\not\leq\mathbf{c}\}$$ とおく（$\mathbf{d}\not\leq\mathbf{c}$ は $\mathbf{c}\leq\mathbf{d}$ を意味しないので注意）と $\mathbf{a}\leq\mathbf{d}\leq\mathbf{c}$ となる $\mathbf{d}$ については、先に論じた場合に相当するので $$\begin{split} \sum_{\mathbf{a}\leq\mathbf{d}\leq\mathbf{b}}\mu(\mathbf{a}, \mathbf{d})= & \sum_{\mathbf{a}\leq\mathbf{d}\leq\mathbf{c}}\mu(\mathbf{a}, \mathbf{d})+\sum_{\mathbf{d}\in U}\mu(\mathbf{a}, \mathbf{d}) \\ = & \sum_{\mathbf{d}\in U}\mu(\mathbf{a}, \mathbf{d}) \\ = & \mu(\mathbf{a}, \mathbf{b})+\sum_{\mathbf{d}\in U, \mathbf{d}\neq \mathbf{b}}\mu(\mathbf{a}, \mathbf{d})\end{split}$$ となるが、$\mathbf{d}\in U, \mathbf{d}\neq \mathbf{b}$ のとき $d_i\geq a_i+2$ となる $i$ が存在し、しかも $\mathbf{d}<\mathbf{b}$ となるから $$\sum_i (d_i-a_i)<\sum_i (b_i-a_i)$$ が成り立つので、帰納法の仮定より $$\sum_{\mathbf{d}\in U, \mathbf{d}\neq \mathbf{b}}\mu(\mathbf{a}, \mathbf{d})=0$$ となる。よって $$\mu(\mathbf{a}, \mathbf{b})=\sum_{\mathbf{a}\leq\mathbf{d}\leq\mathbf{b}}\mu(\mathbf{a}, \mathbf{d})=0 $$ となる。

例3

$N>0$ に対して $$N=2^{e_1} 3^{e_2} \cdots$$ と素因数分解し、$P=\NN^{<\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}$$ となる。これは次に述べる包含と除去の原理の一般化となる。

包含と除去の原理

$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\NN_{>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 \NN_{>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がそのような方法を開発した後、大きく発展した。

information

参考文献

• [Sta1] R. Stanley, "Enumerative Combinatorics, Volume I", Wadsworth, Monterey, Calif., 1986.

外部リンク

• [日1] 数え上げの世界, 日比孝之, j-stage (2020-10-21 有効なリンク)
• [Lur1] Combinatorics (Math 155), Jacob Lurie (2020-10-21 有効なリンク)