Red cat の数学よもやま話・新装開店

はてなダイアリー「Red cat の数学よもやま話」から徐々にこちらに移行していきます。

母関数を用いた種々の技法(その 4)

数学・組み合わせ 数学・解析

今回は, 少し天下り的ではあるが調和数
{\displaystyle H_n = 1 + \frac12 + \cdots + \frac1n}
の母関数を求めてみたい.

{\displaystyle \frac{1}{1 - z} = \sum_{n\geqslant 0}z^n}
の両辺を {z} について積分すると
{\displaystyle \ln\frac{1}{1 - z} = \sum_{n\geqslant 1}\frac1n z^n}
を得る*1. この両辺を {\displaystyle \frac{1}{1 - z}} で割ると
{\begin{align} \frac{1}{1 - z}\ln\frac{1}{1 - z} &= \sum_{n\geqslant 1}\frac1n \frac{z^n}{1 - z} \\ &= \sum_{n\geqslant 1}\frac1n \sum_{m\geqslant 0}z^{m + n} \\ &= \sum_{n\geqslant 1}\sum_{m=0}^{n - 1}\frac{1}{n - m}z^n \\ &= \sum_{n\geqslant 1}\sum_{m=1}^n \frac1m z^n \\ &= \sum_{n\geqslant 1}H_n z^n \\ \end{align}}
となるから, {\langle H_n\rangle} の母関数は {\displaystyle \frac{1}{1 - z}\ln\frac{1}{1 - z}} である. 次回, もう少し一般化したものを求める.

*1:この式で {z\to 1} とすることで, {H_n\to\infty\ (n\to\infty)} がわかる.

母関数を用いた種々の技法(その 2)

数学・組み合わせ 数学・解析

{ F_0 = 0, \\ F_1 = 1, \\ F_{n+2} = F_{n+1} + F_n\ (n\geqslant 0) }
は Fibonacci 数の漸化式である. ここで第 3 の式の両辺に {z^{n+2}} を掛けて {n} についての和を取ると
{\displaystyle\sum_{n\geqslant 0}F_{n+2}z^{n+2} = z\sum_{n\geqslant 0}F_{n+1}z^{n+1} + z^2\sum_{n\geqslant 0}F_nz^n}
となるが,
{ \displaystyle\sum_{n\geqslant 0}F_{n+2}z^{n+2} = \sum_{n\geqslant 0}F_nz^n - z, \\ \displaystyle\sum_{n\geqslant 0}F_{n+1}z^{n+1} = \sum_{n\geqslant 0}F_nz^n }
であることから, {\displaystyle F(z) = \sum_{n\geqslant 0}F_nz^n} とおくと
{F(z)-z = zF(z) + z^2F(z)}
となり, このことから
{\displaystyle F(z) = \frac{z}{1-z-z^2}}
が求まる. 級数展開すると
{F(z) = z + z^2 + 2z^3 + 3z^4 + 5z^5 + 8z^6 + \dots}
となるので
{F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, \dots}
がわかるのだが, これだけではどうと言うこともないので, 次の記事で {F_n} の閉じた式を求めることにする.

母関数を用いた種々の技法(その 1)

数学・組み合わせ 数学・解析

{ g_0 = 1,\\ g_n = ng_{n-1}\ (n\geqslant 1) }
なる漸化式を見たとき, 数学が得意な方であればこれが {g_n = n!} であることはすぐにわかると思う. しかし, ここでは母関数を用いた解法を紹介したい.

上の式は一行で書くと
{g_n = ng_{n-1} + [n = 0]}
となる. 系列 {\langle g_n\rangle} の指数母関数
{\displaystyle \hat{G}(z) = \sum_{n\geqslant 0}g_n\frac{z^n}{n!}}
を考えると
{\begin{align} \hat{G}(z) &= \sum_{n\geqslant 0}ng_{n-1}\frac{z^n}{n!} + 1 \\ &= z\sum_{n\geqslant 1}g_{n-1}\frac{z^{n-1}}{(n-1)!} + 1 \\ &= z\sum_{n\geqslant 0}g_n\frac{z^n}{n!} + 1 \\ &= z\hat{G}(z) + 1 \end{align}}
故,
{\displaystyle \hat{G}(z) = \frac{1}{1 - z} = \sum_{n\geqslant 0}z^n}
が求まる. 従って {g_n = n!} である.

