(cache)[多項式・形式的べき級数]数え上げとの対応付け

概要
例題
1. 分配法則に基づく説明
2. 状態の遷移を多項式で表す
問題演習
高次元の状態遷移

概要

ある種の数え上げの計算は、多項式・形式的べき級数に対する計算と結び付けることができます。数え上げの問題を、多項式・形式的べき級数に対する計算と読み替えて、代数的な式変形により答を得る手法が、競技プログラミングにおいても注目され始めているようです。

さまざまな問題を文字式の問題に翻訳できるようになっておけば、文字式に対して理解を深めるだけで、幅広い問題に対する解決力を同時に伸ばしてしまうことができます。また、中高数学の学習で学んだ文字式や関数の式変形に対する能力が利用できることも魅力になると思います。

ここでは、数え上げの対象を多項式・形式的べき級数の問題に対応させる練習をしていきましょう。（逆に言うと、対応させた先の「多項式・形式的べき級数の問題を解く」方法の説明は、この記事では扱いません。）

多項式への言い換えは、経験がないうちは、唐突に感じてしまうことがあると思いますが、頻出のパターンは限られており、少しの考え方を知っておくだけで多くの場面で適用できると思います。

考え方を形式的に説明することはやめて、どんどん問題例を並べていくという形で説明を進めていこうと思います。同様の例を繰り返し見ることで、おおよその考え方はつかめると思います。

「問題」では数え上げを問うていたりしますが、多項式・形式的べき級数と対応付けるところまでを「解答」としています。実際にそれをどう計算するかについては扱いません。

では，始めましょう．

例題

【問題１】
集合 $A = {2, 3}$ , $B = {2, 4}$ , $C = {3, 5, 7}$ がある。それぞれの集合から $1$ つずつ元 $a, b, c$ を選ぶ。 $a + b + c = n$ になるようにする方法は何通りあるでしょうか？

【解答】
$f = (x^{2} + x^{3}) (x^{2} + x^{4}) (x^{3} + x^{5} + x^{7})$ とするとき、 $f$ の $x^{n}$ の係数が答である。

以下、「 $f$ の $x^{n}$ の係数」という概念が頻発します。これを、 $[x^{n}] f$ と表すことにしていきます。したがって、次のような表記をとっていきます。

【解答】
$[x^{n}] (x^{2} + x^{3}) (x^{2} + x^{4}) (x^{3} + x^{5} + x^{7})$ が答である。

この解答に至る理由を、2つの方法で説明しましょう。

分配法則に基づく説明

一般に、 $(a_{1} + a_{2} + \dots) (b_{1} + b_{2} + \dots) (c_{1} + c_{2} + \dots)$ というような積を計算すると、 $a_{i} b_{j} c_{k}$ という形の積を全て 1 度ずつ加えたものが計算結果になります。今回の場合、

$x^{2}$ または $x^{3}$ を選ぶ
$x^{2}$ または $x^{4}$ を選ぶ
$x^{3}$ または $x^{5}$ または $x^{7}$ を選ぶ
選んだものの積を全て加える

ことで $f = (x^{2} + x^{3}) (x^{2} + x^{4}) (x^{3} + x^{5} + x^{7})$ が計算できます。選んだものを $x^{a}, x^{b}, x^{c}$ とすると、 $x^{a + b + c}$ が選んだものの積になり、したがって $[x^{n}] f$ は $a + b + c = n$ となるような $(a, b, c)$ の選び方の総数と一致します。

状態の遷移を多項式で表す

個人的には、こちらの考え方の方がよく使っている気がします。

状態ごとに何らかの値が計算されているときに、その計算結果を多項式の形で持ちます。この際、「多項式の次数」が「考えている状態」、「係数」が状態ごとの「計算した値」（多くの場合、数え上げ）を表すように多項式を持つのが原則です。

今回の問題では、「どのような和」が「何通りの方法で作れるか」を状態・値として多項式を更新していきましょう。

