早稲田大学(理系) 2025年 問題Ⅲ
$1\ から \ n\ までの異なる自然数が \ 1\ つずつ書かれた \ n\ 枚のカードが一列に並んでいる。このとき、どのカードも$
$現在とは異なる位置に移動するように並べ替えてできる順列の総数を \ a_n \ で表し、並べ方の総数 \ n!\ に占めるa_n $
$の割合を \ p_n \ で表す。例えば、a_1=0,\ \ p_1=0,\ \ a_2=1,\ \ p_2=\dfrac{1}{2},\ \ a_3=2,\ \ p_3=\dfrac{1}{3}\ \ である。次の問に答えよ。$
$(1)\ \ a_4\ の値を求めよ。$
$(2)\ \ n \geqq 3 \ \ のとき、a_n \ を \ a_{n-1}\ と \ a_{n-2}\ を用いて表せ。$
$(3)\ \ n \geqq 2 \ \ のとき、p_n -p_{n-1}\ \ を \ n\ を用いて表せ。$
(1)
$1\ から \ n\ までの\ n\ 枚のカードの並びを \ \ (1,\ 2,\ 3,\ \cdots,\ n)\ \ と表し、どのカードも現在とは異なる位置に$
$移動するように並べ替えてできる順列を \ \ (q_1,\ q_2,\ \cdots,\ q_n)\ \ と表すことにする。$
$n=2\ \ のとき \ \ (2,\ 1)\ \ の \ 1\ 通りだから \ \ a_2=1$
$n=3\ \ のとき \ \ (2,\ 3,\ 1),\ \ (3,\ 1,\ 2)\ \ の \ 2\ 通りだから \ \ a_3=2$
$n=4\ \ のときは$
$\quad (2,\ 1,\ 4,\ 3),\ \ (2,\ 3,\ 4,\ 1),\ \ (2,\ 4,\ 1,\ 3),$
$\quad (3,\ 1,\ 4,\ 2),\ \ (3,\ 4,\ 1,\ 2),\ \ (3,\ 4,\ 2,\ 1),$
$\quad (4,\ 1,\ 2,\ 3),\ \ (4,\ 3,\ 1,\ 2),\ \ (4,\ 3,\ 2,\ 1),$
$の \ 9\ 通りだから \ \ a_4=9$
(2)
$n\ 枚のカードを並べ替えてできる順列\ \ (q_1,\ q_2,\ \cdots,\ q_k,\ \cdots ,\ q_n)\ \ は$
$q_1\ は \ 1\ 以外だから \ \ (n-1)\ 通り、このとき \ q_k \ \ (2 \leqq k \leqq n)\ \ は$
(i)$\ \ 1でない$
(ii)$\ \ 1である$
$のどちらかである。$
(i)$\ \ のとき$
$\quad 残りの数字は、q_1 \ を除く \ (n-1)\ 個だからこれらを並び替えてできる順列は \ \ a_{n-1}\ 通り$
(ii)$\ \ のとき$
$\quad 残りの数字は、q_1 \ と \ 1\ を除く \ (n-2)\ 個だからこれらを並び替えてできる順列は \ \ a_{n-2} \ 通り$
$したがって$
$a_n=(n-1)(a_{n-1}+a_{n-2})$
$なお、この漸化式を利用して(1)を求めると$
$a_4=3(a_3+a_2)=3(2+1)=9$
(3)
$a_n=(n-1)(a_{n-1}+a_{n-2})$
$a_n -na_{n-1}=-a_{n-1}+(n-1)a_{n-2}$
$a_n -na_{n-1}=-(a_{n-1}-(n-1)a_{n-2})$
$a_n-na_{n-1}=b_n \ \ とおくと$
$b_n=-b_{n-1} \quad b_2=a_2-2a_1=1$
$b_n=b_2 \times (-1)^{n-2}$
$右辺=(-1)^{n-2} \times (-1)^2=(-1)^n$
$よって \quad a_n-na_{n-1}=(-1)^n$
$両辺を \ n!\ で割って$
$\cfrac{a_n}{n!}-\cfrac{a_{n-1}}{(n-1)!}=\cfrac{(-1)^n}{n!}$
$\cfrac{a_n}{n!}=p_n \quad だから$
$\quad p_n-p_{n-1}=\cfrac{(-1)^n}{n!} \quad ただし \ \ p_1=0$
$(補充)$
$この順列を「完全順列」といい、a_n \ を「モンモール数」といいます。$
$完全順列の一般項の求め方については「$完全順列$」をご覧ください。$
メインメニュー に戻る