文献あり

平成29年国際信州学院大学観光学部　数学第二問

277

中身の見えない袋の中に、 $A, E, L, P$ の文字のいずれか１つが書かれた４つの球がある。「袋から無作為に球を取り出し、書かれた文字列が記録して袋に戻す」という操作を繰り返し、「 $APPLE$ 」という文字列が記録されたら作業を終了する。ちょうど $n$ 回の操作で作業が終了する確率を求めよ。 (国際信州学院大学 H29)

解答

$n$ 回で作業が終了する確率を $p_{n}$ 、 $n$ 回の作業で「 $APPLE$ 」の文字列が含まれている確率を $S_{n}$ とする。
$p_{n} = S_{n} - S_{n - 1}$ である。
まずは具体的に考えてみよう。
$1 \leq n \leq 4$ のときは勿論 $S_{n} = 0$ 。
$5 \leq n \leq 9 ならば S_{n} = \frac{n - 4}{4^{5}}$ となる。
(例えば $n = 9$ のとき、
$APPLE????$ 、 $?APPLE???$ 、 $??APPLE??$ 、 $???APPLE?$ 、 $????APPLE$ のパターンが考えられ、それぞれは独立である。)
$10 \leq n \leq 14$ の場合、 $APPLE$ が異なる場所に2つできるため、先ほどの「 $APPLE$ がある場所1つにできる場合全体」の中で重ねて数えてしまっているものがある。
$APPLE$ が2つ出来る場所の総数が分かれば求められそうだ。
$APPLE$ 2つとその10文字を除いた他の文字との並べ替えになるので、 $\frac{(n - 10 + 2)!}{2! (n - 10)!} =_{n - 8} C_{2}$ 通りとなる。
よって $10 \leq n \leq 14$ のとき、 $S_{n} = \frac{n - 4}{4^{5}} - \frac{_{n - 8} C_{2}}{4^{10}}$
$\dots$ といったことを $APPLE$ が $⌊ \frac{n}{5} ⌋$ 個あるときまで繰り返すだけです。
( $⌊ x ⌋$ は $x$ を超えない最大の整数のことです。)
$⌊ \frac{n}{5} ⌋$ 個まで繰り返すのはいいのですが $15 \leq n$ のときの議論があんまり自明じゃないので、少し深堀していきます。

$r$ 個の集合の和集合の要素の個数

「 $APPLE$ 」が2個のとき、重複した分を引いてあげるため、その確率を引き算していましたが、一般に「 $APPLE$ 」が $r$ 個ある場合はどう対応すればよいのでしょうか。

実は、以下のような公式があります。

r

個の和集合の要素の個数

$r$ 個の和集合 $A_{1}, A_{2}, \dots, A_{r}$ の和集合 $A_{1} \cup A_{2} \cup \dots \cup A_{r}$ の要素の個数について、以下が成り立つ。
$n (A_{1} \cup A_{2} \cup \dots \cup A_{r}) = \sum_{k = 1}^{r} (- 1)^{k - 1} \sum_{i_{1} < i_{2} < \dots < i_{k}} n (A_{i_{1}} \cap A_{i_{2}} \cap \dots \cap A_{i_{k}})$

つまり今回の例でいうと「 $APPLE$ 」がある場所に奇数個あるときは足して、偶数個あるときは引く、ということです。

任意の $a \in A_{1} \cup A_{2} \cup \dots \cup A_{r}$ に対して、右辺の式を適用して $a$ が合計何回足されるかを確かめる。
(略記: $j := j_{1}, j_{2} \dots j_{k}$ )
$a \in A_{j_{1}} \cap \dots \cap A_{j_{k}}$ かつ $a \notin ⋃_{l \notin j} A_{l} (1 \leq l, j \leq r)$ である、(つまり、ある $k$ 個の集合の中に $a$ は入っているが、それ以外の集合に $a$ は入っていない)と仮定すると、
$n (A_{i_{1}})$ の項では $k$ 個の数字の中から1つ選ぶので $_{k} C_{1}$ 回足され、
$n (A_{i_{1}} \cap A_{i_{2}})$ の項では $k$ 個の数字の中から2つ選ぶので $_{k} C_{2}$ 回引かれ、
$n (A_{i_{1}} \cap A_{i_{2}} \cap A_{i_{3}})$ の項では $k$ 個の数字の中から3つ選ぶので $_{k} C_{3}$ 回足され、
$\dots$
と繰り返していけば、
$a$ が足された回数は、 $\sum_{m = 1}^{k} (- 1)^{m + 1}_{k} C_{m}$ 回と分かり、 $(1 - 1)^{k}$ に対する
二項定理より
$\sum_{m = 0}^{k} (- 1)^{m + 1}_{k} C_{m} = -_{k} C_{0} + \sum_{m = 1}^{k} (- 1)^{m + 1}_{k} C_{m} = 0$ であるから、 $\sum_{m = 1}^{k} (- 1)^{m + 1}_{k} C_{m} = 1$ である。
よって、任意の $a$ に対して右辺は1回足されるので、右辺の計算結果は和集合の要素の個数に等しい。