何も選んでいない状態 → $1$
集合 $A$ の要素を選ぶ → $x^{2} + x^{3}$
さらに集合 $B$ の要素を選ぶ → ？？？（ここが問題）
- $B$ から $2$ を選ぶ場合 → $(x^{2} + x^{3}) x^{2}$ .
- $B$ から $4$ を選ぶ場合 → $(x^{2} + x^{3}) x^{4}$ .
- あわせて → $(x^{2} + x^{3}) (x^{2} + x^{4})$ .

$B$ から選ぶのは、「状態を $+ 2$ する選択肢」と「状態を $+ 4$ する選択肢」です。このように、全ての状態を一斉に定数だけ変化させるような操作を、 $x^{n}$ をかけるという形で表すことができます。「そのような操作のうちいずれか 1 つを選んで、計算結果を足し合わせる」のですから、和をとればよいですね。続けていきましょう。

集合 $B$ まで選んだ時点で、多項式 $g$ を得ているとする。
さらに集合 $C$ の要素を選ぶ
- $C$ から $3$ を選ぶ → $g x^{3}$ .
- $C$ から $5$ を選ぶ → $g x^{5}$ .
- $C$ から $7$ を選ぶ → $g x^{7}$ .
- あわせて → $g (x^{3} + x^{5} + x^{7})$ .

$1$ つ選ぶことが、ある多項式をかける操作になっていますね。何も選んでいない状態が $1$ でしたから、 $A, B, C$ からの選択を経て、最終的に多項式 $(x^{2} + x^{3}) (x^{2} + x^{4}) (x^{3} + x^{5} + x^{7})$ の完成です。

さて、1 つ問題を消化しただけですが、この考え方 1 つでどんどん多項式による立式ができます。加速して、一気に問題を紹介していきましょう。

【問題２】
りんごを $2$ 個、みかんを $3$ 個、ぶどうが $4$ 個売られています。合計 $n$ 個買う方法は何通りあるでしょうか？

【解答】
$[x^{n}] (1 + x + x^{2}) (1 + x + x^{2} + x^{3}) (1 + x + x^{2} + x^{3} + x^{4})$

購入したものの個数を状態として、数え上げを係数にして、多項式を考えます。りんごに関する選択肢は、「0個、1個、2個」のいずれかで、これが $(1 + x + x^{2})$ と対応しています。同様にみかん、ぶどうによる遷移を考えて、状態 $n$ を取り出せば、答です。

【問題３】
りんご・みかん・ぶどうが無限にたくさん売られています。合計 $n$ 個買う方法は何通りあるでしょうか？（同種の果物同士は区別しない）

【解答】
$f = \sum_{n = 0}^{\infty} x^{n} = 1 + x + x^{2} + x^{3} + x^{4} + x^{5} + \dots$ （無限に続ける）とするとき、 $[x^{n}] f^{3}$ が答である。

りんごに対する選択肢に個数の上限がなく、「無限個項があるような多項式」（形式的べき級数）の登場です。

実際には、りんごを $n$ 個よりもたくさん買うような選択肢を考えなくてもよいので、多項式の範囲で記述することも可能です。

【解答】
$f_{n} = 1 + x + x^{2} + x^{3} + \dots + x^{n}$ とするとき、 $[x^{n}] f_{n}^{3}$ が答である。

考察は形式的べき級数として進めても、実装時には結局 $n$ 次以下のみを多項式として計算するような手順が一般的です。

問題演習

ネタバレに配慮して、解答の一部や、問題の出典を、伏字にしている場合があります。ドラッグ反転により確認してください。

「出典」を明示している場合でも、適当な要素だけを抜き出して改題していたり、数値を具体化して考えやすくしたりしている場合がほとんどです。

【問題４】
集合 $A = {a_{1}, a_{2}, \dots, a_{k}}$ が与えられている。 $n = a_{i} + a_{j}$ となるような $(i, j)$ は何通りあるか？（関連：ABC149-E、yukicoder No.723 など）

【解答】
$f = x^{a_{1}} + x^{a_{2}} + \dots + x^{a_{k}}$ とするとき、 $[x^{n}] f^{2}$ が答である。

【問題５】
$1$ から $N$ までの順に番号がついた $N$ 個のマス目が一直線に並んでいる。 $1$ 回の移動では、マス $x$ からマス $x + 2$ または $x + 3$ に移動できる。 $n$ 回の移動でゴールする移動方法を数え上げよ。（出典：第二回全国統一プログラミング王決定戦本戦 Fの一部分をとても簡単に改題）

