6 S(k,r)

この節以降で、3 節で述べた方法での計算を行い、 それが 4 節での結果 (3) と一致することを確認する。 ただし、ここから先の話は元の問題からすれば本質的な話ではなく、 純粋に数学的な議論のみである。 また、この方針での計算はかなり大変であるので、 この後いくつかの節に分けて考察する。

3 節で考えたように、$k$ 回余計にかって $(m+k)$ 回で終わる確率は

$$\begin{eqnarray*}p_{m+k} &=& \frac{N-1}{N}\,\frac{N-2}{N}\cdots\frac{N-m+1}{N}... ... \end{array}\right)m!\frac{1}{N^k}S(k,m-1)\hspace{1zw}(1<m\leq N)\end{eqnarray*}$$

であるので、期待値 $\mu (N,m)$ は、

$$\mu(N,m) =\sum_{k=0}^\infty (m+k)p_{m+k} =\frac{m!}{N^m}\... ...\\ m \end{array}\right)\sum_{k=0}^\infty\frac{m+k}{N^k}S(k,m-1)$$ (4)

となる。まずは、この $S(k,r)$ を $k$ と $r$ の式で表すところから始める。 なお、$m=1$ のときは明らかに $\mu(N,m)=1$ であるから、 以後 $1<m\leq N$ として考える。

3 節で見たように、$S(k,r)$ には、

$$S(k,r) = \sum_{i=1}^r iS(k-1,i)$$ (5)

$$S(k,1) = 1$$ (6)

が成り立つ。 $S(1,r)=r(r+1)/2$ も言えていたが、これはむしろ (5) で

$$S(0,r)=1$$ (7)

であるとすれば得られるので、(7) が成り立つとすればよい。 なお、(5) を この式の $r$ を $(r-1)$ とした式と比較してみればわかるが、

$$S(k,r)=S(k,r-1)+rS(k-1,r)\hspace{1zw}(k\geq 1,\ r\geq 2)$$ (8)

が成り立つことに注意する。以後、この (6), (7), (8) から $S(k,r)$ を求めていくことにするが、 逆にこれを満たす $S(k,r)$ が一意に決定されることも容易にわかる。

さて、今 (8) で $r=2$ としてみると、 (6) より

$$S(k,2) =S(k,1)+2S(k-1,2) =2S(k-1,2)+1$$

となるから、この両辺を $2^k$ で割れば、

$$\frac{S(k,2)}{2^k}=\frac{S(k-1,2)}{2^{k-1}}+\frac{1}{2^k}$$

となるので、こ の式にこの式の $k$ を $(k-1)$ にしたものを代入する、 といったことを繰り返すことによって、

$$\begin{eqnarray*}\frac{S(k,2)}{2^k} &=& \frac{S(k-1,2)}{2^{k-1}}+\frac{1}{2^k}... ...+\frac{1}{2^k} \\ &=& \frac{1-1/2^{k+1}}{1-1/2}=2-\frac{1}{2^k}\end{eqnarray*}$$

となり、よって

$$S(k,2)=2\cdot 2^k-1$$ (9)

が得られる。同様に、(8) で $r=3$ とすると

$$S(k,3) =S(k,2)+3S(k-1,3) =3S(k-1,3)+2\cdot 2^k-1$$

となるので、$3^k$ で割れば

