院試を解く3 秘書問題

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