2004年入試問題研究に戻る東工大後期解答
異なる $ n $ 個のものを，数 $ 1,\ 2,\ \cdots,\ n $ と数字で表す． $ n $ 個の場所に入る数字をそれぞれ $ x_1,\ x_2,\ \cdots,\ x_n $ で表す．
(1) $ x_1 $ で場合に分け，さらに， $ x_1=i $ のとき， $ x_i $ が1か否かで場合に分ける． これから \[ (x_1,\ x_2,\ x_3,\ x_4)= \left\{ \begin{array}{l} (2,\ 1,\ 4,\ 3),\ (2,\ 4,\ 1,\ 3),\ (2,\ 3,\ 4,\ 1)\\ (3,\ 4,\ 1,\ 2),\ (3,\ 1,\ 4,\ 2),\ (3,\ 4,\ 2,\ 1)\\ (4,\ 3,\ 2,\ 1),\ (4,\ 1,\ 2,\ 3),\ (4,\ 3,\ 1,\ 2) \end{array} \right. \] を得， $ D(4)=9 $ である．
【 $ D(4)=9 $ を求める別法I】
3文字，4文字の順列を，いくつ同じ位置にあるかで分けることにより， \[ \begin{array}{l} 3!=D(3)+{}_3\mathrm{C}_1D(2)+{}_3\mathrm{C}_2D(1)+{}_3\mathrm{C}_3\\ 4!=D(4)+{}_4\mathrm{C}_1D(3)+{}_4\mathrm{C}_2D(2)+{}_4\mathrm{C}_3D(1)+{}_4\mathrm{C}_4 \end{array} \] を得る． $ D(1)=0 $ ， $ D(2)=1 $ なので， \[ \begin{array}{l} D(3)=3!-3\cdot 1-1=2\\ D(4)=4!-4\cdot 2-6\cdot 1-1=9 \end{array} \] ※ これは，最初の解がすべてであることの別証となる．
【 $ D(4)=9 $ を求める別法II】 \[ \begin{array}{l} 4!=1+{}_4\mathrm{C}_3D(1)+{}_4\mathrm{C}_2D(2)+{}_4\mathrm{C}_1D(3)+D(4)\\ 3!=1+{}_3\mathrm{C}_2D(1)+{}_3\mathrm{C}_1D(2)+D(3)\\ 2!=1+{}_2\mathrm{C}_1D(1)+D(2)\\ 1!=1+D(1)\\ 0!=1 \end{array} \] より， $ D(1)=0 $ も用いて， \begin{eqnarray*} {}_4\mathrm{C}_44!&=&{}_4\mathrm{C}_4+{}_4\mathrm{C}_2D(2)+{}_4\mathrm{C}_1D(3)+D(4)\\ -{}_4\mathrm{C}_33!&=&-{}_4\mathrm{C}_3-{}_4\mathrm{C}_3{}_3\mathrm{C}_1D(2)-{}_4\mathrm{C}_3D(3)\\ {}_4\mathrm{C}_22!&=&{}_4\mathrm{C}_2+{}_4\mathrm{C}_2D(2)\\ -{}_4\mathrm{C}_11!&=&-{}_4\mathrm{C}_1\\ {}_4\mathrm{C}_00!&=&{}_4\mathrm{C}_0 \end{eqnarray*} とおき，辺々加える．ここで， \begin{eqnarray*} &&{}_4\mathrm{C}_4-{}_4\mathrm{C}_3+{}_4\mathrm{C}_2-{}_4\mathrm{C}_1+{}_4\mathrm{C}_0=(1-1)^4=0\\ &&{}_4\mathrm{C}_2-{}_4\mathrm{C}_3{}_3\mathrm{C}_1+{}_4\mathrm{C}_2=6-12+6=0 \end{eqnarray*} なので， \begin{eqnarray*} D(4)&=&{}_4\mathrm{C}_44!-{}_4\mathrm{C}_33!+{}_4\mathrm{C}_22!-{}_4\mathrm{C}_1+{}_4\mathrm{C}_0\\ &=&24-24+12-4+1=9 \end{eqnarray*} となる．
(2) $ i $ を $ 2,\ 3,\ \cdots,\ n $ のいずれかとする．
$ i $ は $ n-1 $ 通りなので， $ n\geqq 4 $ に対して \[ D(n)=(n-1)\{D(n-2)+D(n-1)\} \] がなりつ立つ．(i) $ x_1=i $ ， $ x_i=1 $ の場合：
残る $ n-2 $ の場所にもとの数字が来ないように並べるので， $ D(n-2) $ 通り．(ii) $ x_1=i $ ， $ x_i\ne 1 $ の場合：
$ 2,\ 3,\ \cdots,\ n $ から $ i $ を除いた $ n-2 $ の数字は元の位置に来ず， かつ1は $ x_i $ とはならないので，この並べ方は $ D(n-1) $ 通りある．※ $ D(1)=0 $ であるから $ n=3 $ でも成りたつ．
【 $ D(n) $ を求めるI】 記号の統一のため $ D(0)=1 $ とする．
(2)の漸化式を変形して \[ D(n)-nD(n-1)=-\{D(n-1)-(n-1)D(n-2)\} \] となる． $ D(n)-nD(n-1) $ が公比 $ -1 $ の等比数列なので， \[ D(n)-nD(n-1)=(-1)^{n-1}\{D(1)-D(0)\}=(-1)^n \] これから \[ \dfrac{D(n)}{n!}-\dfrac{D(n-1)}{(n-1)!}=\dfrac{(-1)^n}{n!} \] よって， \[ \dfrac{D(n)}{n!}=\dfrac{D(0)}{0!}+\sum_{j=1}^n\dfrac{(-1)^j}{j!} \] つまり， \[ D(n)=n!\left\{1-1+\dfrac{1}{2!}-\dfrac{1}{3!}+\cdots+\dfrac{(-1)^n}{n!} \right\} \] となる．【 $ D(n) $ を求めるII】 (1)の別法IIと同様に考える． \[ n!={}_n\mathrm{C}_{n}D(0)+{}_n\mathrm{C}_{n-1}D(1)+\cdots+{}_n\mathrm{C}_{n-k}D(k)+\cdots+{}_n\mathrm{C}_{0}D(n) \] である． $ (-1)^n{}_m \mathrm{C}_n $ を乗じて， $ n=0,\ 1,\ 2,\ \cdots,\ m $ にわたる和をとる． \begin{eqnarray*} (-1)^m{}_m \mathrm{C}_mm!&=&(-1)^m{}_m\mathrm{C}_{m}D(0)+\cdots+(-1)^m{}_m\mathrm{C}_{m-k}D(k)\\ &&\quad \quad \quad \quad \quad +\cdots+(-1)^m{}_m\mathrm{C}_{m-n}D(n)+\cdots+(-1)^m{}_m\mathrm{C}_{0}D(m)\\ \cdots \quad &=& \quad \cdots\\ (-1)^{n+1}{}_m \mathrm{C}_{n+1}(n+1)!&=&(-1)^{n+1}{}_m \mathrm{C}_{n+1}{}_{n+1}\mathrm{C}_{n+1}D(0)+\cdots +(-1)^{n+1}{}_m \mathrm{C}_{n+1}{}_{n+1}\mathrm{C}_{n+1-k}D(k)\\ &&\quad \quad \quad \quad \quad +\cdots+(-1)^{n+1}{}_m \mathrm{C}_{n+1}{}_{n+1}\mathrm{C}_{1}D(n)+(-1)^{n+1}{}_m \mathrm{C}_{n+1}{}_{n+1}\mathrm{C}_{0}D(n+1)\\ (-1)^n{}_m \mathrm{C}_nn!&=&(-1)^n{}_m \mathrm{C}_n{}_n\mathrm{C}_{n}D(0)+\cdots+(-1)^n{}_m \mathrm{C}_n{}_n\mathrm{C}_{n-k}D(k)\\ &&\quad \quad \quad \quad \quad +\cdots+(-1)^n{}_m \mathrm{C}_n{}_n\mathrm{C}_{0}D(n)\\ \cdots \quad &=& \quad \cdots\\ (-1)^0{}_m \mathrm{C}_00!&=&{}_0 \mathrm{C}_0D(0) \end{eqnarray*} $ 0\leqq n< m $ のとき， $ D(n) $ の係数は \begin{eqnarray*} \sum_{j=0}^{m-n}(-1)^{n+j}{}_m \mathrm{C}_{n+j}{}_{n+j} \mathrm{C}_j &=&\sum_{j=0}^{m-n}(-1)^{n+j}\dfrac{m!}{(m-n-j)!(n+j)!}\cdot\dfrac{(n+j)!}{n!j!}\\ &=&\dfrac{(-1)^nm!}{n!(m-n)!}\sum_{j=0}^{m-n}(-1)^{j}\dfrac{(m-n)!}{(m-n-j)!j!}\\ &=&\dfrac{(-1)^nm!}{n!(m-n)!}\sum_{j=0}^{m-n}{}_{m-n}\mathrm{C}_j(-1)^{j}=\dfrac{(-1)^nm!}{n!(m-n)!}(1-1)^{m-n}=0 \end{eqnarray*} である．よって， \begin{eqnarray*} (-1)^mD(m)&=&\sum_{n=0}^m(-1)^n{}_m \mathrm{C}_nn!\\ &=&m!\left\{\dfrac{1}{m!}-\dfrac{1}{(m-1)!}+\dfrac{1}{(m-2)!}-\cdots+(-1)^m \right\} \end{eqnarray*} $ m $ を $ n $ にとりなおして． \[ D(n)=n!\left\{1-1+\dfrac{1}{2!}-\dfrac{1}{3!}+\cdots+\dfrac{(-1)^n}{n!} \right\} \] となる．
※ このような順列を 完全順列という．これを研究した人の名を借りて， 数 $ D(n) $ をモンモール数という．
無作為に並べたとき，完全順列となる確率を $ P(n) $ とすると， \[ P(n)=\dfrac{D(n)}{n!}=1-1+\dfrac{1}{2!}-\dfrac{1}{3!}+\cdots+\dfrac{(-1)^n}{n!} \] である．そしてまた \[ \lim_{n \to \infty}P(n)=1-1+\dfrac{1}{2!}-\dfrac{1}{3!}+\cdots+\dfrac{(-1)^n}{n!}+\cdots=e^{-1} \] となる．
※ 0以上の整数で定義された2つの数列 $ \{a_n\},\ \{b_n\} $ の間に， \[ b_n=\sum_{k=0}^n{}_n\mathrm{C}_ka_k \quad \cdots ① \] という関係が，各 $ n $ に対してなりたつなら， \[ a_n=\sum_{k=0}^n(-1)^{n-k}{}_n\mathrm{C}_kb_k \quad \cdots ② \] がなりたつ．二項係数のとり方は， $ a_n=D(n) $ ， $ b_n=n! $ のとき逆になっているが，対称性から同じことである． 逆に，②が，各 $ n $ に対しなりたつなら，①がなりたつ．
まとめとして，その双方の証明を示しておく．また添え字の用い方も上記と少し変えている．
① $ \to $②：
\begin{eqnarray*} \sum_{k=0}^n(-1)^{n-k}{}_n\mathrm{C}_kb_k &=&\sum_{k=0}^n(-1)^{n-k}{}_n\mathrm{C}_k\left(\sum_{j=0}^k{}_k\mathrm{C}_ja_j \right) =\sum_{p=0}^n\left(\sum_{j=0}^p(-1)^{n-p}{}_n\mathrm{C}_p\cdot{}_p\mathrm{C}_ja_j \right)\\ &=&\sum_{p=0}^n\left(\sum_{i=0}^{n-p}(-1)^{n-p-i}{}_n\mathrm{C}_{p+i}\cdot{}_{p+i}\mathrm{C}_p\right)a_p\\ &=&\sum_{p=0}^n\left(\sum_{i=0}^{n-p}(-1)^{n-p-i}{}_n\mathrm{C}_{p}\cdot{}_{n-p}\mathrm{C}_i\right)a_p \\ &=&a_n+\sum_{p=0}^{n-1}(-1)^{n-p}{}_n\mathrm{C}_{p}\left(\sum_{i=0}^{n-p}(-1)^{-i}{}_{n-p}\mathrm{C}_i\right)a_p\\ &=&a_n+\sum_{p=0}^{n-1}(-1)^{n-p}{}_n\mathrm{C}_{p}(1-1)^{n-p}a_p =a_n \end{eqnarray*} 2行目から3行目は次の変形を用いた．
$ n $ 人から $ p+i $ 人選び，その $ p+i $ 人から $ p $ 人選ぶ場合の数と， $ n $人から $ p $ 人選び，残る $ n-p $ 人から $ i $ 人選ぶ場合の数は， いずれも， $ n $ 人から $ p $ 人と $ i $ 人の2つのグループをつくる場合の数であるから， \[ {}_n\mathrm{C}_{p+i}\cdot{}_{p+i}\mathrm{C}_k= {}_n\mathrm{C}_{p}\cdot{}_{n-p}\mathrm{C}_i \] がなりたつ．② $ \to $ ①： \begin{eqnarray*} \sum_{k=0}^n{}_n\mathrm{C}_ka_k &=& \sum_{k=0}^n{}_n\mathrm{C}_k\left(\sum_{j=0}^k(-1)^{k-j}{}_k\mathrm{C}_jb_j \right) =\sum_{k=0}^n\left(\sum_{j=0}^k(-1)^{k-j}{}_n\mathrm{C}_k\cdot{}_k\mathrm{C}_jb_j \right)\\ &=&\sum_{p=0}^n\left(\sum_{i=0}^{n-p}(-1)^{p+i-p}{}_n\mathrm{C}_{p+i}\cdot{}_{p+i}\mathrm{C}_p\right)b_p\\ &=&\sum_{p=0}^n\left(\sum_{i=0}^{n-p}(-1)^{i}{}_n\mathrm{C}_{p}\cdot{}_{n-p}\mathrm{C}_i\right)b_p \\ &=&b_n+\sum_{p=0}^{n-1}{}_n\mathrm{C}_{p}\left(\sum_{i=0}^{n-p}(-1)^{i}{}_{n-p}\mathrm{C}_i\right)b_p =b_n+\sum_{p=0}^{n-1}{}_n\mathrm{C}_{p}(1-1)^{n-p}b_p=b_n \end{eqnarray*}
※ これはある種の反転公式である．これについては，VISUAL数学を目指しての中の「全順列，全射，円順列の総数－反転公式および和集合の要素数に関する公式の利用」に教えられた．