母関数と漸化式

　この記事は以下の問題を解くことを目標にします。

例題をいくつか解きましょう。

例題.1

　条件をみたしながら $k$ 回に分けて玉を合計 $n$ 個入れるとき, $1,2,\dots ,k$ 回目に入れた玉の個数を $c_1,c_2,\cdots ,c_k$ とすると,

• $c_1+c_2+\cdots c_k=n$
• $c_i\equiv 1,2(\mathrm{mod}6)(i=1,2,\cdots ,k)$
  を満たす正整数の組 $(c_1,c_2,\cdots ,c_k)$ の個数を数え上げる問題になります.
  よって, $k$ を固定した時の答えは以下の$x^n$ の係数になります.
  $$\begin{array}{rl}& (\sum _{\begin{array}{c}n\equiv 1,2(\mathrm{mod}6)\\ n\ge 0\end{array}}{x}^n{)}^k\\ & =(x+x^2+x^7+x^8+\cdots {)}^k\\ & =(x(1+x^6+x^{12}+\cdots )+x^2(1+x^6+x^{12}+\cdots ){)}^k\\ & =(x\frac{1}{1-x^6}+x^2\frac{1}{1-x^6}{)}^k\\ & =(\frac{x+x^2}{1-x^6}{)}^k\end{array}$$
  　答えはこれを $k=0,1,2,\cdots$ にて, 和を取れば求まるので, 先に母関数の和を取った以下の $x^n$ の係数になります.
  $$\begin{array}{rl}\sum _{k=0}^{\mathrm{\infty }}(\frac{x+x^2}{1-x^6}{)}^k& =\frac{1}{1-\frac{x+x^2}{1-x^6}}\\ \\ & =\frac{1-x^6}{1-x-x^2-x^6}\end{array}$$
  　上の冪級数を ${\displaystyle \sum _{k=0}^{\mathrm{\infty }}{a}_k{x}^k}$ とすると, 以下が成立します. ( $n<0$ について, $a_n=0$ とします.)
  $$(1-x-x^2-x^6)\sum _{k=0}^{\mathrm{\infty }}{a}_k{x}^k=\sum _{k=0}^{\mathrm{\infty }}(a_k-a_{k-1}-a_{k-2}-a_{k-6})x^k$$
  　一方これは
  $${\displaystyle \frac{x+x^2}{1-x-x^2-x^6}}\times (1-x-x^2-x^6)=1-x^6$$
  であるため,
  $$\sum _{k=0}^{\mathrm{\infty }}(a_k-a_{k-1}-a_{k-2}-a_{k-6})x^k=1-x^6$$
  の $x^k$ の係数を比較することで, $k\notin \{0,6\}$ にて,漸化式
  $$a_k-a_{k-1}-a_{k-2}-a_{k-6}=0$$
  が成立します. (問題の表記に従うと$f(n)-f(n-1)-f(n-2)-f(n-6)=0$ となります. )
  これは数直線上での $(x)\to (x+6n+1),(x+6m+2)$ のワープの問題と考えることもできます.次は座標平面の問題を考えてみます.

例題.2

　先程の問題と同じくまずワープを行う回数を $k$ 回と固定します. $1,2,\dots ,k$ 回目に宣言した整数の組を $(x_1,y_1),(x_2,y_2),\cdots ,(x_k,y_k)$ とすると,

