院試を解く3 秘書問題

(1)候補者の並べ方は全部で$4!$通り.その中で$1$位の人を取る場合を数える.
$2$人目で取るとき他$3$人の並べ方は何でもよいから$3!$通り.$3$人目で取るとき$1$番目の候補者の順位が$2$番目の候補者の順位より小さければよくそのような数のペアは$_3C_2$通り.$4$人目で取るとき$1$人目の順位が$2$になりその場合は$3$と$4$の並べ方で$2$通り.
よって求める確率は$\dfrac{3!+3+2}{4!}=\dfrac{11}{24}$
(2)$10$人の並べ方は$10!$通り.$k\geq 3$とする.$k$人目で$1$位の人を採用するのは最初の$k-1$人の内の最小順位の人が最初の$2$人のどちらかである場合で他の$k-2$人の並べ方と$k+1$番目以降の$10-k$人の並べ方は自由だから最初の$k-1$人の選び方も考えて$2\cdot _9C_{k-1}(k-2)!(10-k)!$通り.
よって$P_{10}(3)=\displaystyle\sum_{k=3}^{10}\dfrac{1}{10!}2\cdot_9C_{k-1}(k-2)!(10-k)!$
$=\displaystyle\sum_{k=3}^{10}\dfrac{1}{10!}\dfrac{2\cdot9!(k-2)!(10-k)!}{(10-k)!(k-1)!}$
$=\displaystyle\sum_{k=3}^{10}\dfrac{2}{10}\dfrac{1}{k-1}$
となる.
(3)$n$人の並べ方は$n!$通り.$k$人目で$1$位の人を採用するのは最初の$k-1$人の内の最小順位の人が最初の$r-1$人のどれかである場合で他の$k-2$人の並べ方と$k+1$番目以降の$n-k$人の並べ方は自由だから最初の$k-1$人の選び方も考えて$(r-1)\cdot _{n-1}C_{k-1}(k-2)!(n-k)!$通り.
よって$\dfrac{1}{n!}(r-1)\cdot _{n-1}C_{k-1}(k-2)!(n-k)!$
$=\dfrac{1}{n!}\dfrac{(r-1)\cdot (n-1)!(k-2)!(n-k)!}{(n-k)!(k-1)!}$
$=\dfrac{r-1}{n(k-1)}$.
(4)(3)で求めた確率を$k=1,…,n$に渡って足すと$P_n(r)$になるから
$P_n(r)=\displaystyle \sum_{k=r}^{n}\dfrac{r-1}{n(k-1)}$.これより
$P_n(r+1)=\dfrac{1}{n}+\dfrac{r-1}{r}P_n(r+1)$
(5)(4)から計算する.$n$が十分大きいとき$\sum \dfrac{1}{k}$と$\text{log}$との差は無視できて$P_n(r)=\displaystyle \sum_{k=r}^{n}\dfrac{r-1}{n(k-1)}=\dfrac{r}{n}\dfrac{r-1}{r}(\displaystyle \sum_{k=1}^{r-1}\dfrac{1}{k}-\sum_{k=1}^n\dfrac{1}{k})$
$\risingdotseq q(\text{log}r-\text{log}n)=-q\text{log}q$.微分により最大値は$\dfrac{1}{e}$で取る.