ta1人が、A, B, C, D, E と書かれたくじを引いてペア替え
W(1)=0, W(2)=1, W(n)=(n-1){W(n-1)+W(n-2)} (n>3)
366 第6章 場
例題 208 完全順列
ように並べたものをn個の完全順列といい, その総数を W(n) と書く
(1) W(2), W(3) を求めよ。
(2) W(4)=3(W(3)+ W(2)) であることを示し, W(4) を求めよ。
(1) 実際に並べて数え上げる。
(2) 1, 2, 3のときに4をつけ加えて考えてみるとよい。
考え方
もとの位置に戻って
いる並び方を省いて
味 いけばよい
n=2 のとき,
1→2
解答
12
123
こみ
×|X 2
×| 23
○|2-1
×|* 3 2
×|2 13
○|2 3 1
n=3 のとき,
W(2)=1
W(3)=2
○|3 12
よって,
×|3 2 1
2 3、2
1が1番目に行くと,
不適である。
2, 3, 4が1~3番
目に並ぶと考える。.
(2) 1の行き場所は1番目以外の
3通り、
1 込ここで, 1が4番目に行ったと
(×, ○, 0, "O)
する。
(i) 4が1番目に行く場合
2と3の2つの数字
の完全順列なので、,
W(2)=1
0 の す残りの2つの数字の完全順列を考えて, W(2)=1
合(i) 4が1番目以外に行く場合
1 4を1と考えると, 「4が1 (1, 2, 3, 4)
番目以外」は「1が1番目以
外」と考えられるので, 1, 2,
3の3つの数字の完全順列を考えればよい。
W(3)=2
2, 3, 4
る したがって,
よって,1が2番目, 3番目に行っても同様に考えら
ここで、
「41, 2→2, 3→3」
だから,4を1と書
き直すと,
w
れるから,(i), (i)より,
W(4)=3(W(3)+W(2))=3(2+1)=9
べへ
( となり, 3つの数子
の完全順列と同じに
なる。
nの完全順列の総数を W(n) とすると、
注》一般に,n個の数1, 2, 3, ……,
また, W(n) を, モンモール数という.。
徳習
