母関数
概要
母関数（generating function）とは、数列 $(a_n)$ を係数とする形式的冪級数 $\sum a_nx^n$（通常母関数）や $\sum a_nx^n/n!$（指数型母関数）のことで、生成関数ともいう。数列の畳み込みが級数の積に対応し、通常母関数が多項式の比で書けることと、数列がある項から先で定数係数の線形漸化式を満たすことは同値である。区別のつかないものの選び方は通常母関数の積で、番号の付いたものを 2 組に分けてそれぞれに構造を載せる方法は指数型母関数の積で数えられ、完全順列の個数の指数型母関数は $e^{-x}/(1-x)$ になる。$\sum n!\,x^n$ のように $0$ でない数を代入すると発散する母関数もあるが、形式的冪級数としての計算はそのまま正しい。
定義
Fibonacci数 $0,1,1,2,3,5,8,13,\dots$（$F_0=0$、$F_1=1$、$F_{n+2}=F_{n+1}+F_n$）を係数に並べた式 $F_0+F_1x+F_2x^2+\cdots$ は、分数式
$$
\frac{x}{1-x-x^2}=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+\cdots
$$
に等しい。無限に続く数列が、たった 1 つの分数式に詰め込まれている。別の例として、1 円・5 円・10 円・50 円・100 円の硬貨で 100 円をちょうど支払う方法（使う枚数の組）の個数は、式
$$
\frac1{(1-x)(1-x^5)(1-x^{10})(1-x^{50})(1-x^{100})}
$$
を展開したときの $x^{100}$ の係数で、$159$ 通りである（ex-gf-coins）。また、$n$ 人の帽子を誰も自分の帽子を受け取らないように返す方法の数（完全順列の個数）$1,0,1,2,9,44,265,\dots$ は、$\frac{e^{-x}}{1-x}$ の $x^n$ の係数に $n!$ を掛けたものである（prop-gf-derangement）。
このように、数列 $(a_n)$ を係数にもつ級数 $\sum a_nx^n$ を母関数（generating function）という。生成関数ともいう。数列についての問題（漸化式、数え上げ、確率）を、級数の足し算・掛け算・割り算についての問題に翻訳するための道具である。
以下、$K$ を有理数体・実数体・複素数体のいずれかとし、$K$ 係数の形式的冪級数の環を $K[\![x]\!]$ と書く。形式的冪級数 $A(x)=\sum_{n\geq0}a_nx^n$ は係数の列 $(a_n)$ そのものであり、$x$ は係数の位置を示す記号である。$x^n$ の係数を $[x^n]A:=a_n$ と書く。和は係数ごと、積は
$$
[x^n](AB)=\sum_{k=0}^na_kb_{n-k}
$$
（Cauchy 積）で定める。2 つの形式的冪級数が等しいとは、すべての係数が等しいことである（形式的冪級数 の記事の定義「形式的冪級数」）。
$K$ の元の列 $(a_n)_{n\geq0}$ に対して、形式的冪級数
$$
A(x):=\sum_{n\geq0}a_nx^n,\qquad\hat A(x):=\sum_{n\geq0}a_n\frac{x^n}{n!}
$$
をそれぞれ $(a_n)$ の通常母関数（ordinary generating function）、指数型母関数（exponential generating function）という。単に母関数といえば通常母関数を指す。
通常母関数の定義は 数え上げ組合せ論 の記事の定義「通常母関数」と同じである。KT17 §8.1（p. 157）は、代入して値を求めることには必ずしも関心がなく、形式的冪級数として扱って収束の問題を無視することが多い、と断っている。指数型母関数は同書 §8.6（p. 170）にある。本記事でも母関数はすべて形式的冪級数として扱い、$x$ に数を代入するのは、級数が収束することを確かめた場合に限る。
$1/(1-x)$ のような分数式は、形式的冪級数の逆元を表す。定数項が $0$ でない形式的冪級数は $K[\![x]\!]$ で逆元をもつ（形式的冪級数 の記事の命題「定数項による単元判定」）。$a\in K$ について
$$
(1-ax)\sum_{n\geq0}a^nx^n=\sum_{n\geq0}a^nx^n-\sum_{n\geq1}a^nx^n=1
$$
なので $\frac1{1-ax}=\sum_{n\geq0}a^nx^n$ である。多項式 $P,Q$ で $Q$ の定数項が $0$ でないとき、$P/Q$ は $P\cdot Q^{-1}$ を表す。指数関数の級数に合わせて、$e^{cx}:=\sum_{n\geq0}c^nx^n/n!\in K[\![x]\!]$（$c\in K$）とも書く。これは定数列 $(c^n)$ の指数型母関数である。
直感
母関数は、数列全体を 1 つの式にまとめて扱うための入れ物である。第 $n$ 項を $x^n$ の位置に置いておけば、数列どうしの畳み込み $\sum_ka_kb_{n-k}$ が級数の積になり、漸化式は級数の 1 次方程式になる。数列を直接扱うより、級数の代数で計算するほうが見通しがよいことが多い。
通常母関数と指数型母関数の違いは、数える対象の性質に対応する。区別のつかないもの（同じ額の硬貨、整数の分割）を組み合わせるときは通常母関数の積が、区別のつく（番号の付いた）ものを 2 つの組に分けて別々の構造を載せるときは指数型母関数の積が、組み合わせた個数を与える（prop-gf-egf-product）。$\binom nk$ 通りの分け方が、$\frac{x^n}{n!}$ の $n!$ で吸収される。
例と反例
定数列 $1,1,1,\dots$ の通常母関数は $\frac1{1-x}$、等比数列 $1,a,a^2,\dots$ の通常母関数は $\frac1{1-ax}$ である（上の計算）。$\frac1{(1-x)^2}=\frac1{1-x}\cdot\frac1{1-x}$ の $x^n$ の係数は、Cauchy 積により $\sum_{k=0}^n1\cdot1=n+1$ なので、$1,2,3,\dots$ の通常母関数は $\frac1{(1-x)^2}$ である。定数列 $1,1,1,\dots$ の指数型母関数は $e^x$、$n!$ の列の指数型母関数は $\sum_n n!\frac{x^n}{n!}=\frac1{1-x}$ である。$(1+x)^n=\sum_k\binom nkx^k$（二項定理）は、$n$ を固定した列 $\binom n0,\binom n1,\dots$ の通常母関数である（二項係数 の記事の命題「二項係数の母関数」）。
$n$ 元集合の置換の個数 $n!$ の通常母関数 $\sum_{n\geq0}n!\,x^n$ は、形式的冪級数としては正当な母関数である。しかし実数の冪級数とみると、$x\ne0$ ではどこでも発散する（$x\ne0$ なら $|n!\,x^n|\to\infty$ なので項が $0$ に近づかない）。この母関数は「形式的冪級数である」という性質を満たすが、「$0$ でない数を代入して値が定まる」という性質を満たさない（KT17 Example 8.2、p. 159、形式的冪級数 の記事の例「収束しない級数も扱える」）。一方、同じ列の指数型母関数は $\frac1{1-x}$ で、$|x|<1$ で収束する。母関数の等式は係数の等式であって、関数としての等式ではない。
$\frac1{1-x}=1+x+x^2+\cdots$ の $x$ に形式的冪級数 $1+x$ を代入しようとすると、$x^0$ の係数は $1+1+1+\cdots$ となり定まらない。形式的冪級数 $f(x)$ に別の形式的冪級数 $g(x)$ を代入した $f(g(x))$ が係数ごとの有限和で定まるのは、$g$ の定数項が $0$ の場合である（形式的冪級数 の記事の命題「定数項が零の級数への代入」と注意「代入条件を落とせない理由」）。$g=1+x$ は「形式的冪級数である」という性質を満たすが「定数項が $0$」という性質を満たさず、代入 $f(g)$ が定義されない。母関数の計算で $x$ を $x^5$ や $ax$ に置き換えるのは、定数項が $0$ の級数の代入なので許される。
条件を 1 つ外した反例を表にまとめる。1・2 行目の確認は上の反例の箱にあり、3・4 行目は表の中の計算で確かめられる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 代入する級数 $g$ の定数項が $0$ | $f=\frac1{1-x}$、$g=1+x$（ex-gf-substitution） | $f(g)$ が係数ごとの有限和で定まること |
| 級数が $0$ でない $x$ で収束すること | $\sum_n n!\,x^n$（ex-gf-divergent） | $x\ne0$ を代入して値が定まること |
| $Q$ の定数項が $0$ でない（cor-gf-rational） | $P=1$、$Q=x$ | $P/Q$ が形式的冪級数として定まること（$x$ は $K[\![x]\!]$ で逆元をもたない） |
| $X$ と $Y$ が独立（prop-gf-pgf の 1） | $P(X=0)=P(X=1)=\frac12$、$Y=X$ | $G_{X+Y}=G_XG_Y$（左辺は $\frac{1+t^2}2$、右辺は $\frac{(1+t)^2}4$） |
性質
数列の操作と母関数の操作
$(a_n)$、$(b_n)$ の通常母関数を $A,B$ とし、$c\in K$ とする。
- $(a_n+b_n)$、$(ca_n)$ の通常母関数は $A+B$、$cA$ である。
- $(\sum_{k=0}^na_kb_{n-k})_n$ の通常母関数は $AB$ である。
- 1 つ後ろにずらした列 $0,a_0,a_1,\dots$ の通常母関数は $xA$ である。$a_0=0$ のとき、1 つ前にずらした列 $a_1,a_2,\dots$ の通常母関数は $B$ で $xB=A$ を満たす。
- 部分和の列 $(a_0+a_1+\cdots+a_n)_n$ の通常母関数は $\frac{A}{1-x}$ である。
たとえば 4 と ex-gf-basic から、$1+2+\cdots+(n+1)$ の母関数は $\frac1{(1-x)^3}$ であり、その $x^n$ の係数は $\frac{(n+1)(n+2)}2$ である。
硬貨の支払い方
$c_1,\dots,c_r$ を正の整数とし、$N(n)$ を、$c_1m_1+\cdots+c_rm_r=n$ を満たす $0$ 以上の整数の組 $(m_1,\dots,m_r)$ の個数とする。このとき
$$
\sum_{n\geq0}N(n)\,x^n=\prod_{i=1}^r\frac1{1-x^{c_i}}
$$
である。
$\frac1{1-x^{c}}$ は $\frac1{1-x}=\sum_mx^m$ の $x$ に定数項 $0$ の級数 $x^c$ を代入したもので、$\sum_{m\geq0}x^{cm}$ に等しい（直接 $(1-x^c)\sum_mx^{cm}=1$ を確かめてもよい）。$r$ についての帰納法で示す。$r=1$ では、$c_1m_1=n$ となる $m_1$ は $c_1\mid n$ のとき 1 個、それ以外で 0 個であり、$\sum_mx^{c_1m}$ の係数と一致する。$r-1$ 個の場合を仮定し、$c_1,\dots,c_{r-1}$ についての個数を $N'(n)$ とする。組 $(m_1,\dots,m_r)$ を最後の成分 $m_r$ で分けると、$c_rm_r=j$ となる $j$ ごとに残りの組は $N'(n-j)$ 個あるので
$$
N(n)=\sum_{j=0}^n[x^j]\Bigl(\sum_mx^{c_rm}\Bigr)\cdot N'(n-j)
$$
であり、これは prop-gf-operations の 2 により $\bigl(\sum_nN'(n)x^n\bigr)\cdot\frac1{1-x^{c_r}}$ の $x^n$ の係数である。帰納法の仮定から主張を得る。
1 円・5 円・10 円の硬貨で 10 円を支払う方法は、$\frac1{(1-x)(1-x^5)(1-x^{10})}=1+x+x^2+x^3+x^4+2x^5+\cdots+2x^9+4x^{10}+\cdots$ の $x^{10}$ の係数 $4$ である（10 円 1 枚、5 円 2 枚、5 円 1 枚と 1 円 5 枚、1 円 10 枚）。1 円・5 円・10 円・50 円・100 円で 100 円を支払う方法は、prop-gf-weights の積の $x^{100}$ の係数で、係数を順に計算すると $159$ である。1 つの因子を掛けるたびに係数を更新する計算（$a_n\leftarrow a_n+a_{n-c}$ を $n$ の小さい順に行う）は、$(1-x^c)^{-1}$ を掛けることを係数の漸化式で書いたものである。各 $c_i$ の枚数の上限を $u_i$ に制限すると、因子は $1+x^{c_i}+\cdots+x^{c_iu_i}$ に変わる（KT17 §8.2 の Example 8.5、p. 161 の果物かごの例と同じ考え方）。$c_i=i$（$i=1,2,3,\dots$）のすべてを使うと、整数の分割の個数の母関数 $\prod_{k\geq1}\frac1{1-x^k}$ になる（分割数 の記事の命題「分割数の母関数」）。
有理関数と線形漸化式
$(a_n)$ を $K$ の元の列、$A$ をその通常母関数とする。$k\geq1$、$c_1,\dots,c_k\in K$ とし、
$$
Q(x):=1-c_1x-c_2x^2-\cdots-c_kx^k
$$
とおく。次の 2 条件は同値である。
- すべての $n\geq k$ について $a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}$。
- $Q(x)A(x)$ は次数が $k$ 未満の多項式（または $0$）である。
このとき $P:=QA$ とおくと $A=P/Q$ であり、$P$ の $x^j$ の係数（$0\leq j< k$）は $a_j-\sum_{i=1}^jc_ia_{j-i}$ である。
$Q$ の $x^i$ の係数は、$i=0$ で $1$、$1\leq i\leq k$ で $-c_i$、$i>k$ で $0$ である。Cauchy 積により
$$
[x^n](QA)=a_n-\sum_{i=1}^{\min(n,k)}c_ia_{n-i}
$$
である。$n\geq k$ ではこれは $a_n-\sum_{i=1}^kc_ia_{n-i}$ なので、1 は「$QA$ の $k$ 次以上の係数がすべて $0$」と同値であり、それは 2 と同値である。$Q$ の定数項は $1$ なので $Q$ は $K[\![x]\!]$ で逆元をもち（形式的冪級数 の記事の命題「定数項による単元判定」）、$QA=P$ の両辺に $Q^{-1}$ を掛けて $A=PQ^{-1}=P/Q$ である。$P$ の係数の式は、上の式で $n=j< k$ としたものである。
列 $(a_n)$ の通常母関数が、多項式 $P,Q$（$Q$ の定数項は $0$ でない）によって $A=P/Q$ と書けるための必要十分条件は、ある $k\geq1$、$c_1,\dots,c_k\in K$、整数 $N\geq0$ について、すべての $n\geq N$ で $a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}$ が成り立つことである。
$A=P/Q$ とする。$Q$ を定数項で割っても $P/Q$ は変わらないので、$Q$ の定数項を $1$ としてよい。$k:=\max(\deg Q,1)$ とし、$Q=1-c_1x-\cdots-c_kx^k$ と書く（$\deg Q< k$ なら余った係数は $0$）。$QA=P$ なので、$n>\deg P$ では $[x^n](QA)=0$ である。$n\geq N:=\max(k,\deg P+1)$ で prf-gf-rational の係数の式を使えば漸化式を得る（$P=0$ なら $\deg P+1$ を $0$ と読む）。逆に漸化式が $n\geq N$ で成り立てば、同じ係数の式により $QA$ の $\max(N,k)$ 次以上の係数は $0$ で、$QA=:P$ は多項式であり、$A=P/Q$ である。
この対応は、母関数による漸化式の解法の基礎である（漸化式 の記事の注意「母関数による解法」、KT17 §9.6 の Example 9.24、pp. 202–203）。$Q(x)=x^k\chi(1/x)$ は漸化式の特性多項式 $\chi(t)=t^k-c_1t^{k-1}-\cdots-c_k$ の係数を逆順に並べたもので、$\chi$ の根 $\alpha$ ごとに $Q$ は因子 $1-\alpha x$ をもつ。$Q$ が相異なる因子 $1-\alpha_ix$ の積に分かれるとき、$P/Q$ を部分分数 $\sum_i\frac{\beta_i}{1-\alpha_ix}$ に分解すれば、$a_n=\sum_i\beta_i\alpha_i^n$ という一般項が得られる（$\deg P<\deg Q$ の場合。$c_k\ne0$ なら $\deg Q=k$ なので、これは $\deg P< k$ と同じである）。
$a_0=0$、$a_n=2a_{n-1}+1$（$n\geq1$）は定数係数の線形漸化式ではないが、差をとると $n\geq2$ で $a_n=3a_{n-1}-2a_{n-2}$ を満たす（$a_n-a_{n-1}=2(a_{n-1}-a_{n-2})$）。$a_0=0$、$a_1=1$ で、thm-gf-rational（$k=2$）により $P$ の係数は $a_0=0$ と $a_1-3a_0=1$ なので
$$
A(x)=\frac{x}{1-3x+2x^2}=\frac{x}{(1-x)(1-2x)}=\frac1{1-2x}-\frac1{1-x}
$$
であり（右端は通分して確かめられる）、$a_n=2^n-1$ を得る。これはハノイの塔の最少手数である（漸化式 の記事の例「ハノイの塔の最少手数」）。Fibonacci 数では $Q=1-x-x^2$ で、$P$ の係数は $F_0=0$、$F_1-F_0=1$ なので $\sum F_nx^n=\frac x{1-x-x^2}$ である（数え上げ組合せ論 の記事の例「二項係数・Fibonacci 数・Catalan 数の母関数」）。$1-x-x^2=(1-\varphi x)(1-\psi x)$（$\varphi,\psi=\frac{1\pm\sqrt5}2$）と部分分数に分けると、Fibonacci数 の記事の定理「Binetの公式」$F_n=\frac{\varphi^n-\psi^n}{\sqrt5}$ が得られる。
指数型母関数とラベル付きの構造
- $K$ の元の列 $(f_n)$、$(g_n)$ に対し $h_n:=\sum_{k=0}^n\binom nkf_kg_{n-k}$ とおくと、指数型母関数について $\hat H=\hat F\hat G$ である。
- 各有限集合 $S$ に有限集合 $\mathcal{F}(S)$、$\mathcal{G}(S)$ が対応していて、その元の個数は $S$ の元の個数だけで決まり、$|S|=n$ のとき $|\mathcal{F}(S)|=f_n$、$|\mathcal{G}(S)|=g_n$ であるとする。$[n]:=\{1,\dots,n\}$ の部分集合 $T$ と、$\alpha\in\mathcal{F}(T)$、$\beta\in\mathcal{G}([n]\setminus T)$ の組 $(T,\alpha,\beta)$ の個数は $h_n$ に等しい。
1：Cauchy 積により
$$
[x^n](\hat F\hat G)=\sum_{k=0}^n\frac{f_k}{k!}\cdot\frac{g_{n-k}}{(n-k)!}=\frac1{n!}\sum_{k=0}^n\frac{n!}{k!\,(n-k)!}f_kg_{n-k}=\frac{h_n}{n!}
$$
であり、これは $\hat H$ の $x^n$ の係数である。2：組 $(T,\alpha,\beta)$ を $|T|=k$ で分ける。$[n]$ の $k$ 元部分集合 $T$ は $\binom nk$ 個あり（二項係数 の記事の命題「部分集合による特徴づけ」）、各 $T$ について $\alpha$ の選び方は $f_k$ 通り、$\beta$ の選び方は $g_{n-k}$ 通りである。したがって組の個数は $\sum_k\binom nkf_kg_{n-k}=h_n$ である。
1 の $h_n$ を $(f_n)$ と $(g_n)$ の二項畳み込みという。2 は、番号の付いた $n$ 個のものを 2 組に分け、一方の組に $\mathcal{F}$ の構造を、他方に $\mathcal{G}$ の構造を載せる方法の数が、指数型母関数の積で数えられることを表す（Bog §C.4 The Product Principle for EGFs、pp. 156–162）。たとえば $n$ 本の柱を赤・白の 2 色で塗る方法は $2^n$ 通りで指数型母関数は $e^{2x}$、青・緑・黄の 3 色では $e^{3x}$ であり、5 色で塗る方法の指数型母関数は、柱を「赤・白で塗る組」と「残りの 3 色で塗る組」に分けることで $e^{2x}e^{3x}$ になる。係数を比べると $5^n=\sum_k\binom nk2^k3^{n-k}$ で、二項定理 と一致する（同書 pp. 157–158 の例）。
指数型母関数の計算では、形式的冪級数 $e^{x}=\sum_nx^n/n!$ と $e^{-x}=\sum_n(-1)^nx^n/n!$ が互いに逆元であることをよく使う。実際、1 により $e^xe^{-x}$ の $x^n/n!$ の係数は $\sum_k\binom nk(-1)^{n-k}=(1-1)^n$ で、$n=0$ で $1$、$n\geq1$ で $0$ である。
$[n]$ の置換で不動点をもたないもの（完全順列）の個数を $d_n$ とする（$d_0:=1$）。このとき $(d_n)$ の指数型母関数 $\hat D$ は
$$
e^x\hat D(x)=\frac1{1-x},\qquad\hat D(x)=\frac{e^{-x}}{1-x}
$$
を満たし、したがって
$$
d_n=n!\sum_{j=0}^n\frac{(-1)^j}{j!}
$$
である。
$[n]$ の置換 $\sigma$ に対し、不動点の集合 $T:=\{i\mid\sigma(i)=i\}$ をとる。$\sigma$ は全単射で $\sigma(T)=T$ なので、$\sigma$ は補集合 $[n]\setminus T$ をそれ自身に写し、その上への制限は不動点をもたない置換（$[n]\setminus T$ の完全順列）である。逆に、部分集合 $T$ と $[n]\setminus T$ の完全順列 $\tau$ が与えられれば、$T$ の上で恒等写像、$[n]\setminus T$ の上で $\tau$ となる置換がただ 1 つ定まり、その不動点の集合はちょうど $T$ である。この 2 つの対応は互いに逆なので、$[n]$ の置換全体と組 $(T,\tau)$ の全体は 1 対 1 に対応する。
prop-gf-egf-product の 2 を、$\mathcal{F}(S)$ を $S$ の恒等写像だけからなる 1 元集合（$f_k=1$）、$\mathcal{G}(S)$ を $S$ の完全順列全体の集合（$g_m=d_m$。$S=\emptyset$ では空写像 1 個）として使うと、置換の個数について $n!=\sum_k\binom nk\cdot1\cdot d_{n-k}$ を得る。$(n!)$ の指数型母関数は $\frac1{1-x}$、$(1)$ の指数型母関数は $e^x$ なので、1 により $e^x\hat D=\frac1{1-x}$ である。両辺に $e^{-x}$ を掛けると $\hat D=e^{-x}\cdot\frac1{1-x}$ であり、右辺の $x^n$ の係数は Cauchy 積により $\sum_{j=0}^n\frac{(-1)^j}{j!}\cdot1$ である。これが $d_n/n!$ に等しい。
$d_0,d_1,\dots,d_7$ は $1,0,1,2,9,44,265,1854$ である。同じ公式は包除原理でも得られる（数え上げ組合せ論 の記事の例「完全順列の個数」、KT17 Theorem 7.11、p. 147）。$d_n/n!$ は $e^{-1}$ の級数の部分和なので、$n\to\infty$ で $1/e=0.3678\ldots$ に近づく（KT17 Theorem 7.12、p. 148）。Bog p. 157 は、すべての置換が完全順列と恒等置換の組に分かれることからこの母関数の関係を説明している。
確率母関数
離散確率空間の上の確率変数 $X$ が $0$ 以上の整数の値だけをとるとき、分布の列 $(P(X=k))_{k\geq0}$ の通常母関数
$$
G_X(t):=\sum_{k\geq0}P(X=k)\,t^k\in\mathbb{R}[\![t]\!]
$$
を $X$ の確率母関数（probability generating function）という。
係数の和は $\sum_kP(X=k)=1$ なので、この級数は $|t|\leq1$ で絶対収束し、確率変数 の記事の命題「確率変数の関数の分布と期待値」を $g(k)=t^k$ に使えば $G_X(t)=E[t^X]$ である（$0^0=1$）。特に $G_X(1)=1$ である。形式的冪級数としての $G_X$ は分布そのものであり、$G_X=G_Y$ なら $X$ と $Y$ は同じ分布をもつ。GrS06 §10.1（p. 369）はこの $h(z)=\sum_jp(j)z^j$ を $X$ の ordinary generating function と呼んでいる。
$X,Y$ を同じ離散確率空間の上の確率変数で、$0$ 以上の整数の値だけをとるものとする。
- $X$ と $Y$ が独立ならば、形式的冪級数として $G_{X+Y}=G_XG_Y$ である。
- $X$ のとる値が有限個ならば、$G_X$ は多項式で、$E[X]=G_X'(1)$、$E[X(X-1)]=G_X''(1)$ である。
1：独立な確率変数の和の分布は畳み込み $P(X+Y=s)=\sum_{k=0}^sP(X=k)P(Y=s-k)$ で与えられる（確率変数 の記事の命題「周辺分布と和の分布」の 3。確率 $0$ の値は和に寄与しない）。これは prop-gf-operations の 2 により $G_XG_Y$ の $t^s$ の係数である。2：$G_X(t)=\sum_{k=0}^Mp_kt^k$（$p_k=P(X=k)$、$M$ は最大の値）を微分すると $G_X'(1)=\sum_kkp_k$、$G_X''(1)=\sum_kk(k-1)p_k$ であり、確率変数 の記事の同じ命題により、これらは $E[X]$、$E[X(X-1)]$ に等しい。
1 は GrS06 p. 371 にある。2 から $V[X]=G_X''(1)+G_X'(1)-G_X'(1)^2$ である。
さいころ 1 個の目の確率母関数は $\frac{t+t^2+\cdots+t^6}6$ である。独立に振った 2 個の目の和 $S$ の確率母関数は、1 により
$$
G_S(t)=\Bigl(\frac{t+t^2+\cdots+t^6}6\Bigr)^2=\frac{t^2+2t^3+3t^4+4t^5+5t^6+6t^7+5t^8+4t^9+3t^{10}+2t^{11}+t^{12}}{36}
$$
で、係数が $S$ の分布を与える（$P(S=7)=\frac6{36}$）。二項分布 $B(n,p)$ の確率母関数は $\sum_k\binom nkp^k(1-p)^{n-k}t^k=(1-p+pt)^n$ である（二項定理）。$G'(1)=np$、$G''(1)=n(n-1)p^2$ なので、期待値 $np$ と分散 $n(n-1)p^2+np-n^2p^2=np(1-p)$ が再び得られる。独立な $B(m,p)$ と $B(n,p)$ の和の確率母関数は $(1-p+pt)^{m+n}$ なので、和は $B(m+n,p)$ に従う（$m=n$ の場合が GrS06 Example 10.5、pp. 371–372）。
Poisson 分布（$P(X=k)=e^{-\lambda}\lambda^k/k!$、$\lambda>0$）の確率母関数は $e^{-\lambda}\sum_k\frac{\lambda^k}{k!}t^k$ である。パラメータ $\lambda$ と $\mu$ の Poisson 分布に従う独立な $X,Y$ の和について、1 と 二項定理 により
$$
[t^s]G_{X+Y}=e^{-\lambda-\mu}\sum_{k=0}^s\frac{\lambda^k\mu^{s-k}}{k!\,(s-k)!}=e^{-(\lambda+\mu)}\frac{(\lambda+\mu)^s}{s!}
$$
なので、$X+Y$ はパラメータ $\lambda+\mu$ の Poisson 分布に従う。
補足
母関数が $0$ の近くで収束する冪級数であれば、形式的冪級数としての和・積は、収束域の共通部分で関数としての和・積に一致する（冪級数 の記事の命題「冪級数の和・定数倍・積」）。たとえば Fibonacci 数の母関数は $|x|<\frac{\sqrt5-1}2$ で収束して関数 $\frac x{1-x-x^2}$ に等しい。この場合は、係数の大きさの評価に関数論（特異点の位置）を使える。一方、ex-gf-divergent のように収束しない母関数でも、形式的冪級数としての計算はそのまま正しい。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
