形式的冪級数による写像12相の導出

この記事の概要

この記事では、主に競技プログラミングに（最終的に）応用する目的で、場合の数を数え上げる方法について議論します。
具体的には、「形式的冪級数」という理論的な道具を用いることで場合の数を系統的に表すことを題材とします。

ここでは、数え上げの基礎である「写像１２相」を形式的冪級数を用いて再導出してみます。これは形式的冪級数に慣れる為の練習問題にすぎませんが、より一般の問題を解く上での足がかりになるのではないかと思います。

写像12相と形式的冪級数を初めて見る方は、記事末尾の参考文献をご覧ください。

改行箇所の不具合について

筆者の環境ではタブレットで表示した時に意図していない箇所で改行される不具合が見つかっています。読みづらかったらすみません。

写像12相について簡単におさらい

$n$ 個の対象（例：物体、概念、生物など）を $m$ 個の状態¹（例：ある位置に存在する、ある速度を持っている、ある容器に入っているなど）に見出す場合の数を数えましょう。(よく、$n$ 個のボールを $m$ 個の箱に入れる方法の数で説明されます。) 一般に、一つの対象を複数の状態に見出すことは無いとします。（一つのボールを異なる箱に同時に入れることはできません。） 一方、一つの状態が幾つの対象と結びつくか（一つの箱に幾つのボールを入れられるか）は以下の箇条書きの三番目の (i)-(iii) の場合分けがなされます。写像１２相は以下のように分類されます。

• $n$ 個の対象は (1) 区別できない場合や (2) 区別できる場合が有り得ます。
• $m$ 個の状態も (A) 区別ができる状態や (B) 区別のできない状態が考えられます。
• 更に、各々の状態を占有できる対象の数が (i) 0 個以上 1 個以下の場合、(ii) 0 個以上いくらでも（制限無し）の場合、(iii) 1 個以上いくらでもの場合が典型的に議論されます。

これら $2 \times 2 \times 3 = 12$ 通りのセットアップでの場合の数を求める問題が、写像１２相と呼ばれています。

形式的冪級数について簡単におさらい

対象（ボールとか） $x$ がある一つの状態に $i$ 個存在する状況を $x^i$ で表すことにします。² $x$ は具体的な値を持つ数というよりは形式的に取り扱う変数という感じです。$a_i x^i$ と書いた時に係数 $a_i$ がこの状況を実現する場合の数を表すことにします。

一般に、対象が 0 個、1 個、2 個、…存在する場合が考えられるので、以下の形式的冪級数（無限級数）の形で表すことができます。

f(x) = \sum_{i = 0}^{\infty} a_i x^i

$x$ の値によっては、この級数はそもそも収束するとは限らず、関数 $f(x)$ が適切に定義できるか非自明である事に注意してください。そういった事を一切気にせず「形式的に」冪級数を操作するのが形式的冪級数の便利さです。

$n$ 個の対象が存在する場合の数は以下のように記述します。

\begin{align}
[x^n] \, f(x) &\left( = \frac{1}{n!} \left. \frac{\mathrm{d}^n f(x)} {\mathrm{d}x^n}\right|_{x = 0} \right)  \\
&= a_n
\end{align}

括弧内の式について

括弧内の式は $f(x)$ の $n$ 階微分を $n$ の階乗（$n!=\\prod_{i=1}^n i$（ただし $0! = 1$））で割ったものです。普通の関数の場合、そもそも微分可能かという所から考える必要があるかと思いますが、形式的冪級数を考える上では形式的に $n$ 次の係数をとってくる操作として捉える事ができます。以下、この式は使いませんので、微分に詳しくない方は無視して構いません。

形式的冪級数を用いるコツとして、背反な場合を和、独立な場合を積として表すことが挙げられるでしょう。

以下の立式で、問題の条件を満たすためには背反性や独立性が成り立たないのではないかと疑問に思われるかもしれません。ポイントは、まずあらゆる可能な場合を考えてから、$[x^n]$ などを作用させて特定の冪を抜き出した後に元々の問題の答えが得られればいいということです。

以下では、状態（箱）が一つとは限らず複数（0個以上）存在する場合について考えます。

1. 状態が区別できる場合

