辞書式配列の順列に関する問題について見ていきます。ある程度は地道な計算が必要になります。
(問題)
相異なる5つの文字\(A,B,C,D,E\) を用いてできるすべての順列を、辞書式配列法によって順に並べるとき
(1)\(BDCEA\)は何番目にあるか。
(2)第65番目にある順列は何か。
(解答)
(1)
\(BDCEA\)より前にあるものが何個あるか数えます。
①\(A□□□□\) のもの全部
②\(BA□□□\) \(BC□□□\) のもの全部
③\(BDA□□\) のもの全部
④\(BDC□□\) のものは\(BDCAE\)のみ
①\(A□□□□\) のもの全部
②\(BA□□□\) \(BC□□□\) のもの全部
③\(BDA□□\) のもの全部
④\(BDC□□\) のものは\(BDCAE\)のみ
\(BDCEA\)より前にある順列を考える。
①\(A□□□□\) のものは、\(4!\)(個)
②\(BA□□□\) \(BC□□□\) のものは、それぞれ\(3!\)(個)
③\(BDA□□\) のものは、\(2!\)(個)
④\(BDC□□\) のものは\(BDCAE\)の\(1\)(個)
①から④の個数はあわせて、\(4!+2×3!+2!+1=39\)(個)であり、\(BDCEA\)は④の\(BDCAE\)の次の順列だから、\(40\)(番目)
(2)
地道に数えます。
\(A□□□□\)のものは、\(4!=24\)(個)
\(B□□□□\)のものは、\(4!=24\)(個)
\(C□□□□\)のものは、\(4!=24\)(個) なので
頭文字が\(B\)の最後のものは\(48\)番目、頭文字が\(C\)の最後のものは\(72\)番目となるので、\(65\)番目の順列の頭文字は\(C\)となります。次は2文字目を検討していきます。(以下3文字目・・・を検討)
\(A□□□□\)のものは、\(4!=24\)(個)
\(B□□□□\)のものは、\(4!=24\)(個)
\(C□□□□\)のものは、\(4!=24\)(個) なので
頭文字が\(B\)の最後のものは\(48\)番目、頭文字が\(C\)の最後のものは\(72\)番目となるので、\(65\)番目の順列の頭文字は\(C\)となります。次は2文字目を検討していきます。(以下3文字目・・・を検討)
\(A□□□□\), \(B□□□□\) のものは、\(4!×2=48\)(個)
\(CA□□□\), \(CB□□□\) のものは、\(3!×2=12\) (個)
ここまで計\(48+12=60\)個で
\(CDA□□\), \(CDB□□\) のものは、\(2!×2=4\)(個)
ここまで計 \(64\)(個)で、\(65\)番目の順列は3文字目が\(E\)である最初の順列となるので、\(CDEAB\)
\(CA□□□\), \(CB□□□\) のものは、\(3!×2=12\) (個)
ここまで計\(48+12=60\)個で
\(CDA□□\), \(CDB□□\) のものは、\(2!×2=4\)(個)
ここまで計 \(64\)(個)で、\(65\)番目の順列は3文字目が\(E\)である最初の順列となるので、\(CDEAB\)
\(65\)番目の\(65\)を\(4!\)で割って、その余りをさらに\(3!\)で割って、その余りをさらに\(2!\)で割ると
\(65=4!×2+3!×2+2!×2+1\) と表されることがわかります。こうすると見通しが立ちやすくなると思います。
\(65=4!×2+3!×2+2!×2+1\) と表されることがわかります。こうすると見通しが立ちやすくなると思います。
以上になります。お疲れさまでした。
ここまで見て頂きありがとうございました。