同じ種類の文字が続く部分の個数と確率

問題です。解答は下部に載せました。

問題： $\displaystyle { n }$ 種の文字からランダムに $\displaystyle { m }$ 個の文字を選び１列に並べる。このとき、同じ種類の文字が続く部分（１文字でもよい）が $\displaystyle { k }$ 個ある並べ方の数 $\displaystyle { N \left( k \right) }$ とその確率 $\displaystyle { P \left( k \right) }$ を求めよ。また、 $\displaystyle { P \left( k \right) }$ が最大となる $\displaystyle { k }$ を求めよ。

解答：同じ種類の文字が続く部分の仕切り方は $\displaystyle { \binom{m-1}{k-1} }$ 通りある。

次に、仕切られた部分への文字の当てはめ方を考える。 $\displaystyle { k }$ 個の仕切られた部分から任意にひとつをとり、その部分に $\displaystyle { n }$ 通りの文字を当てはめるとすれば、その両隣りの部分は重複がないようにすると $\displaystyle { n - 1}$ 通りの文字の当てはめ方が考えられる。同様にして、始めに指定した仕切られた部分以外は $\displaystyle { n - 1}$ 通りの文字の当てはめ方があるとわかるので、結局、仕切られた部分への文字の当てはめ方は $\displaystyle { n \left( n - 1 \right) ^{k - 1} }$ 通りある。よって、

$\displaystyle { N \left( k \right) = n \left( n - 1 \right) ^{k - 1} \cdot \binom{m-1}{k-1} = n \left( n - 1 \right) ^{k - 1} \cdot \frac{\left( m - 1 \right) !}{\left( m - k \right) ! \left( k - 1 \right) ! } }$

となる。また、 $\displaystyle { n }$ 種の文字からランダムに $\displaystyle { m }$ 個の文字を選び１列に並べるときの並べ方の総数は $\displaystyle { n^m }$ 通りなので、

$\displaystyle { P \left( k \right) = \frac{N \left( k \right)}{n^m} = \frac{\left( n - 1 \right) ^{k - 1}}{n^{m-1}} \cdot \frac{\left( m - 1 \right) !}{\left( m - k \right) ! \left( k - 1 \right) ! } }$

となる。

続いて、 $\displaystyle { P \left( k \right) }$ が最大となる $\displaystyle { k }$ を求める。これは、次の不等式を満たす最大の $\displaystyle { k }$ に等しい。

$\displaystyle { \frac{P \left( k \right)}{P \left( k - 1 \right)} = \left( n - 1 \right) \cdot \frac{m - k + 1}{k - 1} \geq 1 }$

上の不等式を変形すると、

$\displaystyle { m + 1 - \frac{m}{n} \geq k }$

となり、求める $\displaystyle { k }$ はこの不等式を満たす最大の $\displaystyle { k }$ である。

補足：明らかに、

$\displaystyle { \sum _{k = 1} ^m N \left( k \right) = \sum _{k = 1} ^m n \left( n - 1 \right) ^{k - 1} \cdot \frac{\left( m - 1 \right) !}{\left( m - k \right) ! \left( k - 1 \right) ! } = n^m }$

が成り立つ。よって、 $\displaystyle { P \left( k \right) }$ は、

$\displaystyle { \sum _{k = 1} ^m P \left( k \right) = \sum _{k = 1} ^m \frac{\left( n - 1 \right) ^{k - 1}}{n^{m-1}} \cdot \frac{\left( m - 1 \right) !}{\left( m - k \right) ! \left( k - 1 \right) ! } = 1 }$

を満たす。

下のグラフは、 $\displaystyle { n = 5 }$ 、 $\displaystyle { m = 100 }$ のときの、 $\displaystyle { P \left( k \right) }$ を縦軸に取り、横軸に $\displaystyle { k }$ を取ったものです。