母関数（組合せ論の生成関数）

Q: 母関数（組合せ論の生成関数）とは何ですか？

数列 \{a_n\}_{n=0}^{\infty} に対し、形式的べき級数 A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \cdots を数列 \{a_n\} の（通常型）母関数（generating function）と呼ぶ。ここで x は収束・発散を問わない形式的な記号（プレースホルダー）として扱われ、A(x) における x^n の係数を取り出す操作を [x^n]A(x) = a_n と書く。 組合せ論では、「額面 c の硬貨を1枚使うかどうか」を選ぶ操作は因子 (1 + x^c + x^{2c} + \cdots) = \frac{1}{1-x^c}（何枚でも使ってよい場合）に対応し、複数種類の硬貨を独立に選ぶ操作はそれぞれの因子の積として表される。額面 1 と 2 の硬貨で n 円を作る場合の数の母関数は、 A(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^2} となり、これを展開したときの x^n の係数がちょうど求める場合の数に一致する。

Q: 母関数（組合せ論の生成関数）は社会やプログラミングでどのように使われていますか？

コイン問題の動的計画法（DP）と母関数の係数計算の対応: 「硬貨の組み合わせで金額 n を作る場合の数」を求める典型的なDP（動的計画法）のアルゴリズムは、実は母関数 \prod_{c}\frac{1}{1-x^c} の係数を1つずつ計算しているのと数学的に同じ操作である。DPの二重ループはまさに母関数同士の積（畳み込み）の計算手順に対応する。

べき級数の係数に数え上げ問題の答えを閉じ込める組合せ論の魔法

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 母関数（生成関数）とは、数列 $a_0, a_1, a_2, \dots$ を「係数」として並べたべき級数 $A(x) = \sum_{n=0}^{\infty} a_n x^n$ のことで、数え上げ問題の答えをまとめて1つの式に閉じ込める道具
2: 額面1円玉と2円玉だけで n 円を作る場合の数は、 $\frac{1}{1-x}\cdot\frac{1}{1-x^2}$ という母関数を展開したときの $x^n$ の係数として一発で求まる
3: 母関数による係数の漸化式は、プログラミングの動的計画法（DP）の遷移式と本質的に同じものであり、コインの数え上げDPは母関数の係数計算そのものと言える

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

母関数（生成関数）とは、数列 $a_0, a_1, a_2, \dots$ を「係数」として並べたべき級数 $A(x) = \sum_{n=0}^{\infty} a_n x^n$ のことで、数え上げ問題の答えをまとめて1つの式に閉じ込める道具

身につく武器・思考力

額面1円玉と2円玉だけで n 円を作る場合の数は、$\frac{1}{1-x}\cdot\frac{1}{1-x^2}$ という母関数を展開したときの $x^n$ の係数として一発で求まる

実社会・ITでの活躍現場

•コイン問題の動的計画法（DP）と母関数の係数計算の対応
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

「使える硬貨の種類（1円玉のみ／1円玉と2円玉／1円玉・2円玉・5円玉）」をボタンで選び、スライダーで表示する金額 n の上限を変えてみよう。棒グラフに、各金額 $n=0,1,2,\dots$ を作る組み合わせの数（母関数を展開したときの $x^n$ の係数）がリアルタイムに積み上がっていく様子を確認できる。

表示する金額の上限 N = 10

母関数

A(x) = \dfrac{1}{(1-x)(1-x^2)}

の係数

[x^n]A(x)

x^0

x^1

x^2

x^3

x^4

x^5

x^6

x^7

x^8

x^9

x^10

n = 4 円を作る方法の数: 3 通り

これは母関数 $A(x)=\dfrac{1}{(1-x)(1-x^2)}$ を展開したときの $x^{4}$ の係数 $[x^{4}]A(x) = 3$ に一致します。棒グラフの棒をクリックすると、その金額の係数を選択できます。

↑ 硬貨の種類を切り替えると、各棒（各金額 n）の高さ＝場合の数がどう変わるか観察してみよう。使える硬貨が増えるほど、同じ金額でも多くの作り方があることが分かる。この計算は内部的に「動的計画法（DP）」のテーブル埋めと完全に同じ手順で行われている。

直感チェック！ミニクイズ

1円玉と2円玉だけを使って合計4円を作る方法は何通りあるか（同じ金種の硬貨同士は区別しない）？

Layer 2 — 定義・受験・証明

定義

数列 $\{a_n\}_{n=0}^{\infty}$ に対し、形式的べき級数

A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \cdots

を数列 $\{a_n\}$ の（通常型）母関数（generating function）と呼ぶ。ここで $x$ は収束・発散を問わない形式的な記号（プレースホルダー）として扱われ、 $A(x)$ における $x^n$ の係数を取り出す操作を $[x^n]A(x) = a_n$ と書く。

