母関数：数列を関数として扱う

さいころ 1 個の目の出方を $D=x+x^2+\cdots+x^6$ で表す。$D^2$ を展開すると、1 つ目の因子から $x^i$、2 つ目の因子から $x^j$ を選んで $x^{i+j}$ ができる。$x^7$ の係数は $i+j=7$ となる組の数 $6$ であり、これは 2 個のさいころの目の和が $7$ になる出方の数である。全体は
$$ D^2=x^2+2x^3+3x^4+4x^5+5x^6+6x^7+5x^8+4x^9+3x^{10}+2x^{11}+x^{12} $$
である。

$(1-x)(1+x+x^2+x^3+\cdots)$ の $x^n$ の係数は、$n=0$ で $1$、$n\ge1$ で $1-1=0$ である。したがって形式的冪級数として
$$ \frac1{1-x}=1+x+x^2+x^3+\cdots $$
である。これは高校の等比数列の和の公式 $1+x+\cdots+x^n=\frac{1-x^{n+1}}{1-x}$ を、極限を使わずに係数の等式として述べたものである。ただし、$x$ に $2$ を入れて $-1=1+2+4+\cdots$ とするのは誤りである。どんなときに数を入れてよいかは、3 本目の記事で扱う。

$F_0=0$、$F_1=1$、$F_{n+2}=F_{n+1}+F_n$ で定まる Fibonacci 数 $0,1,1,2,3,5,8,\dots$ の母関数を $\Phi$ とする。$(1-x-x^2)\Phi$ の $x^n$ の係数は $F_n-F_{n-1}-F_{n-2}$（負の添字は $0$）であり、$n=0$ で $0$、$n=1$ で $1$、$n\ge2$ で漸化式から $0$ になる。したがって
$$ (1-x-x^2)\Phi=x,\qquad \Phi=\frac{x}{1-x-x^2} $$
である。漸化式が、分母の多項式 $1-x-x^2$ に記録されている。

正の整数 $n$ を、順序を区別せずに $1$ と $2$ だけの和で表す方法を数える。$n=5$ なら $1+1+1+1+1$、$2+1+1+1$、$2+2+1$ の $3$ 通りである。母関数では、2 つの等比級数の積
$$ (1+x+x^2+\cdots)(1+x^2+x^4+\cdots)=\frac1{1-x}\cdot\frac1{1-x^2} $$
を展開して、1 つ目の因子から $x^i$（$1$ を $i$ 個）、2 つ目の因子から $x^{2j}$（$2$ を $j$ 個）を選ぶ。$x^n$ の係数は $i+2j=n$ となる組 $(i,j)$ の数で、$1,1,2,2,3,3,4,\dots$ と並ぶ（$n=5$ で $3$）。使える部分を $1,2,3,\dots$ と全部に広げると、無限個の因子の積 $\frac1{1-x}\cdot\frac1{1-x^2}\cdot\frac1{1-x^3}\cdots$ が分割の総数を数える。

$6$ を順序を区別せずに正の整数の和で表す方法のうち、同じ数を 2 回使わないものは $6$、$5+1$、$4+2$、$3+2+1$ の $4$ 個、奇数だけを使うものは $5+1$、$3+3$、$3+1+1+1$、$1+1+1+1+1+1$ の $4$ 個である。この 2 つの個数は、どの $n$ でも等しい。母関数で書くと、2 つの無限積の等式
$$ (1+x)(1+x^2)(1+x^3)\cdots=\frac1{1-x}\cdot\frac1{1-x^3}\cdot\frac1{1-x^5}\cdots $$
になる。