次へ: 参考文献 上へ: 配列内のランダムな配置の選択の評価 前へ: 7 μ(N,m) (PDF ファイル: rand3.pdf)


8 f6(0)

この節では、7 節で考察した $f_6(0)$ を求める。 以後この $f_6(0)$ を
\begin{displaymath} F_3(N,n)=\int_0^{1} (1-s)^n s^{N-n-1}\log sds\end{displaymath} (21)

のようにおいてこれを考えることにする。 なお、$m\geq 2\leq N$ で $n=m-1$ なので、 ここまでは $1\leq n<N$ としてきたが、 この (21) を考える場合は $n=0$ を除外する必要はないので、 この (21) は $0\leq n<N$ として考えることにする。

部分積分により、

\begin{eqnarray*}\lefteqn{F_3(N,n) = \int_0^{1} (1-s)^n \left(\frac{s^{N-n}}{N... ...-n-1} ds \\ &=& \frac{n}{N-n}F_3(N,n-1)-\frac{1}{N-n}B(n+1,N-n)\end{eqnarray*}


となるが、この第 2 項は、 既に 7 節の $f_4(0)$ の計算で見たように、
\begin{displaymath} \frac{1}{N-n}B(n+1,N-n) = \frac{1}{(N-n)(n+1)\left(\begin{array}{c} N \\ n+1 \end{array}\right)} \end{displaymath}

と書けるので、
\begin{displaymath} F_3(N,n)=\frac{n}{N-n}F_3(N,n-1)-\frac{1}{(N-n)(n+1)\left(\begin{array}{c} N \\ n+1 \end{array}\right)} \end{displaymath}

となり、両辺を $(N-n)/n$ 倍すれば、
\begin{displaymath} \frac{N-n}{n}F_3(N,n)=F_3(N,n-1)-\frac{1}{n(n+1)\left(\begin{array}{c} N \\ n+1 \end{array}\right)}\end{displaymath} (22)

となる。ここで、
\begin{eqnarray*}\left(\begin{array}{c} N-1 \\ n-1 \end{array}\right)\frac{N-n}{... ...n}{n} \\ &=& \left(\begin{array}{c} N-1 \\ n \end{array}\right)\end{eqnarray*}


なので、(22) の両辺を $\left(\begin{array}{c} N-1 \\ n-1 \end{array}\right)$ 倍すれば
\begin{displaymath} \left(\begin{array}{c} N-1 \\ n \end{array}\right)F_3(N,n) =... ...ht)}{n(n+1)\left(\begin{array}{c} N \\ n+1 \end{array}\right)} \end{displaymath}

と書ける。 この最後の項は、
\begin{displaymath} \frac{\left(\begin{array}{c} N-1 \\ n-1 \end{array}\right)}{... ...(N-1)(N-2)\cdots(N-n+1)}{N(N-1)\cdots(N-n)} = \frac{1}{N(N-n)} \end{displaymath}

となるので、結局
\begin{displaymath} \left(\begin{array}{c} N-1 \\ n \end{array}\right)F_3(N,n) =... ...y}{c} N-1 \\ n-1 \end{array}\right)F_3(N,n-1)-\frac{1}{N(N-n)} \end{displaymath}

が成り立つことになる。 この右辺の最初の項は、左辺の $n$ を $(n-1)$ にした形になっているので 繰り返し代入すれば
\begin{eqnarray*}\lefteqn{\left(\begin{array}{c} N-1 \\ n \end{array}\right)F_3(... ...\frac{1}{N(N-1)}+\frac{1}{N(N-2)}+\cdots+\frac{1}{N(N-n)}\right\}\end{eqnarray*}


が得られる。ここで、
\begin{displaymath} F_3(N,0) = \int_0^{1}s^{N-1}\log sds = \left[\frac{s^N}{N}\l... ...s = -\left[\frac{s^N}{N^2}\right]_{s=0}^{s=1} = -\frac{1}{N^2} \end{displaymath}

なので、よって
\begin{displaymath} \left(\begin{array}{c} N-1 \\ n \end{array}\right)F_3(N,n) = -\frac{1}{N}\sum_{j=0}^n\frac{1}{N-j} \end{displaymath}

となり、結局 $F_3(N,n)$ は
\begin{displaymath} F_3(N,n) = \frac{-1}{N\left(\begin{array}{c} N-1 \\ n \end{... ...rray}{c} N \\ n+1 \end{array}\right)}\sum_{j=0}^n\frac{1}{N-j} \end{displaymath}

と表されることになる。よって (20) より、
\begin{eqnarray*}\mu(N,m) &=& -Nm\left(\begin{array}{c} N \\ m \end{array}\rig... ...}\frac{1}{N-j}\right\} %\\ &=& = \sum_{j=0}^{m-1}\frac{N}{N-j}\end{eqnarray*}


となり、これでようやく (3) と同じものが得られたことになる。

次へ: 参考文献 上へ: 配列内のランダムな配置の選択の評価 前へ: 7 μ(N,m)
竹野茂治＠新潟工科大学
2008年5月24日