母関数って役に立ちそうだけど、難しくてよく分からないって思っていましたが、このYouTube（英語）を見てあまりにも簡単で目からウロコだったので、ぜひ紹介したいと思います。
母関数の基本形
まずは基本形の$S=1+x+x^2+x^3+x^4+\cdots$(数列は$1,1,1,1,1,\cdots$)は以下のように求まります。
\begin{align}
\ \ S &= 1+x+x^2+x^3+x^4+\cdots &(a)\\
xS &= \ \ \ \ \ \ \ x+x^2+x^3+x^4+\cdots &(b)\\ \\
&(a)-(b)で \\\\
(1-x) S &= 1 \\
S &= \frac{1}{1-x}
\end{align}
母関数の基本操作
この基本形に対して以下のような基本操作を組合せることによって多くの母関数を求めることが出来ます。
| 基本操作 | 例 | 母関数＿ | 多項式 | 説明 | |
|---|---|---|---|---|---|
| (1) | 基本形 | $\Large \frac{1}{1-x}$ | $ 1+x+x^2+x^3+x^4+\cdots$ | ||
| (2) | 両辺をm倍 | $\times 2$ | $\Large \frac{2}{1-x}$ | $2+2x+2x^2+2x^3+2x^4+\cdots$ | すべてm倍 |
| (3) | 両辺を$x^m$倍 | $\times x$ | $\Large \frac{x}{1-x}$ | $x+x^2+x^3+x^4+\cdots$ | 右にm個シフト |
| (4) | xに$mx^n$を代入 | $x \leftarrow 2x$ | $\Large \frac{1}{1-2x}$ | $1+2x+4x^2+8x^3+16x^4+\cdots$ | 係数を$m^k$倍（n個おきに飛ばす） |
| (5) | 両辺を微分 | 1回微分 | $\Large \frac{1}{(1-x)^2}$ | $1+2x+3x^2+4x^3+5x^4+\cdots$ | 係数を$(k-1)$倍 |
| (6) | 2つの式の積 | $(1) \times (5)$ | $\Large \frac{1}{(1-x)^3}$ | $1+3x+6x^2+10x^3+15x^4+\cdots$ |
【例題 1~7】数列から母関数を求める
以下の例題はすべて$(2)から(6)$の基本操作の組み合わせで作ることが出来ます。
[例題 1] $\ \ 4,4,4,4,4,\cdots$
\begin{align}
&基本形(1)に基本操作の(2)を使って両辺を4倍する \\
&\frac{4}{1-x}=4+4x+4x^4+4x^3+4x^4+\cdots
\end{align}
[例題 2] $\ \ 2,4,6,8,10,\cdots$
\begin{align}
&(5) から\\
\frac{1}{(1-x)^2}&=1+2x+3x^2+4x^3+5x^4+\cdots \\
&(2) で2倍して \\
\frac{2}{(1-x)^2}&=2+4x+6x^2+8x^3+10x^4+\cdots \\
\end{align}
[例題 3] $\ \ 0,0,0,2,4,6,8,10,\cdots$
\begin{align}
&例題2の答えを(3)を使って3つシフトする\\
&x^0,x^1,x^2の係数が0になっていることに注意 \\
&\frac{2x^3}{(1-x)^2}=2x^3+4x^4+6x^5+8x^6+10x^7+\cdots \\
\end{align}
[例題 4] $\ \ 1,5,25,125,\cdots$
\begin{align}
&基本形(1)に(4)を使ってxに5xを代入\\
&\frac{1}{1-5x}=1+5x+25x^2+125x^3+\cdots \\
\end{align}
[例題 5] $\ \ 1,-3,9,-27,81,\cdots$
\begin{align}
&基本形(1)に(4)を使ってxに-3xを代入\\
&\frac{1}{1+3x}=1-3x+9x^2-27x^3+81x^4+\cdots \\
\end{align}
[例題 6] $\ \ 1,0,5,0,25,0,125,0,\cdots$
\begin{align}
&基本形(1)に(4)を使ってxに5x^2を代入\\
&x^2を代入することによって奇数次の項が0になることに注目 \\
&\frac{1}{1-5x^2}=1+5x^2+25x^4+125x^6+\cdots \\
\end{align}
[例題 7] $\ \ 0,1,0,0,2,0,0,3,0,0,4,0,0,5, \cdots$
\begin{align}
&(5)の後に(4)でxにx^3を代入して3つおきにする \\
&次に(3)で右に1つシフト \\
&\frac{1}{(1-x^3)^2}=x+2x^4+3x^7+4x^{10}+5x^{13}+\cdots \\
\end{align}
【例題 8~11】母関数から数列を求める
それほど難しくないので答えだけ示します
[例題 8] $\ \ \Large \frac{4x}{1-x} \large \rightarrow [0,4,4,4,4,4,\cdots]$
[例題 9] $\ \ \Large \frac{1}{1-4x}\large \rightarrow[1,4,16,64,256,\cdots]$
[例題 10] $\ \ \Large \frac{x}{1+x}\large \rightarrow [0,1,-1,1,-1,1,-1,\cdots]$
[例題 11] $\ \ \Large \frac{3x}{(1+x)^2}\large \rightarrow [0,3,-6,9,-12,15,-18,\cdots]$
[例題 12]
\begin{align}
\frac{1+x+x^2}{(1-x)^2} &= \frac{(1-x)^2+3x}{(1-x)^2} = 1+\frac{3x}{(1-x)^2} \\ \\
&\rightarrow [1,0,0,\cdots]+ [0,3,6,9,12,15,\cdots] \\
&= [1,3,6,9,12,15,\cdots] \\
\end{align}
どうですか、簡単ですよね。次回の（その２）では漸化式から母関数を求める方法を紹介したいと思います。