状態（箱とか）が区別できるので、状態毎に独立に考えます。よって、状態毎に冪級数を考えてその積をとります。

1-A. 対象が区別できない場合

区別のできな対象（ボールとか） $x$ を考えます。

1-A-i. 状態ごとの占有数: 1 個以下

一つの状態（箱）に対象を 0 個入れる場合は $x^0 = 1$、1 個入れる場合は $x^1 = x$ と表します。0 個でありかつ 1 個であるということはないので、これらは背反であり足すことができます。また、$m$ 種類の状態毎に同じ考察をすればよいので、$(1+x)$ を $m$ 乗した冪級数を考えれば良いです。

\begin{align}
[x^n] (1 + x)^m =& [x^n] \sum_{i=0}^{m} {}_m C_i x^i \\ 
=& {}_m C_n
\end{align}

最初の等号で二項定理 $(a + b)^m = \sum_i {}_m C_i a^{m-i} b^{i}$ を用いました。

さて、この場合の数を $n$ や $m$ に関して数列と見ると、形式的冪級数はこの数列の生成母関数になっていると言えます。数列が満たす線形漸化式は形式的冪級数の分母と深い関係にあることが maspy さんの記事 で説明されています。上記の結果では分母がありませんが、比較的簡単に二項係数の漸化式を（組み合わせ論的な考察を経ずに、形式的な式変形操作だけで）求めることができます。元々は $n$ に関しての冪展開だったわけですが、ここでは $m$ についての数列として考えてみます。

\begin{align}
[x^n] (1 + x)^m =& [x^n] (1 + x)(1+x)^{m-1} \\
 =& [x^n](1 + x)^{m-1} + [x^{n-1}](1+x)^{m-1}
\end{align}

二つ目の等号で、 $[x^n] , x , f(x) = [x^{n-1}] , f(x)$ を使いました。さて、最左辺と最右辺を見比べ上記の結果を使うと、この結果はまさに二項係数の漸化式を表しています。

{}_m C_n  = {}_{m-1} C_n + {}_{m-1} C_{n-1}

競技プログラミング用のコメントをすると、漸化式が分かれば動的計画法によって各 $n$, $m$ での数え上げの値を順番に求めていくことができます。

1-A-ii. 状態ごとの占有数: 0 個以上

同様に、２個以上に相当する高次の項を足していけば良いです。

\begin{align}
[x^n] \left(\sum_{i=0}^\infty x^i \right)^m =& [x^n] \frac{1}{(1-x)^m} \\
=& {}_{n+m-1} C_n　(= {}_m H_n)
\end{align}  

一つ目の等号で、等比級数の和の公式を使って無限急数を形式的に足し上げました。二つ目の等号では、負の二項定理を使いました。

無限等比級数の形式的な和

\sum_{i = 0}^\infty r^i \left(= 1 + r + r^2 + r^3 + \cdots \right) =  \frac{1}{1 - r}

(負の)二項定理
二項係数の具体形に負の数を代入すると、負冪の場合にも二項定理が使えます。

\begin{align}
(a + b)^{m} =& \sum_{i = 0}^{m} \frac{(m)(m-1)\cdots (m-i+1)}{i! } a^{m-i} b^i 
= \sum_{i = 0}^m {}_{m}C_i a^{m-i} b^i \\
(a + b)^{-m} =& \sum_{i = 0}^{\infty} \frac{(-m)(-m-1)\cdots (-m-i+1)}{i! } a^{-m-i} b^i 
= \sum_{i = 0}^\infty {}_{m+i-1}C_i a^{-m-i} (-b)^i 
\end{align}

($b = 0$ 周りで Laurent 展開すると確かめられます。)

漸化式を確認しましょう。

\begin{align}
[x^n] \frac{1}{(1-x)^{m-1}} =& [x^n] \frac{1-x}{(1-x)^m} \\
=& [x^n] \frac{1}{(1-x)^m} - [x^{n-1}] \frac{1}{(1-x)^m}
\end{align}

移項すると、以下の式に対応します。

{}_{n+m-1} C_n = {}_{n+m-2} C_{n} + {}_{n+m-2}C_{n-1}

\left( {}_{m} H_n = {}_{m-1} H_{n} + {}_{m}H_{n-1}\right)

