|123 いそます もとの位置に戻って
W(1)=0, W(2)=1, W(n)=(n-1){W(n-1)+W(n-2)} (n23)
例 題 208 完全順列
1, 2, 3, 4, ……, nを並びかえたとき, どの数字ももとの位置にいない
ように並べたものをn個の完全順列といい, その総数を W(n) と書く
(1) W(2), W(3) を求めよ。
(2) W(4)=3(W(3)+W(2)) であることを示し,W (4) を求めよ。
考え方(1) 実際に並べて数え上げる。
(2) 1, 2, 3のときに4をつけ加えて考えてみるとよい。 白 5em
解答
12
いい いる並び方を省いて
小 いけばよい。
|n=2 のとき,
1→2
n=3 のとき,
× 2
*23
× 3 2
×213参歩
用
人化 大一
O|2 1
○|2 3 1
○|3 12
W(2)=1
W(3)=2
よって、
3.-2 32
1が1番目に行くと
不適である。
|2, 3, 4が1~3番
目に並ぶと考える。
2と3の2つの数字
の完全順列なので、
W(2)=1
×|3 21
(2) 1の行き場所は1番目以外の
3通り、
| ここで、1が4番目に行ったと
(x, ○, O, "O)
する。
(i) 4が1番目に行く場合
1る o (1, 2, 3, 4) → (4, ○, O, 1)
0 残りの2つの数字の完全順列を考えて,W(2)=1
) 4が1番目以外に行く場合
4を1と考えると,「4が1 (1, 2, 3, 4) S →(O, O, O, 1)
番目以外」は「1が1番目以
2, 3, 4
ここで、
「4分1, 2→2, 33」
だから,4を1と
の 外」と考えられるので, 1, 2,
3の3つの数字の完全順列を考えればよい。
したがって,
よって,1が2番目, 3番目に行っても同様に考えら
れるから,(i), ()より,
W(4)=3(W(3)+ W(2))=3(2+1)=9
W(3)=2
M ww
き直すと、
+11→1, 2→2, 3→3』
( となり, 3つの数子
る
A の完全順列と同じに
なる。
に、n個の数1, 2, 3, …, nの完全順列の総数を W(n) とすると
このような式を漸化式という。(数学B「数列」で学)
また, W(n) を, モンモール数という。
