重要 例題15 完全順列 (k番目の数がんでない順列)
5人に招待状を送るため、あて名を書いた招待状
0000
を入れるあてる
あるか。
た封筒を作成した。招待状を全部間違った封筒に入れる方法は何通りある
何通りあ
〔武庫川女子大〕
指針 5人を 1, 2, 3, 4, 5 とし それぞれの人のあて名を書いた封筒を1, 2, 3, ④ F
招待状を1, 2, 3, 4, 5 とすると, 問題の条件は k ≠ (k=1,2,3,4,
よって, 1,2,3,4,5の5人を1列に並べたとき, k番目がんでない順列の数を
ればよい。
5人を1,2,3,4,5 とすると, 求める場合の数は,5人を
解答 1列に並べた順列のうち, 番目が (k=1,2,3,4,5)
でないものの個数に等しい。
m ta
1番目が2のとき, 条件を満たす順列は,次の11通り。
1番目は1でない。
pac1-5-4
4-5-3
2-1<
2-3 4-5-1
参考 樹形図を作る
5-3-4
5-1-4
例えば
1-5-3
A
1-3-4
2-44
1-3
2-54
~5<
1-3
2-1<
4
5-3-
3-1
3-1
1番目が 3,4,5のときも条件を満たす順列は,同様に 11
のように書き, 内
通りずつある。
よって, 求める方法の数は
11×4=44 (通り)
完全順列 (次ページの参考事項も参照)
の下にその数字を並
ようにするとよい。
do
1~nのn個の数字を1列に並べた順列のうち、どの番目の数字もんでないもの
寸
全順列という。 完全順列の総数を調べるには,上の解答のように樹形図をかいても
しかし, nの値が大きくなると, 樹形図をかくのは大変。 そこで, n≧4のときの完全
については,1つ前や2つ前の結果を利用して調べてみよう。
n個の数字の順列 1, 2,
n=1のとき W (1) = 0
の完全順列の総数を W (n) で表す。
od
n=2のとき, ②①の1通りしかないから W (2)=1
n=3のとき, 31, 3 1 2 の2通りあるから
n=4のとき,まず, 1, 2, 3の3個の数字の順列の
W(3)=2