1-A-iii. 状態ごとの占有数: 1 個以上

0 個に相当する $x^0 = 1$ の部分を削除するだけです。

\begin{align}
[x^n] \left(\sum_{i=1}^\infty x^i \right)^m =& [x^n] \frac{x}{(1-x)^m} \\
=& {}_{n-1} C_{n-m}
\end{align}

$[x^n] \frac{x}{(1-x)^m} = [x^{n-1}] \frac{1}{(1-x)^m}$ となり 1-A-ii の場合に帰着します。

1-B. 対象が区別できる場合

異なる $n$ 種類の対象（ボール）を一つずつ選ぶ場合を考えます。ここでも $x$ の冪だけを用いて形式的冪級数を考えることができるかもしれませんが、$n$ 種類の対象に応じて $n$ 種類の変数 $x_1, x_2, ..., x_n$ を導入してみましょう。

1-B-i. 状態ごとの占有数: 1 個以下

一つの箱に一個も入れない時は、これまで同様 $1$ で、一個入れる場合は $n$ 通りの可能性を足し上げる必要があります。

[x_1 x_2 \dots x_n] \left( 1 + x_1 + x_2 + \dots + x_n \right)^m = {}_m P_n

漸化式を確認します。

\begin{align}
&[x_1 x_2 \dots x_n] \left( 1 + x_1 + x_2 + \dots + x_n \right)^m \\
=& [x_1 x_2 \dots x_n] \left( 1 + x_1 + x_2 + \dots + x_n \right)^{m-1}  \left( 1 + x_1 + x_2 + \dots + x_n \right) \\
=& [x_1 x_2 \dots x_n] \left( 1 + x_1 + x_2 + \dots + x_{n} \right)^{m-1} + \sum_i [x_1 x_2 \dots x_n] \left( 1 + x_1 + x_2 + \dots + x_{n} \right)^{m-1} x_i \\
=& [x_1 x_2 \dots x_n] \left( 1 + x_1 + x_2 + \dots + x_{n} \right)^{m-1} + n [x_1 x_2 \dots x_{n-1}] \left( 1 + x_1 + x_2 + \dots + x_{n-1} \right)^{m-1}
\end{align} 

これは

{}_m P_n = {}_{m-1}P_{n} + n \, {}_{m-1} P_{n-1}

に対応しています。

1-B-ii. 状態ごとの占有数: 0 個以上

\begin{align}
[x_1 x_2 \dots x_n] \left( \prod_{i=1}^n \sum_{j=0}^\infty x_i^j  \right)^m =&  [x_1 x_2 \dots x_n]  \prod_{i=1}^n (1 + x_i)^m \\
=& m^n
\end{align}

途中計算で、$[x_1 x_2 ... x_n]$ が作用していることを考慮して、関係ない冪の部分が変わっても構わないという変形をしました。

自明ですが漸化式を求めます。

[x_1 x_2 \dots x_n]  \prod_{i=1}^n (1 + x_i)^m =   \prod_{i=1}^n [x_i] \left( (1 + x_i)^{m-1}  +  x_i (1 + x_i)^{m-1} \right) 

これは

m^n = (m - 1 + 1)^n

を表しています。

1-B-iii. 状態ごとの占有数: 1 個以上

通常は包除原理を使って導出するところですが、形式的冪級数を使いましょう。
全通りから 0 個の場合を引いて考えます。

\begin{align}
[x_1 x_2 \dots x_n] \left( \prod_i \left( \sum_{j = 0}^\infty x_i^j \right) - 1 \right)^m = & [x_1 x_2 \dots x_n] \left( \frac{1}{\prod_i (1-x_i) } - 1 \right)^m \\
=& [x_1 x_2 \dots x_n] \sum_{i = 0}^m \frac{{}_m C_i (-)^{m-i}}{\prod_j (1 - x_j)^i} \\
=& \sum_{i=0}^m {}_m C_i (-)^{m-i} \prod_j [x_j] \frac{1}{1- i x_j+ \dots} \\ 
=& \sum_{i=0}^m {}_m C_i (-)^{m-i} i^n
\end{align}

漸化式を求めます。上の式を仮に $X(n, m)$ と呼ぶとすると、