これは簡単な例であるが, 次回以降, もう少し複雑な式の求め方を紹介する.

Bernoulli 数の指数母関数

数学・組み合わせ 数学・解析

二つの系列
{\langle f_n\rangle=\langle f_0,f_1,f_2,\dots\rangle,\langle g_n\rangle=\langle g_0,g_1,g_2,\dots\rangle}
のそれぞれの指数母関数を
{\displaystyle\hat{F}(z)=\sum_{n\geqslant 0}f_n\frac{z^n}{n!},\hat{G}(z)=\sum_{n\geqslant 0}g_n\frac{z^n}{n!}}
とするとき,
{\displaystyle\hat{F}(z)\hat{G}(z)=\sum_{n\geqslant 0}\sum_k{n \choose k}f_k g_{n-k}\frac{z^n}{n!}}
は系列
{\displaystyle\langle h_n\rangle=\left\langle\sum_k{n \choose k}f_k g_{n-k}\right\rangle}
の指数母関数になる. これをたたみ込みと言う.

さて, Bernoulli 数 {B_n} を
{\displaystyle\sum_{j=0}^m{m+1 \choose j}B_j=[m=0]\quad(m\geqslant 0)}
で定義する*1. {m+1} を {n} に置き換えて両辺に {B_n} を加えると
{\displaystyle\sum_k{n \choose k}B_k=B_n+[n=1]\quad(n\geqslant 0)}
である. 系列 \langle B_n\rangle の指数母関数を {\hat{B}(z)} とするとき, 上式の左辺は \langle B_n\rangle と定数系列 {\langle 1,1,1,\dots\rangle} のたたみ込みになっているので, その指数母関数は {\hat{B}(z)e^z} である、また右辺の指数母関数は
{\displaystyle\sum_{n\geqslant 0}(B_n+[n=1])\frac{z^n}{n!}=\hat{B}(z)+z}
である. 故に
{\hat{B}(z)e^z=\hat{B}(z)+z}
であるから \hat{B}(z)=z/(e^z-1) を得る.

*1:{[m=n]} は {m=n} のとき {1}, そうでないとき {0} を表す.

二項係数に関する関係式(補足)

数学・代数 数学・組み合わせ

二項係数に関する関係式 - Red cat の数学よもやま話・新装開店 の補足記事.
mathneko.hatenablog.com

補題. n \ge 0 のとき (x \cdot D)^n = \sum_k {n \atopwithdelims\{\} k} x^k D^k, ただし {n \atopwithdelims\{\} m} は第 2 種 Stirling 数.
(証明)
{\begin{align} (x \cdot D)^{n + 1} &= (x \cdot D) \cdot (x \cdot D)^n \\ &= (x \cdot D) \sum_k {n \atopwithdelims\{\} k} x^k D^k \\ &= x \sum_k {n \atopwithdelims\{\} k} D(x^k D^k) \\ &= x \sum_k {n \atopwithdelims\{\} k} (k x^{k - 1} D^k + x^k D^{k + 1}) \\ &= \sum_k {n \atopwithdelims\{\} k} (k x^k D^k + x^{k + 1} D^{k + 1}) \\ &= \sum_k k {n \atopwithdelims\{\} k} x^k D^k + \sum_k {n \atopwithdelims\{\} k} x^{k + 1} D^{k + 1} \\ &= \sum_k k {n \atopwithdelims\{\} k} x^k D^k + \sum_k {n \atopwithdelims\{\} k - 1} x^k D^k \\ &= \sum_k \left( k {n \atopwithdelims\{\} k} + {n \atopwithdelims\{\} k - 1} \right) x^k D^k \\ &= \sum_k {n + 1 \atopwithdelims\{\} k} x^k D^k. \end{align}}
n = 0 のときは {0 \atopwithdelims\{\} k} = [k = 0] により成り立つ. よって補題は帰納的に成り立つ.

命題 1. {m \lt n} のとき {(x \cdot D)^m (1 + x)^n = (1 + x)^{n-m} f(x)\ (\deg f(x) = m).}
(証明)
{\begin{align} (x \cdot D)^m (1 + x)^n &= \sum_k {m \atopwithdelims\{\} k} x^k D^k (1 + x)^n \\ &= \sum_k {m \atopwithdelims\{\} k} x^k n^\underline{k} (1 + x)^{n - k} \\ &= (1 + x)^{n - m}\sum_k n^\underline{k} {m \atopwithdelims\{\} k} x^k (1 + x)^{m - k}. \end{align}}
ただし n^\underline{k} は下降階乗べき. ここに f(x) = \sum_k n^\underline{k} {m \atopwithdelims\{\} k} x^k (1 + x)^{m - k} は m 次の多項式である.

