方針・初手

確率は「場合の数の比」で数えるのが最も自然である。

集合 $T$ の大きさは $r+n$ であり，そこから $r+k$ 個を一様に選ぶ。 このとき，集合 $S={1,2,\dots,r}$ の元がすべて含まれるためには，$S$ の $r$ 個を必ず取り，残り $k$ 個を $T\setminus S$ の $n$ 個から選べばよい。

(2) では，(1) で得た式を階差の形に直して望遠和にする。

解法1

(1)

$T$ から $r+k$ 個を選ぶ総数は

$$ {}_{r+n}\mathrm{C}_{r+k} $$

である。

一方，$S$ の元がすべて含まれるためには，$S$ の $r$ 個は全て選ばれていなければならない。 したがって，残り $k$ 個を $T\setminus S$ の $n$ 個から選ぶので，有利な場合の数は

$$ {}_{n}\mathrm{C}_{k} $$

である。

よって

$$ a_n=\frac{{}_{n}\mathrm{C}_{k}}{{}_{r+n}\mathrm{C}_{r+k}} $$

となる。

これを階乗で表せば

$$ a_n === # \frac{\dfrac{n!}{k!(n-k)!}}{\dfrac{(r+n)!}{(r+k)!(n-k)!}} \frac{(r+k)!}{k!}\cdot\frac{n!}{(r+n)!} $$

である。

---

(2)

まず

$$ \frac{n!}{(n+r)!} ================= \frac{1}{r-1} \left( \frac{n!}{(n+r-1)!} ------------------- \frac{(n+1)!}{(n+r)!} \right) $$

が成り立つ。実際，

$$ \frac{n!}{(n+r-1)!} ------------------- # \frac{(n+1)!}{(n+r)!} \frac{n!}{(n+r-1)!} \left( 1-\frac{n+1}{n+r} \right) ======= (r-1)\frac{n!}{(n+r)!} $$

である。

したがって

$$ a_n === \frac{(r+k)!}{k!(r-1)} \left( \frac{n!}{(n+r-1)!} ------------------- \frac{(n+1)!}{(n+r)!} \right) $$

となる。

ここで，問題文の条件より $a_n$ が定まるのは $n\ge k$ のときであるから，級数は実質的に

$$ \sum_{n=\max{1,k}}^\infty a_n $$

を考えればよい。

(i) $k=0$ のとき

このとき下端は $n=1$ であるから，

$$ \sum_{n=1}^{N} a_n ================== \frac{r!}{(r-1)} \sum_{n=1}^{N} \left( \frac{n!}{(n+r-1)!} ------------------- \frac{(n+1)!}{(n+r)!} \right) $$

$$ \frac{r!}{(r-1)} \left( \frac{1!}{r!} ------------- \frac{(N+1)!}{(N+r)!} \right) $$

となる。

$r\ge2$ より

$$ \frac{(N+1)!}{(N+r)!} ===================== \frac{1}{(N+2)(N+3)\cdots(N+r)} \to 0 \qquad(N\to\infty) $$

なので，

$$ \sum_{n=1}^\infty a_n ===================== # \frac{r!}{r-1}\cdot\frac{1}{r!} \frac{1}{r-1} $$

である。

(ii) $k\ge1$ のとき

このとき下端は $n=k$ であるから，

$$ \sum_{n=k}^{N} a_n ================== \frac{(r+k)!}{k!(r-1)} \sum_{n=k}^{N} \left( \frac{n!}{(n+r-1)!} ------------------- \frac{(n+1)!}{(n+r)!} \right) $$

$$ \frac{(r+k)!}{k!(r-1)} \left( \frac{k!}{(k+r-1)!} ------------------- \frac{(N+1)!}{(N+r)!} \right) $$

となる。

再び $r\ge2$ より $\dfrac{(N+1)!}{(N+r)!}\to0$ であるから，

$$ \sum_{n=1}^\infty a_n ===================== # \sum_{n=k}^\infty a_n # \frac{(r+k)!}{k!(r-1)}\cdot\frac{k!}{(k+r-1)!} \frac{r+k}{r-1} $$

である。

解説

この問題の本質は，まず確率を直接数え上げることである。 「$S$ の元がすべて含まれる」という条件は，$S$ の $r$ 個を固定してしまえば，残りをどこから選ぶかという単純な組合せになる。

(2) では

$$ \frac{n!}{(n+r)!} $$

をそのまま足すのではなく，階差

$$ \frac{n!}{(n+r-1)!} ------------------- \frac{(n+1)!}{(n+r)!} $$

に直すのが典型手法である。これにより望遠和となり，有限個の端の項だけが残る。

また，$k=0$ のときは和の下端が $1$，$k\ge1$ のときは下端が $k$ になるので，そこを分けて扱う必要がある。

答え

$$ a_n=\frac{{}_{n}\mathrm{C}_{k}}{{}_{r+n}\mathrm{C}_{r+k}} = \frac{(r+k)!}{k!}\cdot\frac{n!}{(r+n)!} \qquad(n\ge k) $$

また，$r\ge2$ のとき

$$ \sum_{n=1}^\infty a_n = \begin{cases} \dfrac{1}{r-1} & (k=0),\\[1.2ex] \dfrac{r+k}{r-1} & (k\ge1). \end{cases} $$

である。