X(n, m) = m \sum_{i=0}^{n-1} {}_{n-1} C_{i} \, X(i, m-1)

が成り立っていることが確認できます。

2. 状態が区別できない場合

状態（箱）が区別できない場合は、無限級数の和を実行して具体的な表式を求めるのが困難になってきます。
状態毎に独立に考えることができなくなるので、$k$ 個の対象に占有されている状態の数 $i$ を数えるという方針をとります。

2-A. 対象が区別できない場合

$n$ 個の対象（ボール）を任意個の状態（箱）に分配する場合の数は、整数 $n$ を自然数の和に分割する場合の数と同じで、分割数として知られています。maspy さんのブログ で解説されているように、$k$ 個の対象を含む状態が $i = 0, 1, 2, 3, \dots$ 種類あると、 $(1 + x^{k} + x^{2k} + x^{3k} + \cdots)$ と表せます。全ての整数 $k$ についてこの場合分けがあるので、分割数は以下のように求められます。

[x^n] \prod_{k = 1}^\infty \sum_{i=0}^\infty x^{ki} = [x^n] \prod_{k=1}^\infty \frac{1}{1-x^k} 

以下では、$m$ 種類の状態に分配するという情報を管理する為に新しい変数 $y$ を導入します。$y$ の冪が状態の個数を表します。

2-A-i. 状態ごとの占有数: 1 個以下

一つの状態に分類される対象の数が1個以下の場合です。

\begin{align}
[x^n y^m] \prod_{k = 0}^1 \sum_{i=0}^\infty x^{ki}y^i
=& \frac{1}{(1-y)(1 - x y)} \\
=& \begin{cases}
1 & (n \leq m) \\
0 & (n > m)
\end{cases}
\end{align} 

1 と 0 しかないので、さすがに漸化式は省略します。

2-A-ii. 状態ごとの占有数: 0 個以上

前のセクションで各状態に入る対象の個数が $k=1$ までだった所を無限大までの積にします。

[x^n y^m] \prod_{k = 0}^\infty \sum_{i=0}^\infty x^{ki}y^i
= [x^n y^m]\prod_{k=0}^\infty \frac{1}{1 - x^k y}

漸化式を求めます。 $\frac{1}{1-y} = 1 + \frac{y}{1-y}$ を使います。また、展開の片方の項で $y = x/z$ ($z = x y$) と変数変換します。

\begin{align}
[x^n y^m]\prod_{k=0}^\infty \frac{1}{1 - x^k y} =& [x^n y^m]\left( 1 + \frac{y}{1-y} \right) \prod_{k=1}^\infty \frac{1}{1 - x^k y} \\
=& [x^{n-m} z^m]\prod_{k=0}^\infty \frac{1}{1 - x^k z} + [x^n y^{m-1}] \prod_{k=0}^\infty \frac{1}{1 - x^k y} 
\end{align}

整数 $n$ を丁度 $m$ 個の 0 以上の数に分割する方法（= $m$ 個以下の 1 以上の数に分割する方法）の数を $P(n, m)$ と書くことにすると³、上の式は以下の漸化式を表しています。

P(n, m) = P(n-m, m) + P(n, m-1) 

2-A-iii. 状態ごとの占有数: 1 個以上

上の場合で $k = 0$ の場合を除外したものです。

[x^n y^m] \prod_{k = 1}^\infty \sum_{i=0}^\infty x^{ki}y^i
= [x^n y^m]\prod_{k = 1}^\infty \frac{1}{1 - x^k y} 

$[x^n y^m]\prod_{k = 1}^\infty \frac{1}{1 - x^k y} = [x^n y^m]\prod_{k = 0}^\infty \frac{1}{1 - x^k y} - [x^n y^{m-1}]\prod_{k = 0}^\infty \frac{1}{1 - x^k y} $ となり前のセクションの冪級数の線型結合に帰着します。整数 $n$ を丁度 $m$ 個の 1 以上の数に分割する方法の数を $P_{\geq 1}(n, m)$ と書くことにすると、前のセクションの $P(n, m)$ （$P_{\geq 0} (n, m)$ と書く方が分かりやすいか）を用いて、