【解答】
$[x^{N - 1}]$ $(x^{2} + x^{3})^{n}$ が答である。

あるいは、マス目番号を「状態」と見るならば、次の方が自然かもしれません。

【解答】
$[x^{N}]$ $x (x^{2} + x^{3})^{n}$ が答である。

【問題６】
問題５と同じ設定で、移動回数が何回でも良い場合の移動方法を数え上げよ。

【解答】
$\sum_{n = 0}^{\infty} [x^{N - 1}]$ $(x^{2} + x^{3})^{n}$ が答である。

無限和でもいいから、とにかく文字式の問題に帰着していきます。移動回数はせいぜい $(N - 1) / 2$ 程度なので、有限和で打ち切ってもよいです。

【問題７】
$1$ 円硬貨、 $5$ 円硬貨、 $10$ 円硬貨が無限にたくさんある。ちょうど $n$ 円を支払う方法は何通りあるか。

【解答】
$f_{1} =$ $\sum_{n = 0}^{\infty} x^{n}$ , $f_{5} =$ $\sum_{n = 0}^{\infty} x^{5 n}$ , $f_{10} =$ $\sum_{n = 0}^{\infty} x^{10 n}$ とするとき、 $[x^{n}] f_{1} f_{5} f_{10}$ が答である。

合計金額を状態とします。例えば $5$ 円硬貨の枚数を定めることは、状態遷移を $+ 0, + 5, + 10, + 15 \dots$ の中から選ぶことと対応します。

【問題８】
重さ $w_{1}$ の荷物、重さ $w_{2}$ の荷物、…、重さ $w_{k}$ の荷物が 1 つずつある。耐荷重 $W$ のかばんに詰め込む方法は何通りあるか。（詰め込む順序などは無視。1 つも選ばなくてもよい）

【解答】
$\sum_{n = 0}^{W} [x^{n}]$ $(1 + x^{w_{1}}) (1 + x^{w_{2}}) \dots (1 + x^{w_{n}})$ が答である。

積の記号 $a_{1} a_{2} \dots a_{n} = \prod_{i = 1}^{n} a_{i}$ （シグマ記号の積バージョン）を使って、次のように書いてもよいです。

【解答】
$\sum_{n = 0}^{W} [x^{n}] \prod_{i = 1}^{k}$ $(1 + x^{w_{i}})$ が答である。

【問題９】
$a_{1} + a_{2} + \dots + a_{8} = 6 N$ かつ、 $0 ≦ a_{i} ≦ N$ となるような整数の組 $(a_{1}, \dots, a_{8})$ は何通りあるか。（出典：yukicoder No.287 ）

【解答】
$f = \sum_{n = 0}^{N} x^{n}$ とするとき、 $[x^{6 N}] f^{8}$ が答である。

【問題１０】
$N$ 以下の相異なる $3$ つの素数の組 $(a, b, c)$ であって、 $a + b + c$ が素数になるものは何通りあるか。（出典：yukicoder No.732 で $a, b, c$ の順序制約をなくしたもの）

【解答】
$P_{N}$ を $N$ 以下の素数全体の集合とする。 $f =$ $\sum_{p \in P_{N}} x^{p}$ とするとき、 $\sum_{p \in P_{3 N}} [x^{p}] f^{3}$ が答である。

【問題１１】
$N$ を正の整数の和として表す方法を数え上げよ。ただし、和の順序の違いは区別する。

$N = 4$ なら、 $4, 1 + 3, 3 + 1, 2 + 2, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 1 + 1 + 1 + 1$ の $8$ 通りがあります。

【解答】
$f = x + x^{2} + x^{3} + x^{4} + \dots$ とするとき、 $[x^{N}] \sum_{n = 0}^{\infty} f^{n}$ が答である。

$n$ 個の和として作る方法を足し合わせています。なお、答は $2^{N - 1}$ という簡単な式になります。 $N - 1$ 回 $2$ 択を行う方法と対応付けることでも証明できますし、形式的べき級数の扱いで証明することも可能です。