この証明はこちらのものをほとんど引用させていただいております。
あとは「 $APPLE$ 」が $r$ 個あるときの場所のパターン数は、残りの $n - 5 r$ 個と文字を並び替えるので $\frac{(n - 5 r + r)!}{r! (n - 5 r)!} =_{n - 4 r} C_{r}$ 通りとなる。
よって、 $\sum_{k = 1}^{0} = 0$ とすれば、
$S_{n} = \sum_{k = 1}^{⌊ \frac{n}{5} ⌋} (- 1)^{k - 1} \cdot \frac{_{n - 4 k} C_{k}}{4^{5 k}}$
$\begin{array}{rcl} p_{n} & = & S_{n} - S_{n - 1} \\ = & \sum_{k = 1}^{⌊ \frac{n}{5} ⌋} (- 1)^{k - 1} \cdot \frac{_{n - 4 k} C_{k}}{4^{5 k}} - \sum_{k = 1}^{⌊ \frac{n - 1}{5} ⌋} (- 1)^{k - 1} \cdot \frac{_{n - 4 k - 1} C_{k}}{4^{5 k}} \end{array}$
(この式にパスカルの法則: $_{n} C_{r} =_{n - 1} C_{r} +_{n - 1} C_{r - 1}$ を上手く適用出来れば総和をまとめることが出来ることに注目する。)
ここで、シグマの上限が異なっているとまとめ上げることが出来ないので、 $S_{n - 1}$ の項のシグマの上限を $⌊ \frac{n}{5} ⌋$ に変更したものを考える。 $n$ が $5$ の倍数でないときはどちらも同じである。
では $n$ が $5$ の倍数、つまり整数 $t$ を用いて $n = 5 t$ と表せるとき、
上限は $k = t$ となり、 $_{n - 4 k - 1} C_{k} =_{t - 1} C_{t}$ と表せるので、コンビネーションの定義外となる。これを $0$ と置けば、結果的にシグマの上限を変えたものも値が変わらないことになり、
$n = r$ のときにもパスカルの法則:
$_{n} C_{n} =_{n - 1} C_{n} +_{n - 1} C_{n - 1}$
が成り立つことが分かる。よって、
$p_{n} = \sum_{k = 1}^{⌊ \frac{n}{5} ⌋} (- 1)^{k - 1} \cdot \frac{_{n - 4 k - 1} C_{k - 1}}{4^{5 k}}$
と分かる。

一般化

同様の議論をすることにより、以下のような公式が得られます。

$s$ 種類の文字が同様の確率で出力されて $n$ 文字の文字列を生成する。また、その $s$ 種類の文字の中から $m$ 文字のキーワードを設定するとき、
先頭の $a$ 文字と末尾 $a$ 文字が $1 \leq a \leq m - 1$ のいずれの $a$ に対しても等しくないときに限り、 $n$ 文字でそのキーワードが生成される確率 $p_{n}$ は、
$p_{n} = \sum_{k = 1}^{⌊ \frac{n}{m} ⌋} (- 1)^{k - 1} \cdot \frac{_{n - (m - 1) k - 1} C_{k - 1}}{s^{m k}}$
となる。

例外について：例えば「ア」「コ」「の」「ラ」という文字と「コアラのコア」というキーワードを設定したとします。すると、重複して数えてしまっている場合が多くなってしまいます。本来、この場合だと6文字周期で被りを考えるのですが、「コアラのコアラのコア」などというように、末尾と先頭が繋がってしまうとその部分の重複も除かなければならなくなります。これが存外面倒なので今回は考えてません。
(コアラのコアに関する先行研究をしておらず、同名のキャラクターがどうやら存在しているので、只今別の例を模索中です。)