\begin{align}
P_{\geq 1}(n, m) =& P(n, m) - P(n, m-1) \\
=& P(n-m, m)
\end{align}

と書く事ができます。一行目は、上の冪級数の式に対応しています。 $P$ を第二引数 $m$ についての数列と見たときに $P_{\geq 1}$ が $P$ の階差数列として得られるということを表しており、逆に言うと $P_{\geq 1}$ の累積和が $P$ であるとも言えます。二つ目の等号は 2-A-ii の漸化式と組み合わせて得ました。後の便利の為に、$P_{\geq 1}(n, m)$ だけの漸化式も書いておきます。

P_{\geq 1}(n, m) = P_{\geq 1}(n - m, m) + P_{\geq 1}(n-1, m-1) 

2-B. 対象が区別できる場合

再び $x_i$ $(i = 1, 2, ..., n)$ を導入します。

2-B-i. 状態ごとの占有数: 1 個以下

考え方は大体 2-A と同様です。

\begin{align}
& [x_1 x_2 \cdots x_n y^m] \left( \sum_{\ell=0}^\infty y^\ell \right) \left(1 + y \sum_i x_i + y^2 \sum_{i < j} x_i x_j + \cdots + y^n x_1 x_2 \cdots x_n \right) \\ 
=& [x_1 x_2 \cdots x_n y^m] \frac{y^n}{1-y} x_1 x_2 \cdots x_n \\
=&  \begin{cases} 
1 & (n \leq m) \\
0 & (n > m) 
\end{cases}
\end{align} 

$x$ の積で大小関係を導入しているのは、重複して数えないようにする為です。

2-B-ii. 状態ごとの占有数: 0 個以上

集合 $S = \{ 1, 2, \dots, n \}$, その部分集合 $T = \{ a_1, a_2, \dots, a_t \}$
を考えます。

\begin{align}
& [x_1 x_2 \cdots x_n y^m] \prod_{T \in S} \sum_{k= 0}^\infty \left( x_{a_1} \cdots x_{a_t} y\right)^{k}  \\
=& [x_1 x_2 \cdots x_n y^m]\prod_{p_1 = 0}^1 \prod_{p_2 = 0}^1 \cdots \prod_{p_n = 0}^1 \frac{1}{1 - x_1^{p_1} x_2^{p_2} \cdots x_n^{p_n} y } 
\end{align}

（ちなみに $p_i$ ($i = 1, 2, \dots, n$) が 0 から 1 までのところを無限まで走らせても結果は変わりません。その式でいきなり立式しても良いでしょう。）
これが満たす漸化式の簡単な見つけ方が分かりませんが、$n$ を一つ減らす式変形をします。

\begin{align}
=& [x_1 x_2 \cdots x_n y^m]\prod_{p_1, \dots, p_n} \frac{1}{(1 - x_1^{p_1} x_2^{p_2} \cdots x_{n-1}^{p_{n-1}} y)(1 - x_1^{p_1} x_2^{p_2} \cdots x_n y) } \\
=& [x_1 x_2 \cdots x_n y^m]\prod_{p_1, \dots, p_n} \frac{1 + x_1^{p_1} x_2^{p_2} \cdots x_n y}{(1 - x_1^{p_1} x_2^{p_2} \cdots x_{n-1}^{p_{n-1}} y) } 
\end{align} 

$x^n$ の一次を持ってこないといけないので、$2^n$ 個の積のうち唯一つから $x^n$ の入った項を選ぶ必要があります。関係ある項をまとめると $2^n$ 個の項の和として書けます。更に、形式的冪級数の変数は最終的な答えに入らないダミー変数なので、$x_{a_1} x_{a_2} \cdots x_{a_i}$ という $i$ 次の項毎にまとめることができます。これらを考慮すると、以下のように式変形できます。

= \sum_{i=0}^{n-1} {}_{n-1} C_i [x_1 x_2 \cdots x_i y^{m-1}] \prod_{p_1, \dots, p_i} \frac{1}{1 - x_1^{p_1} \cdots x_i^{p_i}y}  

この見た目から Bell 数 $B(n, m)$ と一致したとは結論付けづらいので、一旦チルダをつけて $\tilde{B}(n, m)$ と書くことにします。上の式は以下の漸化式を表しています。