$$\begin{eqnarray*}\frac{S(k,3)}{3^k} &=& \frac{S(k-1,3)}{3^{k-1}} +2\left(\fra... ...\left(\frac{2}{3}\right)^k-\frac{1}{2}+\frac{1}{2}\,\frac{1}{3^k}\end{eqnarray*}$$

より、

$$S(k,3)=\frac{9}{2}\cdot 3^k-4\cdot 2^k+\frac{1}{2}$$ (10)

のようになる。この、(9), (10) より、

$$S(k,r)=\sum_{j=1}^r a_{r,j} j^k =a_{r,1}\cdot 1^k+a_{r,2}\cdot 2^k+\cdots+a_{r,r}\cdot r^k$$ (11)

の形であることが想像される。

もし、この (11) を (8) に代入して、 (6), (7), (8) を満たすように矛盾なく $a_{r,j}$ を決定できれば、 前に述べたようにそれを満たす $S(k,r)$ は一意であるから、 それで $S(k,r)$ が得られることになる。

(11) を (8) に代入すると、

$$\sum_{j=1}^r a_{r,j}j^k = \sum_{j=1}^{r-1} a_{r-1,j}j^k +r\... ...{r-1}\left(a_{r-1,j}+\frac{r}{j}a_{r,j}\right)j^k +a_{r,r}r^k$$

となる。よって、 $1\leq j\leq r-1$ に対して、

$$a_{r,j}=a_{r-1,j}+\frac{r}{j}\,a_{r,j}$$

であればよく、これは、

$$a_{r,j}=\frac{-j}{r-j}\,a_{r-1,j}$$

を意味するので、

$$\begin{eqnarray*}a_{r,j} &=& \frac{-j}{r-j}\,a_{r-1,j} = \frac{-j}{r-j}\,\f... ... &=& \frac{-j}{r-j}\,\frac{-j}{r-1-j}\cdots\frac{-j}{1}\,a_{j,j}\end{eqnarray*}$$

となり、

$$a_{r,j} = \frac{(-j)^{r-j}}{(r-j)!}\,a_{j,j}$$ (12)

となることになる。この $a_{j,j}$ は次のように決定できる。 (11) に $k=0$ を代入すると (7) より

$$S(0,r)=\sum_{j=1}^r a_{r,j}=1$$

となるが、ここに (12) を代入して

$$\sum_{j=1}^r \frac{(-j)^{r-j}}{(r-j)!}a_{j,j}=1\hspace{1zw}(r\geq j)$$ (13)

が得られるが、 この (13) から次々 $a_{j,j}$ を求めることができる。 例えば、(13) に $r=1$ を代入すれば

$$\frac{(-1)^0}{0!}a_{1,1}=1$$

より $a_{1,1}=1$ となり、$r=2$ を代入すると、

$$\frac{(-1)^1}{1!}a_{1,1}+\frac{(-2)^0}{0!}a_{2,2}=1$$

となるので、 $a_{2,2}=a_{1,1}+1=2$ と求まる。以下、計算すると、

$$a_{3,3}=\frac{9}{2}=\frac{3^2}{2}, \ a_{4,4}=\frac{32}{3}=\frac{4^3}{6}, \ a_{5,5}=\frac{625}{24}=\frac{5^4}{24}$$

のようになるので、

$$a_{j,j}=\frac{j^{j-1}}{(j-1)!}=\frac{j^j}{j!}$$ (14)

となることが予想される。 これは実際に、(13) と帰納法を用いれば証明できる。 $j<r$ まで (14) が成り立つとすれば、 (13) により $a_{r,r}$ は、

$$a_{r,r} = 1-\sum_{j=1}^{r-1} \frac{(-j)^{r-j}}{(r-j)!}\,\fra... ...\left(\begin{array}{c} r \\ j \end{array}\right)\frac{j^r}{r!}$$

となる。ここで、

$$\sum_{j=0}^r\left(\begin{array}{c} r \\ j \end{array}\right)(-1)^{r-j}j^r=r!$$ (15)

であることを用いれば、

$$\begin{eqnarray*}a_{r,r} &=& 1-\frac{1}{r!}\left\{\sum_{j=0}^r (-1)^{r-j}\left... ...ight)r^r-0\right\} \\ &=& 1-\frac{1}{r!}(r!-r^r)=\frac{r^r}{r!}\end{eqnarray*}$$

となるので、帰納法により (14) が成り立つことになる。

(15) は、母関数の方法を用いて以下のように証明できる。 二項定理により、

$$f_1(x) =\sum_{j=0}^r\left(\begin{array}{c} r \\ j \end{array}\right)(-1)^{r-j}e^{jx} =(e^x-1)^r$$

であるが、 $(e^{jx})^{(r)}=j^r e^{jx}$ なので (15) は $f_1^{(r)}(0)$ に等しいことになる。

一方、テイラー展開を考えると、

$$\begin{eqnarray*}f_1(x) &=& (e^x-1)^r = \left(x+\frac{x^2}{2!}+\frac{x^3}... ...lefteqn{(O(x^{r+1})\mbox{ は $(r+1)$\ 次以上の項の和を意味する})}\end{eqnarray*}$$

となるので $f_1^{(r)}(0)=r!$ となり、 これで (15) が示されたことになる。

結局、(11), (12), (14) により、

$$S(k,r) =\sum_{j=1}^r\frac{(-j)^{r-j}}{(r-j)!}\,\frac{j^j}{... ...ft(\begin{array}{c} r \\ j \end{array}\right)\frac{j^{r+k}}{r!}$$ (16)

となる。 これは、$r=1$ とすると

$$S(k,1)=(-1)^0\left(\begin{array}{c} 1 \\ 1 \end{array}\right)\frac{1^{1+k}}{1!}=1$$

となり (6) も満たすので、 (6), (7), (8) を矛盾なく満たすことになり、 確かに (16) が成り立つことがわかる。