はじめに
前回の記事 Cable master とドント方式と中央値の中央値（一年前だった！）に続いて競技プログラミング関係ネタです。
競技プログラミングでよく出てくる重複組合せや両替問題ですが、この記事ではそれらの問題を母関数を使って解く方法を紹介します。
母関数を使うと組合せ論的アイデアをひねり出さずとも式の変形だけで公式を導き出すことができます。
重複組合せ問題
重複組合せ問題とは、例えば
赤の玉が1つ，青の玉が2つ，黄の玉が2つある。この中から4つ玉を選ぶときに得られる色のパターンが何通りあるか求めよ
のように $n$種類のもの（この例のように各種類の個数に上限をつけることもあります）から重複を許して $k$個選ぶ場合の数を求める問題です。
母関数
例にあげた問題で$k$個の玉を選ぶときに得られる色のパターンの場合の数を $c_k$ とすると
c_0 = 1, c_1 = 3, c_2 = 5, c_3 = 5, c_4 = 3, c_5 = 1
となっています。
唐突ですが、
(1+x)(1+x+x^2)(1+x+x^2)
という式を展開してみましょう。結果は
1 + 3x + 5x^2 + 5x^3 + 3x^4 + x^5
と係数が先ほどの $c_k$ と一致します。
展開前の式の最初の $1+x$ が赤の玉が0個か1個選べることに対応し、
二番目の $1+x+x^2$ が青の玉が0個か1個か2個選べることに対応し、
三番目の $1+x+x^2$ が黄の玉が0個か1個か2個選べることに対応しています。
このように $i$番目の種類のものが上限 $a_i$個あるところから重複を許して $k$個選ぶ場合の数を $c_k$ とすると
\prod_{i=1}^{n} (1+x+x^2+\cdots+x^{a_i}) = \sum_{k=0}^{\infty} c_k x^k
が成り立ちます。
右辺の式が $\infty$ までの無限和の形になっていますが、この場合 $a_1+a_2+\cdots+a_n$ より大きい $k$ については $c_k = 0$ なので実際には有限和になっています。
この右辺の $\sum_{k=0}^{\infty} c_k x^k$ を数列 {$c_k$} の母関数といいます。
母関数の係数を求められれば重複組合せ問題を解くことができます。
前提知識
この後使う基本的な冪級数に関する知識を挙げておきます。
ここでは形式的冪級数として扱うので収束とか分母が $0$ になったりしないのかとか気にしないでください。
二項係数
\binom{n}{k} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!} \tag{1}
これは $n \ge 0$ のときは
\binom{n}{k} = \frac{n!}{k!(n-k)!} \tag{1.1}
ですが $n$ が負の場合、例えば
\binom{-5}{3} = \frac{(-5)(-6)(-7)}{3!} = (-1)^3 \frac{5 \cdot 6 \cdot 7}{3!} = (-1)^3 \binom{5+3-1}{3}
となるように
\binom{-n}{k} = (-1)^k \binom{n+k-1}{k} \tag{1.2}
が成り立ちます。
二項展開
(1 + x)^n = \sum_{k=0}^{\infty} \binom{n}{k} x^k \tag{2}
$n \ge 0$ の場合は和が $k = n$ のところで止まりますが、$n$ が負の場合は無限に続きます。
等比級数の和
\begin{align}
&1 + x + x^2 + x^3 + \cdots + x^l = \frac{1 - x^{l+1}}{1 - x} \tag{3.1} \\
&1 + x + x^2 + x^3 + \cdots = \frac{1}{1 - x} \tag{3.2}
\end{align}
$x$ を $x^m$ に置き換えると
\begin{align}
&1 + x^m + x^{2m} + x^{3m} + \cdots + x^{lm} = \frac{1 - x^{(l+1)m}}{1 - x^m} \tag{3.3} \\
&1 + x^m + x^{2m} + x^{3m} + \cdots = \frac{1}{1 - x^m} \tag{3.4}
\end{align}
個数制限なし重複組合せ問題
まず、個数に上限のない $n$種類のものから重複を許して $k$個選ぶ場合の数を求める問題を考えましょう。
個数に上限がないので母関数は
(1+x+x^2+\cdots)^n
になります。(3.2) から
1 + x + x^2 + x^3 + \cdots = \frac{1}{1 - x}
でしたから母関数は
\begin{align}
(\frac{1}{1 - x})^n &= (1 - x)^{-n} \qquad 二項展開 (2) より \\
&= \sum_{k=0}^{\infty} \binom{-n}{k} (-x)^k \qquad (1.2) より \\
&= \sum_{k=0}^{\infty} (-1)^k \binom{n+k-1}{k} (-1)^k x^k \\
&= \sum_{k=0}^{\infty} \binom{n+k-1}{k} x^k
\end{align}
になります。
つまり $k$個選ぶ場合の数は $\binom{n+k-1}{k}$ になります。
これは重複組合せの公式 ${}_n H_k = \binom{n+k-1}{k}$ とも確かに一致します。
組合せ論的には「$k$個のものと $n−1$ 個の仕切りを一列に並べる」方法で解説されますが、母関数 $(1 - x)^{-n}$ の係数の $|\binom{-n}{k}|$ の方が覚えやすいように思います。
重複組合せの記号の豆知識
日本では重複組合せの記号に $H$ を使いますが世界共通ではないようです。
Wikipedia で調べると、英語では
\left(\binom{n}{k}\right)
フランス語では
\Gamma_{k}^{n}
を使っているようです。
ちなみに $H$ は「同次積」「斉次積」の意味の "homogeneous product" からきているようです。
個数制限あり重複組合せ問題
次は各種類 $i$で個数に上限 $a_i$ ありの問題を考えましょう。
この問題の答えの数列の母関数は
(1+x+x^2+\cdots + x^{a_1})(1+x+x^2+\cdots + x^{a_2}) \cdots (1+x+x^2+\cdots + x^{a_n})
になります。
ただし今度は簡単な形に変形できそうにないので
\prod_{t=1}^{i} (1+x+x^2+\cdots + x^{a_t}) = \sum_{j=0}^{\infty} f(i,j) x^j
として $f(i,j)$ の漸化式を求めます。
\sum_{j=0}^{\infty} f(i,j) x^j = (1+x+x^2+\cdots + x^{a_i}) \sum_{j=0}^{\infty} f(i-1,j) x^j
という関係が成り立ちますが、読みやすいように一時的に $d_j = f(i-1, j), e_j = f(i, j)$ とおいて書き直すと
\begin{align}
\sum_{j=0}^{\infty} e_j x^j &= (1+x+x^2+\cdots + x^{a_i}) \sum_{j=0}^{\infty} d_j x^j \qquad (3.1) より \\
&= \frac{1 - x^{a_i +1}}{1 - x} \sum_{j=0}^{\infty} d_j x^j
\end{align}
（$j$が負になる場合の注意： 以降で $d_j$ と $e_j$ で $j$ が負の場合がでてきますが、そのような $d_j$, $e_j$ は 0 と定義します）
分母を払うために両辺に $1 - x$ を掛けて
\begin{align}
左辺 &= (1 - x) \sum_{j=0}^{\infty} e_j x^j \\
&= \sum_{j=0}^{\infty} e_j x^j - \sum_{j=0}^{\infty} e_j x^{j+1} \qquad j+1 を j にずらして \\
&= \sum_{j=0}^{\infty} e_j x^j - \sum_{j=0}^{\infty} e_{j-1} x^j \\
&= \sum_{j=0}^{\infty} (e_j - e_{j-1}) x^j \\
右辺 &= (1 - x^{a_i +1}) \sum_{j=0}^{\infty} d_j x^j \\
&= \sum_{j=0}^{\infty} d_j x^j - \sum_{j=0}^{\infty} d_j x^{j+a_i +1} \qquad j+a_i+1 を j にずらして \\
&= \sum_{j=0}^{\infty} d_j x^j - \sum_{j=0}^{\infty} d_{j-a_i -1} x^j \\
&= \sum_{j=0}^{\infty} (d_j - d_{j-a_i -1}) x^j
\end{align}
両辺の $x^j$ の係数を比較すると
e_j - e_{j-1} = d_j - d_{j-a_i -1}
よって
e_j = e_{j-1} + d_j - d_{j-a_i -1}
$f$ での表現に戻すと
f(i, j) = f(i, j-1) + f(i-1, j) - f(i-1, j-a_i -1)
$f(i, j)$ は i番目までのものから各々上限 $a_i$ までの重複を許して j個選ぶ場合の数でしたが、DP（Dynamic Programming: 動的計画法）に適した漸化式が求まりました。
上限の数がすべて等しい重複組合せ問題
次は上限はあるものの上限の数がすべて等しいときの問題を考えましょう。
a_1 = a_2 = \cdots = a_n = l
というケースです。この問題の答えの数列の母関数は
(1+x+x^2+\cdots + x^l)^n
になります。
\begin{align}
(1+x+x^2+\cdots + x^l)^n &= (\frac{1 - x^{l+1}}{1 - x})^n \\
&= (1 - x^{l+1})^n (1 - x)^{-n} \qquad 二項展開(2)より \\
&= (\sum_{i=0}^{\infty} \binom{n}{i} (-1)^i x^{(l+1)i}) \cdot (\sum_{j=0}^{\infty} \binom{-n}{j} (-1)^j x^j) \\
&= \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \binom{n}{i} \binom{-n}{j} (-1)^{i+j} x^{(l+1)i+j} \\
& \qquad k = (l+1)i + j となる (i,j) の組は \\
& \qquad (0,k),(1,k-(l+1)),(2,k-2(l+1)),... なので \\
&= \sum_{k=0}^{\infty} \sum_{i=0}^{[\frac{k}{l+1}]} \binom{n}{i} \binom{-n}{k-(l+1)i} (-1)^{k-li} x^k
\end{align}
よって $k$個選ぶ場合の数は $x^k$ の係数である
\sum_{i=0}^{[\frac{k}{l+1}]} (-1)^{k-li} \binom{n}{i} \binom{-n}{k-(l+1)i}
ということになります。
これを $n$個のサイコロを振って目の合計が $n+k$ になる場合の数を求める問題に応用してみます。
（サイコロは $1$以上の目が出るので $n$個のサイコロの目の合計は $n$以上です）
$1$から$6$までの目のサイコロを各目を$1$ずらして0から5までの目を持つサイコロで考えると
$0$から$5$までの目を持つサイコロを $n$個振って目の合計が $k$ になる場合の数を求めればよいことになります。
これは上限が $5$個の $n$種類のものから $k$個選ぶ場合の数、つまり上の式の $l = 5$ の場合になります。
\begin{align}
\sum_{i=0}^{[\frac{k}{6}]} (-1)^{k-5i} \binom{n}{i} \binom{-n}{k-6i} &= \sum_{i=0}^{[\frac{k}{6}]} \binom{n}{i} (-1)^{k-5i} (-1)^{k-6i} \binom{n+k-6i-1}{k-6i} \\
&= \sum_{i=0}^{[\frac{k}{6}]} (-1)^i \binom{n}{i} \binom{n+k-6i-1}{k-6i}
\end{align}
数列の和の母関数は数列の母関数の和
数列 {$c_k$} と {$d_k$} の和を各項を足した数列 {$c_k + d_k$} とすると
\sum_{k=0}^{\infty} c_k x^k + \sum_{k=0}^{\infty} d_k x^k = \sum_{k=0}^{\infty} (c_k + d_k) x^k
なので {$c_k$} の母関数と {$d_k$} の母関数の和は {$c_k + d_k$} の母関数になります。
これを使って Atcoder の次の問題を解いてみましょう。
問題 Atcoder 178 D - Redistribution
整数 S が与えられます。 すべての項が 3 以上の整数で、その総和が S であるような数列がいくつあるか求めてください。
まずは数列の長さが決まっている場合の問題から考えましょう。その長さは i だとします。
「すべての項が 3 以上の整数で、その総和が $k$ であるような長さ i の数列」は、
「i種類のものを各種類から3個以上選んで合計 $k$個になる取り出し方」に対応するので、
この長さi での問題の答えの母関数は
(x^3+x^4+x^5+ \cdots)^i = (x^3(1+x+x^2+ \cdots))^i = (\frac{x^3}{1-x})^i = g(x)^i \\
（ただし g(x) = \frac{x^3}{1-x} とします）
になります。
数列の長さに制限のない元の問題の場合の数は、
長さ0の数列での場合の数 + 長さ1の数列での場合の数 + 長さ2の数列での場合の数 + \cdots
なので、対応する母関数も
長さ0のケースの母関数 + 長さ1のケースの母関数 + 長さ2のケースの母関数 + \cdots
よって、元々の問題の母関数は
\begin{align}
g(x)^0 + g(x)^1 + g(x)^2 + \cdots &= \frac{1}{1 - g(x)} \\
&= \frac{1}{1 - \frac{x^3}{1-x}} \qquad 分母分子に 1 - x を掛けて \\
&= \frac{1 - x}{1 - x - x^3}
\end{align}
になります。
母関数の冪級数を $\sum_{k=0}^{\infty} c_k x^k$ とすると
\frac{1 - x}{1 - x - x^3} = \sum_{k=0}^{\infty} c_k x^k
分母を払うために両辺に $1 - x - x^3$ を掛けると
\begin{align}
左辺 &= 1 - x \\
右辺 &= (1 - x - x^3) \sum_{k=0}^{\infty} c_k x^k \\
&= \sum_{k=0}^{\infty} c_k x^k - \sum_{k=0}^{\infty} c_k x^{k+1} - \sum_{k=0}^{\infty} c_k x^{k+3} \qquad k+1 と k+3 をそれぞれ k にずらして \\
&= \sum_{k=0}^{\infty} c_k x^k - \sum_{k=0}^{\infty} c_{k-1} x^k - \sum_{k=0}^{\infty} c_{k-3} x^k \\
&= \sum_{k=0}^{\infty} (c_k - c_{k-1} - c_{k-3}) x^k
\end{align}
両辺の係数を比べると
\begin{align}
&c_0 = 1; c_1 - c_0 = -1; c_2 - c_1 = 0; \\
&c_k - c_{k-1} - c_{k-3} = 0 \qquad (k >= 3 のとき)
\end{align}
これを解いて
\begin{align}
&c_0 = 1; c_1 = 0; c_2 = 0; \\
&c_k = c_{k-1} + c_{k-3} \qquad (k >= 3 のとき)
\end{align}
という漸化式が求められました。
両替問題
次は両替問題を考えます。
この記事でいう両替問題とは、例えば
1円硬貨が7枚，5円硬貨が4枚，10円硬貨が5枚ある。これらの硬貨で16円払うパターンが何通りあるか求めよ」
のように $n$種類の硬貨（この例のように各種類の枚数に上限をつけることもあります）から合計 $k$円払う場合の数を求める問題です。
枚数制限なし両替問題
まずは枚数制限なしで考えましょう。
$i$番目の硬貨が$b_i円硬貨$とします。この問題の答えの数列の母関数は重複組合せ問題のときと同様に
(1+x^{b_1}+x^{2b_1}+\cdots)(1+x^{b_2}+x^{2b_2}+\cdots) \cdots (1+x^{b_n}+x^{2b_n}+\cdots)
になります。これも簡単な形に変形できそうにないので
\prod_{t=1}^{i} (1+x^{b_i}+x^{2b_i}+\cdots) = \sum_{j=0}^{\infty} f(i,j) x^j
として $f(i,j)$ の漸化式を求めます。
\sum_{j=0}^{\infty} f(i,j) x^j = (1+x^{b_i}+x^{2b_i}+\cdots)\sum_{j=0}^{\infty} f(i-1,j) x^j
を読みやすいように一時的に $d_j = f(i-1, j), e_j = f(i, j)$ とおいて書き直すと
\begin{align}
\sum_{j=0}^{\infty} e_j x^j &= (1+x^{b_i}+x^{2b_i}+\cdots) \sum_{j=0}^{\infty} d_j x^j \\
&= \frac{1}{1 - x^{b_i}} \sum_{j=0}^{\infty} d_j x^j \\
\end{align}
分母を払うために両辺に $1 - x^{b_i}$ を掛けて
\begin{align}
左辺 &= (1 - x^{b_i}) \sum_{j=0}^{\infty} e_j x^j \\
&= \sum_{j=0}^{\infty} e_j x^j - \sum_{j=0}^{\infty} e_j x^{j+b_i} \\
&= \sum_{j=0}^{\infty} e_j x^j - \sum_{j=0}^{\infty} e_{j-b_i} x^j \\
&= \sum_{j=0}^{\infty} (e_j - e_{j-b_i}) x^j \\
右辺 &= \sum_{j=0}^{\infty} d_j x^j
\end{align}
両辺の $x^j$ の係数を比較すると
e_j - e_{j-b_i} = d_j
よって
e_j = e_{j-b_i} + d_j
$f$ での表現に戻すと
f(i, j) = f(i, j-b_i) + f(i-1, j)
という漸化式が求められました。
枚数制限あり両替問題
次は各種類iで枚数に上限 $a_i$ ありの問題を考えましょう。
前と同様に
\prod_{t=1}^{i} (1+x^{b_i}+x^{2b_i}+\cdots+x^{a_i b_i}) = \sum_{j=0}^{\infty} f(i,j) x^j
とおいて漸化式を求めます。
\sum_{j=0}^{\infty} f(i,j) x^j = (1+x^{b_i}+x^{2b_i}+\cdots+\cdots+x^{a_i b_i})\sum_{j=0}^{\infty} f(i-1,j) x^j
を読みやすいように一時的に $d_j = f(i-1, j), e_j = f(i, j)$ とおいて書き直すと
\begin{align}
\sum_{j=0}^{\infty} e_j x^j &= (1+x^{b_i}+x^{2b_i}+\cdots+\cdots+x^{a_i b_i}) \sum_{j=0}^{\infty} d_j x^j \\
&= \frac{1 - x^{(a_i +1)b_i}}{1 - x^{b_i}} \sum_{j=0}^{\infty} d_j x^j \\
&分母を払うために両辺に 1 - x^{b_i} を掛けて \\
左辺 &= (1 - x^{b_i}) \sum_{j=0}^{\infty} e_j x^j \\
&= \sum_{j=0}^{\infty} e_j x^j - \sum_{j=0}^{\infty} e_j x^{j+b_i} \\
&= \sum_{j=0}^{\infty} e_j x^j - \sum_{j=0}^{\infty} e_{j-b_i} x^j \\
&= \sum_{j=0}^{\infty} (e_j - e_{j-b_i}) x^j \\
右辺 &= (1 - x^{(a_i +1)b_i}) \sum_{j=0}^{\infty} d_j x^j \\
&= \sum_{j=0}^{\infty} d_j x^j - x^{(a_i +1)b_i} \sum_{j=0}^{\infty} d_j x^j \\
&= \sum_{j=0}^{\infty} d_j x^j - \sum_{j=0}^{\infty} d_j x^{j+(a_i +1)b_i} \\
&= \sum_{j=0}^{\infty} d_j x^j - \sum_{j=0}^{\infty} d_{j-(a_i +1)b_i} x^j \\
&= \sum_{j=0}^{\infty} (d_j - d_{j-(a_i +1)b_i}) x^j
\end{align}
両辺の $x^j$ の係数を比較すると
e_j - e_{j-b_i} = d_j - d_{j-(a_i +1)b_i}
よって
e_j = e_{j-b_i} + d_j - d_{j-(a_i +1)b_i}
$f$ での表現に戻すと
f(i, j) = f(i, j-b_i) + f(i-1, j) - f(i-1, j-(a_i +1)b_i)
という漸化式が求められました。
m進法
m進法で自然数を一意に表すことができますが、そのことを母関数を使っても説明できます。
m進法は両替問題で $m^i$円硬貨が $m-1$枚あるケースにあたります。（ここでは扱いやすいように i は 0からにします）
この問題の答えの数列の母関数は
$ (1+x+x^2+ \cdots +x^{m-1}) (1+x^m+x^{2m}+ \cdots +x^{(m-1)m}) (1+x^{m^2}+x^{2m^2}+ \cdots +x^{(m-1)m^2}) (1+x^{m^3}+x^{2m^3}+ \cdots +x^{(m-1)m^3}) \cdots $
になります。
\begin{align}
1+x^{m^i}+x^{2m^i}+ \cdots +x^{(m-1)m^i} &= \frac{1 - x^{(m-1+1)m^i}}{1 - x^{m^i}} \\
&= \frac{1 - x^{m^{i+1}}}{1 - x^{m^i}}
\end{align}
なので、母関数は
\begin{align}
&\frac{1 - x^m}{1 - x} \cdot \frac{1 - x^{m^2}}{1 - x^m} \cdot \frac{1 - x^{m^3}}{1 - x^{m^2}} \cdot \cdots \\
&ちょうど隣同士の分子分母で約分し合って先頭の分子の 1 - x だけ残り \\
&= \frac{1}{1 - x} \\
&= 1 + x + x^2 + x^3 + \cdots
\end{align}
と、すべての $x^i$ の係数が 1、つまり i の m進法での表し方が必ずちょうど一通りあることがわかります。
おわりに
有名な数列の母関数とこの記事を書くにあたって調べたときに興味を持った話題をいくつか紹介します。
指数的母関数
別の種類の母関数に指数的母関数
\sum_{k=0}^{\infty} \frac{c_k}{k!} x^k
というのがあります。
有名な数列の母関数をいくつか紹介
フィボナッチ数
フィボナッチ数 の母関数は
\frac{1}{1 - x - x^2}
カタラン数
カタラン数 の母関数は
\frac{1 - \sqrt{1 - 4x}}{2x}
分割数
分割数 の母関数は
\prod_{k=1}^{\infty} \frac{1}{1 - x^k}
Bell数
ベル数 の指数型母関数は
\frac{1}{e} e^{e^x}
Polyaの定理
今回の記事ででてきた母関数は一変数でしたが、Polyaの定理 では多変数のある種の母関数がでてきます。
species 圏論化
母関数を圏論化する種(species)の理論というのがあるらしいです。
参考
- 「重複組合せ 母関数」、「両替問題 母関数」、「競技プログラミング 母関数」、「競技プログラミング 形式的冪級数」などでググる
- 母関数の考え方
- いかにして問題をとくか （第2版第4部20番目の問題が1ドル両替問題で母関数を使って解いているらしい。読んでないけど）
- コンピュータの数学 （7章に母関数が載っているらしい。読んでないけど）
- TAOCP(The Art of Computer Programming) （1.2.9項に母関数が載っているらしい。読んでないけど）