\tilde{B}(n, m) = \sum_{i=0}^{n-1} {}_{n-1} C_i \, \tilde{B}(i, m-1)

これは Bell 数が満たす漸化式として比較的よく知られている

B(n) = \sum_{i=0}^{n-1} {}_{n-1} C_i \, B(i)

と同様の形をしています。ここで $B(n) = B(n, n)$ もまた Bell 数と呼ばれがちな量です。$m \geq n$ に対して $B(n,m) = B(n)$ なので、上の $\tilde{B}(n, m)$ の漸化式は $\tilde{B}(n, m) = B(n, m)$ のはずであるという事と整合的です。

次のセクションで Bell 数が Stirling 数の累積和であることと Stirling 数の漸化式を導きます。$n$, $m$ に関しての二つの独立な漸化式が一致し、初項が $\tilde{B}(n, 0) = \delta_{n,0}$、$\tilde{B} (0, m) = \delta_{m, 0}$ （$\delta_{a, b}$ は Kronecker のデルタ）を満たすので $\tilde{B}(n, m) = B(n, m)$ が結論できるでしょう。

2-B-iii. 状態ごとの占有数: 1 個以上

上の場合で $T$ が空集合な場合を除きます。

\begin{align}
& [x_1 x_2 \cdots x_n y^m] \prod_{T \neq \varnothing} \sum_{k=0}^\infty \left( x_{a_1} \cdots x_{a_t} y\right)^k \\
 =& [x_1 x_2 \cdots x_n y^m] (1-y) \prod_{p_1 = 0}^1 \prod_{p_2 = 0}^1 \cdots \prod_{p_n = 0}^1 \frac{1}{ 1 - x_1^{p_1} x_2^{p_2} \cdots x_n^{p_n} y } 
\end{align} 

2-B-ii と比べると $(1-y)$ が全体にかかっています。これは、Bell 数の数列の階差数列が Stirling 数の数列であること、つまり Stirling 数の累積和が Bell 数であることと整合的です。（厳密に言うと、$(1-y)$ を前に出す所で $n > 0$ を仮定しました。$n = 0$ のときは $[y^m] 1 = \delta_{m, 0}$ です。）

式で書くと、

B(n, m) = \sum_{i=0}^m S(n, i)

に相当します。

累積和や階差数列に相当する形式的冪級数

一般に、

\begin{align}
[x^n] \frac{1}{1-x} \, f(x) =& \sum_{i=-\infty}^n [x^i] \, f(x) \\
[x^n] (1-x) \, f(x) =& [x^n] \, f(x) - [x^{n-1}] \, f(x)
\end{align}  

が成り立ちます。（$f(x)$ が負冪を含んでいても良いように書きましたが、含まない場合は和の下限を $0$ とできます。）

まだ漸化式を確認していないので、一応上記の結果を $\tilde{S}(n, m)$ のようにチルダをつけて Stirling 数 $S(n, m)$ と区別しておき、$\tilde{S}(n, m) = S(n, m)$ を示すべく漸化式を考えます。まず、前のセクション 2-B-ii の Bell 数の満たしていた式と全く同じ形の漸化式

\tilde{S}(n, m) = \sum_{i=0}^{n-1} {}_{n-1} C_i \, \tilde{S}(i, m-1)

を満たしています。

Stirling 数は、例えばけんちょんさんの記事で解説されているように、$S(n, m) = S(n-1, m-1) + m , S(n-1, m)$ という漸化式も満たします。以下、$\tilde{S}(n,m)$ も同じ形の漸化式を満たすことを数学的帰納法で示します。

初項として $\tilde{S}(n, 0) = \delta_{n, 0}$、$\tilde{S}(0, m) = \delta_{m, 0}$ を満たしていることはすぐに分かります。示したい式の右辺に二項係数が入ってる方の漸化式を適用してから帰納法の仮定を使います。

\begin{align}
\tilde{S}(n-1, m-1) + m \, \tilde{S}(n-1, m) =& \sum_{i = 0}^{n-2} {}_{n-2} C_i \left( \tilde{S}(i+1, m-1) + \tilde{S}(i, m-1)\right) \\
=& \sum_{i=0}^{n-1} \left( {}_{n-2} C_{i-1} + {}_{n-2} C_i \right) \tilde{S}(i, m-1) \\
=& \sum_{i=0}^{n-1} {}_{n-1}C_i \tilde{S}(i, m-1) \\ 
=& \tilde{S}(n, m)   
\end{align} 

