-
354
重要 例題 15 完全順列(k番目の数がんでない順列)
00000
5人に招待状を送るため, あて名を書いた招待状と,それを入れるあて名を書い
た封筒を作成した。 招待状を全部間違った封筒に入れる方法は何通りあるか。
〔武庫川女子大]
基本
5人を1,2,3,4,5 とし, それぞれの人のあて名を書いた封筒を① ② ③ ④.5
招待状, 2, 3, 4, 5 とすると, 問題の条件は k (k=1,2,3,4,5)
よって, 1, 2, 34,5の5人を1列に並べたとき, k番目がんでない順列の数を求め
ればよい。
5人を12345 とすると, 求める場合の数は, 5人を
解答 1列に並べた順列のうち, k番目がk (k=1,2,3,4,5)
でないものの個数に等しい。
1番目が2のとき,条件を満たす順列は、 次の11通り。
4-5-3
2-1
5-3-4
1-5-3
2-44
1-3
~5<
3-1
1番目は1でない。
参考 樹形図を作る際は、
① ② ③ ④ ⑤
1-5-4
2-3-4-5-1
5-1-4
例えば
1-3-4
2-54
[1-3
・4・
3-1
4-5-3
2-1-
5-3-4
のように書き, 内の数字
1番目が3,4,5のときも条件を満たす順列は,同様に 11 の下にその数字を並べない
ようにするとよい。
通りずつある。
よって, 求める方法の数は
11×4=44 (通り)
完全順列(次ページの参考事項も参照)
1~non個の数字を1列に並べた順列のうち, どのk番目の数字もんでないものを
検討
全順列という。 完全順列の総数を調べるには, 上の解答のように樹形図をかいてもよい。
しかし, nの値が大きくなると, 樹形図をかくのは大変。 そこで, n≧4のときの完全順列
については、 1つ前や2つ前の結果を利用して調べてみよう。
n個の数字の順列 1, 2, .......
n=1のとき W(1)= 0
の完全順列の総数を W (n) で表す。
n=2のとき, ②①の1通りしかないから W(2)=1
n=3のとき, 31, 3 1 2 の2通りあるから W(3)=2
n=4のとき,まず, 1, 2, 3の3個の数字の順列の最後に 4 を並べる。
[1] 3個の数字の順列が完全順列であるとき 4と1~3番目の数字を入れ替える。
例えば, 2314 において, 4 と 1 を入れ替えると
よって
[2] k=1,2,3とする。 3個の数字の順列で1つだけん番目のものが
(残る2個の数字は完全順列になっている), 瓦と4を入れ替える。
例えば, 21 3 4 において, 4と3を入れ替えると
[1] の場合は3通りの入れ替え方があり[2]の場合も3通りの入れ替え方がある。
W(4)=3×W(3)+3×W(2)=3×2+3×1=9
2 3 4 1
完全順列
であるとき
2143
完全順列
(以後,次ページに続く)
練習 右の図のようなマス目を考える。 どの行 (横の並び)にも,どの
15 列 (縦の並び) にも同じ数が現れないように1から4まで自然数
を入れる入れ方の場合の数 K を求めよ。
2
1
34
1
4
23
[ 類 埼玉大 ]