元全順列
nの数字を1列に並べた順列のうちどのを番目の数もんでないものを完全順タ列という。
上の解答のように,完全順列の数を調べるには 樹形図をかく とよい。
また,n個の数の順列1, 2, ….. nの完全順列の個数を W(n) とすると
ーn=2のとき [2]Iの1通り。
W(3)=2
W(1)=0, W(2)=1
3個の数の完全順列には
次に,4個の数の完全順列は, 左から1番目が[2のとき, [2■4[3, [2] [3[4|[1, [2][4I3の
3通りあり,1番目が「3, 4 のときも同様であるから
更に,5個の数の完全順列は, 次のように考えることができる。 左から5番目を4 として
[1] 左から4番目が5であるとき, 残り 213の並べ方は
[2] 左から4番目が5でないとき, 口[235の[5は4番目にないから, [5]を 4におき換え
たI234の並べ方と考えても同じである。ゆえに
左から5番目は, I, [2, 3, 4の4通りあるから
以後,同様に考えると, 完全順列の数は, 一般に次のように表される。
[2]3回, 3I2 の2通りあるから
W(4)=3×3=9
W(3)=2 (通り)
W(4)=9 (通り)
W(5)=4×{W(3)+W(4)}=44
W(1)=0, W(2)=1, W(n)=(n-1){W(n-1)+W(n-2)}(n>3)
右の図のようなマス目を考える。 どの行(横の並び)にも, どの
列(縦の並び)にも同じ数が現れないように1から4まで自然
数を入れる入れ方の場合の数 Kを求めよ。
練習
15
2
1
3|4
3
【類埼玉大)
1
4
2|3