同じ初項と漸化式が得られたということで $\tilde{S}(n, m) = S(n, m)$ と結論します。

まとめ

12 種類の形式的冪級数による表記をまとめると表のようになります。⁴ 一部、他のマスとの対応が見やすくなるように本文と等価な異なる表式を用いている部分があります。本文で見てきたように、これらはよく知られた写像１２相の結果を再現します。

\begin{array}{l:l:l:l:l}
\hline
\text{状態の区別} & \text{対象の区別} & 0-1 \text{個 (i)} & 0 \text{個以上 (ii)} &  1 \text{個以上 (iii)} \\ \hline
\text{しない (1)} & \text{しない (A)} & [x^n] (1+x)^m & [x^n](1-x)^{-m} & [x^n]x (1-x)^{-m}  \\ \hline
\text{しない (1)}  & \text{する (B)} & [\prod_i^n x_i] (1 + \sum_j^n x_j)^m & [\prod_i^n x_i] \prod_j^n (1 - x_j)^{-m} & [\prod_i^n x_i] \left(\frac{1}{\prod_j^n (1- x_j)} - 1 \right)^m \\ \hline
\text{する (2)}  & \text{しない (A)} & [x^n y^m](1-y)^{-1}(1-xy)^{-1}  & [x^n y^m] \prod_{k=0}^\infty (1-x^k y)^{-1} &  [x^n y^m] \prod_{k=1}^\infty (1-x^k y)^{-1} \\ \hline
\text{する (2)}  & \text{する (B)} & [\prod_i^n x_i y^m]y^n (1-y)^{-1}(1 + \prod_j^n x_j + \cdots) & [ \prod_i^n x_i y^m] \prod_{p_1,\dots, p_n}^\infty  (1- y \prod_j^n x_j^{p_j})^{-1} & [\prod_i^n x_i y^m](1-y) \prod_{p_1,\dots, p_n}^\infty  (1- y \prod_j^n x_j^{p_j})^{-1}  \\ \hline
\end{array}

対象が区別できる場合に複数の変数 $x_1, x_2, ..., x_n$ を、また、状態が区別できない場合に状態の数を表す変数 $y$ を持ち込んでしまいました。もっと簡潔な記述をするための一般論はあるでしょうか。⁵
もっとも、写像１２相の場合は組み合わせ論的な考え方での導出がよく知られているので、それらを使えばよいでしょう。

より難しい数え上げ問題に対して形式的冪級数を使って考察を進められるようになると良いですね。未知の数え上げの問題が出てきたときに、形式的冪級数で立式し、簡単な形に式変形したあと、漸化式を見出し、動的計画法を使うという道筋になるでしょう。難しい問題では、更に動的計画法の高速化や他のアイディアとの組み合わせなどを考える必要があるかもしれません。

参考文献

写像12相

競プロにおける形式的冪級数

写像12相と形式的冪級数

1. maspy さんの記事の「状態」とは異なる意味で使っています。maspy さんの記事での数え上げの「状態」は、ここでは単純に（場合の数の）「場合」と呼んでいます。 ↩

2. 対応を分かりやすくする為に対象の名前と変数の名前を揃えましたが、これが分かりづらいという方は適当に異なる文字を使ってください。また、$[x^n]f(x)$ として特定の冪の係数を抜き出したもの ($a_n$) は $x$ には依存していません。こういった変数をダミー変数と呼び、好きな文字に書き換えても結果は変わりません。(例えば
   $[x^n]\, f(x) = [y^n]f(y)$。) ↩

3. 異なる文献で異なる定義をしているかもしれないので注意してください。 ↩

4. Markdown 形式の表の中で数式を使う方法を教えてください。あと表が見切れている場合は横にスクロールできます。 ↩

5. 参考文献の「写像12相と形式的冪級数」にある Sen さんのブログで単一変数 $x$ を使う方法が紹介されています。私はよく分かっていません。 ↩