大阪大学 1986年度
理系数学 第5問

解答

(1)

1回目に袋 $A$ から取り出される番号は，必ず $1,2,\dots ,n$ の並べ替えである。そこで，1回目に取った番号の小さい順に人を並べる。この並べ替えをしても，2回目の番号が1回目の番号より大きいかどうかは変わらない。

したがって，$i$ 番目の人は1回目に番号 $i$ を取ったとしてよい。2回目に袋 $B$ から配る番号は相異なるので，求める条件は $i\text{ 番目の人に，}i\text{ より大きい番号を割り当てる}$ ことである。

このような割り当ての数を $F(n,m)$ とする。最後の $n$ 番目の人には，$n$ より大きい番号を渡す必要があるから $n+1,n+2,\dots ,m$ の $m-n$ 通りがある。その番号を一つ選んで取り除く。残りの $n-1$ 人については，袋 $B$ の番号が一つ減っただけで同じ形の問題になる。

実際，取り除いた番号を $j$ とすると $j>n$ である。残った番号のうち $j$ より大きいものを1ずつ小さくして番号を詰めても，$1,2,\dots ,n-1$ 番目の人に対する条件「$i$ より大きい」は変わらない。よって $F(n,m)=(m-n)F(n-1,m-1)$ である。初期値 $F(0,m)=1$ としてこの関係を繰り返すと，差 $m-n$ は変わらないので $F(n,m)=(m-n{)}^n$ を得る。

一方，袋 $B$ から $n$ 人に相異なるカードを配る全体の場合の数は $m(m-1)\cdots (m-n+1)=\frac{m!}{(m-n)!}$ である。したがって

である。

(2)

$m=2n$ とすると $P_{n,2n}=\frac{n^{n}n!}{(2n)!}$ である。よって

である。

ここで $N!$ の対数を評価する。$\log x$ は増加関数なので ${\int }_1^N\log xdx\leqq \log N!\leqq {\int }_1^{N+1}\log xdx$ が成り立つ。両端を計算すると $N\log N-N+1\leqq \log N!\leqq (N+1)\log (N+1)-(N+1)+1$ である。これを $N$ で割ると $\frac{1}{N}\log N!=\log N-1+o(1)(N\to \infty )$ を得る。

したがって $\frac{1}{n}\log n!=\log n-1+o(1)$ であり，また $\frac{1}{n}\log (2n)!=2\left(\log (2n)-1+o(1)\right)$ である。これらを代入すると

となる。よって

である。