命題 2. {(x \cdot D)^n (1 + x)^n = n !x^n + (1 + x)g(x)\ (\deg g(x) = n - 1).}
(証明)
{\begin{align} (x \cdot D)^n (1 + x)^n &= \sum_k {n \atopwithdelims\{\} k} x^k D^k (1 + x)^n \\ &= \sum_k {n \atopwithdelims\{\} k} x^k n^\underline{k} (1 + x)^{n - k} \\ &= n! x^n + \sum_{k \lt n} n^\underline{k} {n \atopwithdelims\{\} k} x^k (1 + x)^{n - k}\quad (\because n^\underline{n} = n!). \end{align}}
ここに g(x) = \sum_{k \lt n} n^\underline{k} {n \atopwithdelims\{\} k} x^k (1 + x)^{n - k - 1} は (n - 1) 次の多項式である.

席替えの数理(その 4・最終回)

数学・組み合わせ

さて, 6 割強の確率で前回と同じ座席に座る人が出る席替えであるが, 実際のところ, 「前回と同じ座席に座る人の数」の期待値や分散はどのようになっているのだろうか.
これを確率変数 {X} とすると
{\displaystyle P(X=k)=\frac{h(n,k)}{n!}={n \choose k}\frac{!(n-k)}{n!}}
である. 故に
{\begin{align} E(X) &= \sum_{k=0}^n k\frac{h(n,k)}{n!} \\ &= \frac{1}{n!}\sum_{k=1}^n k{n \choose k}!(n-k) \\ &= \frac{1}{n!}n\sum_{k=1}^n {n-1 \choose k-1}!\left((n-1)-(k-1)\right) \\ &= \frac{1}{n!}n\sum_{k=0}^{n-1} {n-1 \choose k}!((n-1)-k) \\ &= \frac{1}{n!}n\sum_{k=0}^{n-1} h(n-1,k) \\ &= \frac{1}{n!}n\cdot(n-1)! = 1. \end{align}}
{\begin{align} E(X^2) &= \frac{1}{n!}\sum_{k=1}^n k^2{n \choose k}!(n-k) \\ &= \frac{1}{n!}\sum_{k=1}^n k(k-1){n \choose k}!(n-k)+\frac{1}{n!}\sum_{k=1}^n k{n \choose k}!(n-k) \\ &= \frac{1}{n!}\sum_{k=1}^n k(k-1){n \choose k}!(n-k)+1 \end{align}}
だから
{\begin{align} V(X) &= E(X^2)-E(X)^2 \\ &= E(X^2)-1 \\ &= \frac{1}{n!}\sum_{k=1}^n k(k-1){n \choose k}!(n-k) \\ &= \frac{1}{n!}n\sum_{k=1}^n (k-1){n-1 \choose k-1}!\left((n-1)-(k-1)\right) \\ &= \frac{1}{n!}n\sum_{k=0}^{n-1}k{n-1 \choose k}!((n-1)-k) \\ &= \frac{1}{n!}n(n-1)\sum_{k=1}^{n-1}{n-2 \choose k-1}!\left((n-2)-(k-1)\right) \\ &= \frac{1}{n!}n(n-1)\sum_{k=0}^{n-2}{n-2 \choose k}!((n-2)-k) \\ &= \frac{1}{n!}n(n-1)\sum_{k=0}^{n-2}h(n-2,k) \\ &= \frac{1}{n!}n(n-1)\cdot(n-2)! = 1. \end{align}}
すなわち期待値も分散も {n} によらず {1} になる. 実は
{\begin{align} P(X=k) &= \frac{h(n,k)}{n!} \\ &= {n \choose k}\frac{!(n-k)}{n!} \\ &= {n \choose k}\frac{(n-k)!}{n!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!} \\ &= \frac{1}{k!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!} \\ &\to \frac{1}{k!}e^{-1}\ (n\to\infty) \end{align}}
であるから, {X} の分布は平均 1, 分散 1 の Poisson 分布に近づいていく(常に {P(X=n-1)=0} であることを除いて).

参考 URL

参考書籍

コンピュータの数学

コンピュータの数学