【問題１２】
$N$ を正の整数の和として表す方法を数え上げよ。ただし、和の順序の違いは区別しない。

$N = 4$ なら、 $4, 1 + 3, 2 + 2, 1 + 1 + 2, 1 + 1 + 1 + 1$ の 5 通りがあります。このような数え上げ $p_{n}$ は、分割数と呼ばれています。

【解答】
各 $k$ に対して $f_{k} =$ $\sum_{i = 0}^{\infty} x^{k i}$ とするとき、 $[x^{N}] \prod_{k = 1}^{\infty} f_{k}$ が答である。

和の順序を区別しないところが厄介で、前問題と同じ立式は使うことができません。ではどのように数え上げ対象を区別するのかというと、それぞれの整数の使用回数です。「1を $a_{1}$ 個、2を $a_{2}$ 個、3 を $a_{3}$ 個、…」という見方をすればこの式になります。（例えば上述の 1円硬貨・5円硬貨・10円硬貨の問題と同じ）。

【問題１３】
$N$ を相異なる正の整数の和として表す方法を数え上げよ。和の順序の違いは区別しない。

【解答】
各 $k$ に対して $f_{k} =$ $(1 + x^{k})$ とするとき、 $[x^{N}] \prod_{k = 1}^{\infty} f_{k}$ が答である。

今度は $1, 2, 3, \dots$ のそれぞれの整数に対して、「1回使う・使わない」の2択を行っていくので、こうなります。

【問題１４】
$N, M$ を正の整数とする。整数の列 $A_{1}, \dots, A_{N}$ であって、
・ $0 < A_{1} ≦ A_{2} ≦ \dots ≦ A_{N} = M$
・任意の $1 ≦ i ≦ N - 1$ に対して $3 ≦ A_{i + 1} - A_{i} ≦ 5$
が成り立つようなものを数え上げよ。（出典：yukicoder No.802を少し易しく）

【解答】
$f =$ $\sum_{n = 1}^{\infty} x^{n}$ とし、 $g =$ $x^{3} + x^{4} + x^{5}$ とするとき、 $[x^{M}] f \cdot g^{N - 1}$ が答である。

$A_{1}, \dots, A_{N}$ の値が状態です。 $A_{1}$ まで選んだ時点では、状態 $1, 2, 3, \dots$ が $1$ 通りずつありえて、これを $f$ で表現しています。 1つ項が進むときに、状態を $+ 3, + 4, + 5$ する方法が1つずつあるので、ここは $g$ 倍で書けます。

あるいは、 $A_{0} = 0$ と考えて、初手のみ任意の正の大きさの状態遷移ができると考えてもよいでしょう。

【問題１５】
$N, M$ を正の整数とする。整数の列 $A_{1}, \dots, A_{N}$ であって、
・ $0 < A_{1} ≦ A_{2} ≦ \dots ≦ A_{N} < M$
・任意の $1 ≦ i ≦ N - 1$ に対して $3 ≦ A_{i + 1} - A_{i} ≦ 5$
が成り立つようなものを数え上げよ。（※問題１４とほぼ同じで、 $A_{N} < M$ にしました）

自然な 2 通りの方法があると思います。

【解答】
【問題１４】の解説と同様の $f, g$ をとったとき、 $\sum_{m = 0}^{M - 1}$ $[x^{m}] f g^{N - 1}$ が答である。

最終的な状態で場合分けして足し合わせていますね。

【解答】
【問題１４】の解説と同様の $f, g$ をとったとき、 $[x^{M}]$ $f \cdot g^{N - 1} \cdot f$ が答である。

$A_{N + 1} = M$ を補って、「最後の一歩は任意の正の大きさで状態遷移できる」と考えるとこうなります。

【問題１6】
標準的なサイコロを $100$ 回投げる。出目の和が $n$ となる確率を求めよ。

【解答】
$f =$ $\frac{1}{6} (x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6})$ とするとき、 $[x^{n}] f^{100}$ が答である。

「状態」ごとの「確率」を係数に持たせて多項式を作っています。状態を $+ 1, + 2, \dots, + 6$ する方法が $1 / 6$ 個ずつあると思うとよいでしょうか。