• $(x_1,y_1)+(x_2,y_2)+\cdots (x_k,y_k)=(N,M)$
• $(x_i,y_i)\ne 0(i=1,2,\cdots ,k)$
  を満たす${\mathbb{Z}}_{\ge 0}^2$の組 $((x_1,y_1),(x_2,y_2),\cdots ,(x_k,y_k))$ の個数を数え上げる問題になります.
  よって, $k$ を固定した時の答えは以下の$x^N{y}^M$ の係数になります.
  $$\begin{array}{rl}& (\sum _{(n,m)\ne (0,0)}{x}^n{y}^m{)}^k\\ & =(\sum _{n,m>0}{x}^n{y}^m-x^0{y}^0{)}^k\\ & =((1+x+x^2+\cdots )(1+y+y^2+\cdots )-1{)}^k\\ & =(\frac{1}{1-x}\frac{1}{1-y}-1{)}^k\\ & =(\frac{x+y-xy}{(1-x)(1-y)}{)}^k\end{array}$$
  　これを $k=0,1,2,\cdots$ にて, 和を取れば
  $$\begin{array}{rl}& \sum _{k=0}^{\mathrm{\infty }}(\frac{x+y-xy}{(1-x)(1-y)}{)}^k\\ \\ & =\frac{1}{1-\frac{x+y-xy}{(1-x)(1-y)}}\\ \\ & =\frac{1-x-y+xy}{(1-x-y+xy)-(x+y-xy)}\\ \\ & =\frac{1-x-y+xy}{1-2x-2y+2xy}\end{array}$$
  この冪級数を ${\displaystyle \sum _{n,m}{a}_{n,m}{x}^n{y}^m}$ とすると, 分母の式 $1-2x-2y+2xy$ をかけることで,
  $$\sum _{n,m}(a_{n,m}-2a_{n-1,m}-2a_{n,m-1}+2a_{n-1,m-1})x^n{y}^m=1-x-y+xy$$
  が成立し, $(n,m)\notin \{(0,0),(1,0),(0,1),(1,1)\}$ にて, $x^n{y}^m$ の係数を比較することで、
  $$a_{n,m}-2a_{n-1,m}-2a_{n,m-1}+2a_{n-1,m-1}=0$$
  すなわち,
  $$f(N,M)-2f(N-1,M)-2f(N,M-1)+2f(N-1,M-1)=0$$
  が得られます.
  余談ですが, $$f(N,M)=\sum _{\begin{array}{c}n\le N,m\le M\\ (n,m)\ne (N,M)\end{array}}f(n,m)$$ であり,
  $$2f(N,M)=\sum _{\begin{array}{c}n\le N,m\le M\\ (n,m)\ne (N,M)\end{array}}f(n,m)+f(N,M)=\sum _{n\le N,m\le M}f(n,m)$$
  が成り立ち,
  図のように以下の式の項とそれぞれ対応を取ると実際に成り立つことがわかります.
  $$f(N,M)=2f(N-1,M)+2f(N,M-1)-2f(N-1,M-1)$$
  
  では本題を解いてみます.

本題

これまでと同様に考えると宣言することのできる整数組の集合を $S$ とすると $f(N,M)$ は
$$\frac{1}{1-{\displaystyle \sum _{(n,m)\in S}{x}^n{y}^m}}$$
の $x^N{y}^M$ の係数となります.
$$S=\{(n,m)\in {\mathbb{Z}}_{\ge 0}^2|min(n,m)\equiv 1(\mathrm{mod}2)\}$$
について, $\sum _{(n,m)\in S}{x}^n{y}^m$ を求めてみましょう.
$min(i,j)=k$ となる $(i,j)$ について, 単項式 $x^i{y}^j$ の和をとると以下のようになります.
$$\begin{array}{rl}\sum _{min(i,j)=k}{x}^i{y}^j& =\sum _{min(i,j)\ge k}{x}^i{y}^j-\sum _{min(i,j)\ge k+1}{x}^i{y}^j\\ \\ & =\sum _{min(i,j)\ge 0}{x}^{k+i}{y}^{k+j}-\sum _{min(i,j)\ge 0}{x}^{k+1+i}{y}^{k+1+j}\\ \\ & =x^k{y}^k\sum _{min(i,j)\ge 0}{x}^i{y}^j-x^{k+1}{y}^{k+1}\sum _{min(i,j)\ge 0}{x}^i{y}^j\\ \\ & =\frac{x^k{y}^k}{(1-x)(1-y)}-\frac{x^{k+1}{y}^{k+1}}{(1-x)(1-y)}\\ \\ & =\frac{(1-xy)}{(1-x)(1-y)}{x}^k{y}^k\end{array}$$
したがって,
$$\begin{array}{rl}\sum _{(n,m)\in S}{x}^n{y}^m& =\sum _{k=0}^{\mathrm{\infty }}\sum _{min(n,m)=2k+1}{x}^n{y}^m\\ & =\sum _{k=0}^{\mathrm{\infty }}\frac{(1-xy)}{(1-x)(1-y)}(xy{)}^{2k+1}\\ & =\frac{(1-xy)}{(1-x)(1-y)}\frac{xy}{1-x^2{y}^2}\\ & =\frac{xy}{(1-x)(1-y)(1+xy)}\end{array}$$
これより,
$$ $$\begin{array}{rl}\frac{1}{1-{\displaystyle \sum _{(n,m)\in S}{x}^n{y}^m}}& =\frac{1}{1-{\displaystyle \frac{xy}{(1-x)(1-y)(1+xy)}}}\\ & =\frac{(1-x)(1-y)(1+xy)}{(1-x)(1-y)(1+xy)-xy}\\ & =\frac{1-x-y+2xy-x^{2}y-x{y}^2+x^2{y}^2}{1-x-y+xy-x^{2}y-x{y}^2+x^2{y}^2}\end{array}$$}
$$ したがって, $(N,M)\notin \{(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)\}$ にて $f(N,M)-f(N-1,M)-f(N,M-1)+f(N-1,M-1)-f(N-2,M-1)-f(N-1,M-2)+f(N-2,M-2)=0$ が成立します. 母関数を用いずに導出する方法を思いついた方がいらっしゃいましたら教えてください！ここまで読んでくださりありがとうございました！！