組合せ論では、「額面 $c$ の硬貨を1枚使うかどうか」を選ぶ操作は因子 $(1 + x^c + x^{2c} + \cdots) = \frac{1}{1-x^c}$ （何枚でも使ってよい場合）に対応し、複数種類の硬貨を独立に選ぶ操作はそれぞれの因子の積として表される。額面 $1$ と $2$ の硬貨で $n$ 円を作る場合の数の母関数は、

A(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^2}

となり、これを展開したときの $x^n$ の係数がちょうど求める場合の数に一致する。

公式・数理モデル

A(x) = \sum_{n=0}^{\infty} a_n x^n, \qquad \frac{1}{1-x^c} = 1 + x^c + x^{2c} + x^{3c} + \cdots

証明・導出

「なぜ積を取ると場合の数が求まるのか」の証明： 1円玉だけを何枚か使って金額を作る操作を考えると、0枚使えば0円、1枚使えば1円、2枚使えば2円、…という選択肢があり、これを母関数として $1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}$ と表す（ $x^k$ の項は「1円玉を使って $k$ 円分寄与する」という選択肢1通りを表す）。

同様に2円玉を何枚か使う操作は $1 + x^2 + x^4 + \cdots = \frac{1}{1-x^2}$ と表される（2円玉は奇数円を作れないため奇数次の項は存在しない）。

1円玉の選び方と2円玉の選び方は独立であるため、両方を組み合わせた「1円玉と2円玉合わせて $n$ 円を作る場合の数」を求めるには、2つの母関数の積を展開すればよい。積の展開において $x^n$ の係数は、

[x^n]\left(\frac{1}{1-x}\cdot\frac{1}{1-x^2}\right) = \sum_{k=0}^{n} [x^k]\frac{1}{1-x} \cdot [x^{n-k}]\frac{1}{1-x^2}

という畳み込み（コンボリューション）の形になる。これはまさに「1円玉で $k$ 円、2円玉で $n-k$ 円を作り、それらをすべての $k$ について足し合わせる」という数え上げの手順と完全に一致しており、母関数の積が場合の数の和（畳み込み）を自動的に計算していることが分かる。

押さえておきたいポイント

母関数の積は「畳み込み（コンボリューション）」に対応し、独立な選択肢を合成する数え上げ問題に強力に働く
フィボナッチ数列の母関数は $\frac{x}{1-x-x^2}$ という有理関数になり、漸化式 $a_n=a_{n-1}+a_{n-2}$ が分母の形にそのまま反映されている
指数型母関数 $\sum a_n \frac{x^n}{n!}$ を使うと、順列（並べ方を区別する）の数え上げも同様の枠組みで扱える
母関数のべき級数展開を先頭から $n$ 項だけ計算する操作は、計算機科学における動的計画法（DP）のテーブル埋めと完全に等価な計算過程である

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

コイン問題の動的計画法（DP）と母関数の係数計算の対応

「硬貨の組み合わせで金額 n を作る場合の数」を求める典型的なDP（動的計画法）のアルゴリズムは、実は母関数 $\prod_{c}\frac{1}{1-x^c}$ の係数を1つずつ計算しているのと数学的に同じ操作である。DPの二重ループはまさに母関数同士の積（畳み込み）の計算手順に対応する。

1// 硬貨の額面リストを使って 0〜N 円を作る場合の数を DP（= 母関数の係数計算）で求める
2function countCoinCombinations(coins: number[], maxN: number): number[] {
3  // dp[n] は「n 円を作る組み合わせの数」= 母関数 A(x) の x^n の係数
4  const dp = new Array(maxN + 1).fill(0);
5  dp[0] = 1; // 0円を作る方法は「何も使わない」の1通り（定数項 a_0 = 1）
6
7  // 硬貨を1種類ずつ「掛け合わせる」＝母関数の積を取ることに対応
8  for (const coin of coins) {
9    // 1/(1-x^coin) を現在の母関数に掛ける操作
10    for (let n = coin; n <= maxN; n++) {
11      dp[n] += dp[n - coin];
12    }
13  }
14
15  return dp; // dp[0..maxN] が母関数 A(x) = Π 1/(1-x^coin) の係数列
16}
17
18// 例: 1円玉と2円玉だけで 0〜8円を作る場合の数
19const coefficients = countCoinCombinations([1, 2], 8);
20console.log(coefficients);
21// => [1, 1, 2, 2, 3, 3, 4, 4, 5]
22//    n=4円 のとき係数3 → {1+1+1+1, 1+1+2, 2+2} の3通りと一致
23
24// 額面1,2,5円玉に増やすと、母関数は 1/((1-x)(1-x^2)(1-x^5)) に対応する
25const withNickels = countCoinCombinations([1, 2, 5], 8);
26console.log(withNickels);