【問題１7】
はじめ、数直線の原点に居る。 $p + q = 1$ となる実数 $p, q$ がある。
「表が確率 $p$ 、裏が確率 $q$ で出るコイン」を投げて、表なら正の方向、裏なら負の方向に 1 進む。 $100$ 回コインを投げたとき、 $x = n$ に居る確率を求めよ。

【解答】
$f =$ $(p x + q x^{- 1})$ とするとき、 $[x^{n}] f^{100}$ が答である。

ちょっと新種のキャラの登場です。到達地点の座標を「状態」と考えて、計算結果を多項式で持とうとすると、 $x^{- 1}, x^{- 2}$ といった負べきの項が登場します。このような項を含む「多項式」はLaurent 多項式と呼ばれます。とはいえ、考察の上での注意点は少なくて、ほとんど多項式と同じように扱えます。

プログラミングで実装する場合は、負のインデックスをそのまま扱うと事故がこわいので、次のような解決策をとることがあります。

【解答】
答は $[x^{n}]$ $(p x + q x^{- 1})$ $^{100}$ であった。これは、 $[x^{n + 100}]$ $x^{100}$ $(p x + q x^{- 1})$ $^{100}$ と等しい。よって $[x^{n + 100}]$ $(p x^{2} + q)$ $^{100}$ と等しい。これで、計算対象から負べきの項が消えた。

【問題１８】
$N = a_{1} + a_{2} + \dots + a_{k}$ （ただし $a_{i}$ は正の整数）と表すことを考える（【問題１１】と同様です）。このような分割に対してその「美しさ」を $\prod_{i = 1}^{k} a_{i}^{2}$ により定義する。全ての分割に対する、「美しさ」の総和を計算せよ。（出典：AGC013-Eで禁止点のない場合）

【解答】
$f =$ $\sum_{k = 1}^{\infty} k^{2} x^{k} = x + 4 x^{2} + 9 x^{3} + 16 x^{4} + \dots$ とするとき、 $[x^{N}] \sum_{n = 0}^{\infty} f^{n}$ が答である。

これは結構難しめでしょうか。「状態」ごとの「値」を持たせて多項式を作るのですが、値として「美しさの総和」を持たせておきます。 $n$ 回目の遷移で「状態」を $k$ 進めると、「値」が $k^{2}$ 倍になるため、この形になります。

あるいは、 $f^{n}$ を分配法則で展開することを考えると、 $N$ の分割ごとに「美しさ」が加算されることが直接確認できると思います。

高次元の状態遷移

高次元の状態を持たせたい場合には、多変数の多項式や形式的べき級数を用いるとよいです。なお、私の知る限り、多変数の形式的べき級数の扱いは $1$ 変数と比べて難しく、上手い構造がないと高速計算ができない場合が増えてくるように思います。考察の上では有用です。

【問題１９】
・価格が3円で重さが4グラムの商品A
・価格が5円で重さが6グラムの商品B
がある。それぞれ $2$ つまで購入できる。ちょうど $n$ 円で $m$ グラムにする方法は何通り？

【解答】
$f = 1 + x^{3} y^{4} + x^{6} y^{8}$ , $g = 1 + x^{5} y^{6} + x^{10} y^{12}$ とするとき、 $[x^{n} y^{m}] f g$ が答である。

「状態 ( $a$ 円、 $b$ グラム)」を「 $x^{a} y^{b}$ 」に対応させています。これまでの考え方を踏まえると、特に難しいところはないと思います。

【問題２０】
$1$ 円硬貨、 $5$ 円硬貨、 $10$ 円硬貨が無限個ある。ちょうど $n$ 枚使ってちょうど $m$ 円を支払う方法を数え上げよ。

【解答】
$f_{1} = \sum_{n = 1}^{\infty}$ $x^{n} y^{n}$ , $f_{5} = \sum_{n = 1}^{\infty}$ $x^{5 n} y^{n}$ , $f_{10} = \sum_{n = 1}^{\infty}$ $x^{10 n} y^{n}$ とするとき、 $[x^{m} y^{n}] f_{1} f_{5} f_{10}$ が答である。

