モンモ-ル数(完全順列)[1]

モンモール数 \(a_n\) とは
「\(1\) から \(n\) までの数字が書かれたカードを、
\(1\) から \(n\) までの数字が書かれた箱に入れるとき、
カードの数字と箱の数字が一致しないように入れる」
ときの場合の数のことです。


\((1)\) モンモール数の漸化式$$a_n=(n-1)(a_{n-1}+a_{n-2})  (n \geq 3)  (a_1=0,\,a_2=1)$$

\((2)\) モンモール数の一般項$$a_n=n!\displaystyle\sum_{k=0}^n \frac{(-1)^k}{k!}$$











<証明>

\((1)\) 下の図のように、まず \(1\) 番目の箱に

\(1\) 以外の数字 (\(2,3,4 \cdots n\)) を入れることが出来るので \(n-1\) 通りです。

次に、例えば \(1\) 番目の箱に

\(2\) (\(1\) 以外なら何でも良い) を入れたときを考えます。

このとき、\(2\) 番目以降の箱に入れる数字を考えるとき、
次の \((α)(β)\) に分けて考えることが出来ます。

\((α)\) \(2\) 番目の箱に \(1\) のカードを入れるとき

残りの \(3,4,5 \cdots n\) 番目の箱に

\(3,4,5 \cdots n\) が書かれたカードを入れることになるので \(a_{n-2}\) 通りです。



\((β)\) \(2\) 番目の箱に \(1\) 以外のカードを入れるとき

すなわち、\(2\) 番目の箱に \(1\) のカードを入れないので

「\(2\) 番目の箱を \(1\) 番目の箱とみなして」考えれば

残りの \(1,3,4,5 \cdots n\) 番目の箱に

\(1,3,4,5 \cdots n\) が書かれた数字を入れることになるので \(a_{n-1}\) 通りです。



よって、次の漸化式を得ます。$$a_n=(n-1)(a_{n-1}+a_{n-2})  (n \geq 3)  (a_1=0,\,a_2=1)$$

この漸化式を用いて \(a_n\) のいくつかを計算してみます。
\begin{alignat}{2}
&a_3=(3-1)(a_2+a_1)=2(1+0)=2\\
&\\
&a_4=(4-1)(a_3-a_2)=3(2+1)=9\\
&\\
&a_5=(5-1)(a_4-a_3)=4(9+2)=44\\
&\\
&a_6=(6-1)(a_5-a_4)=5(44+9)=265\\
\end{alignat}








\((2)\) \((1)\) の漸化式を解きます。
\begin{alignat}{2}
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}\}\\
\end{alignat}\(a_n-na_{n-1}=b_n\) とおくと \(b_1=a_1-a_0=1\)$$b_n=-b_{n-1},  b_n=(-1)^n$$\(b_n\) を元に戻します。$$a_n-na_{n-1}=(-1)^n$$両辺を \(n!\) で割ります。$$\frac{a_n}{n!}-\frac{a_{n-1}}{(n-1)!}=\frac{(-1)^n}{n!}$$\(\displaystyle \frac{a_n}{n!}=c_n\) とおくと (\(c_1=0\))$$c_n-c_{n-1}=\frac{(-1)^n}{n!}$$\(n=2,3,4 \cdots \) のとき$$c_2-c_1=\frac{(-1)^2}{2!},  c_3-c_2=\frac{(-1)^3}{3!},  c_4-c_3=\frac{(-1)^4}{4!}, \cdots  c_n-c_{n-1}=\frac{(-1)^n}{n!}$$これらを全て足し合わせます。$$c_n=\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+\frac{(-1)^4}{4!}+ \cdots +\frac{(-1)^{n-1}}{(n-1)!}+\frac{(-1)^n}{n!}$$右辺に \(\displaystyle \frac{(-1)^0}{0!}+\frac{(-1)^1}{1!}=0\) を加えます。$$\frac{a_n}{n!}=\frac{(-1)^0}{0!}+\frac{(-1)^1}{1!}+\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+\frac{(-1)^4}{4!}+ \cdots +\frac{(-1)^{n-1}}{(n-1)!}+\frac{(-1)^n}{n!}=\displaystyle\sum_{k=0}^n \frac{(-1)^k}{k!}$$両辺に \(n!\) を掛けます。以上より$$a_n=n!\displaystyle\sum_{k=0}^n \frac{(-1)^k}{k!}$$

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です