(金額 $a$ , 枚数 $b$ ) の状態を $x^{a} y^{b}$ に対応させています。

【問題２１】
$2$ 次元座標平面上の原点を出発して、ランダムウォークする。つまり、 $(x, y)$ に居るときに、 $(x \pm 1, y)$ , $(x, y \pm 1)$ に等確率で移動することを繰り返す。 $1$ 秒間に $1$ 回移動する。 $T$ 秒後に $(a, b)$ に居る確率を求めよ。（関連：ARC-012）

【解答】
$f = (x + x^{- 1} + y + y^{- 1}) / 4$ とするとき、 $[x^{a} y^{b}] f^{T}$ が答である。

【問題２２】
3 つの変数 $X, Y, Z$ があり、はじめこれらの値はすべて $0$ である。 $1$ 回の操作では
・変数を $1$ つ選び、 $1$ または $- 1$ を加える
・すべての変数に同時に $1$ を加える、または同時に $- 1$ を加える
のどちらかができる。 $N$ 回の操作の後に、 $X = p$ , $Y = q$ , $Z = r$ となる操作列を数え上げよ。（出典：KUPC 2019-K ）

【解答】
$f = x + x^{- 1} + y + y^{- 1} + z + z^{- 1} + x y z + (x y z)^{- 1}$ とするとき、 $[x^{p} y^{q} z^{r}] f^{N}$ が答である。

問題２１・２２は、上手い構造があって簡単に計算できます。→ 私の記事

【問題２３】
$3$ 次元空間内の原点を出発する。 $(x, y, z)$ に居るとき、非負整数の組 $(a, b, c)$ （ただし $(0, 0, 0)$ を除く）を選んで $(x + a, y + b, z + c)$ にワープできる。原点から $(X, Y, Z)$ までの移動方法を数え上げよ。（出典：yukicoder No.940）

【解答】
$f_{x} =$ $1 + x + x^{2} + x^{3} + \dots$ , $f_{y} =$ $1 + y + y^{2} + y^{3} + \dots$ , $f_{z} =$ $1 + z + z^{2} + z^{3} + \dots$ とおく。 $f =$ $f_{x} f_{y} f_{z} - 1$ とおく。
$\sum_{n = 0}^{\infty} [x^{X} y^{Y} z^{Z}] f^{n}$ が答である。

「 $(0, 0, 0)$ を除く」というルールがなければ、 $f_{x} f_{y} f_{z}$ が 1 回の移動の状態遷移になります。 $(0, 0, 0)$ を除くというルールを付加したものが $f$ になります。

【問題２４】
$3$ 次元空間内の原点を出発して、ランダムウォークする（確率 $1 / 6$ ずつでそれっぽく移動）。 $T$ 秒後に $(a, b, c)$ に到達するとして、 $3 a + 4 b + 5 c = n$ となる確率を求めよ。（出典：yukicoder No.612）

【解答】
$f =$ $(x + x^{- 1} + y + y^{- 1} + z + z^{- 1}) / 6$ とするとき、 $\sum_{3 a + 4 b + 5 c = n} [x^{a} y^{b} z^{c}]$ $f^{T}$ が答である。

と書いたものの、実は変数が減らせます。 $3$ 変数多項式から $3 a + 4 b + 5 c$ の情報を取り出しましょう。

$x = t^{3}$ , $y = t^{4}$ , $z = t^{5}$ とすると、 $x^{a} y^{b} z^{c} = t^{3 a + 4 b + 5 c}$ となるので、次のようになります。

【解答】
$f =$ $(t^{3} + t^{- 3} + t^{4} + t^{- 4} + t^{5} + t^{- 5}$ )/6 とするとき、 $[t^{n}] f^{T}$ が答である。

実際には、そもそも「 $3 a + 4 b + 5 c$ を状態と思う」ことで、はじめから直接この形にしてしまうのが分かりやすいかもしれませんが、どちらの手順が自然に浮かぶときもあるでしょう。

一般的なテクニックとして書くのであれば：
beetさんのブログ → http://beet-aizu.hatenablog.com/entry/2019/12/29/092046