今回は攪乱(かくらん)順列とよばれる並べ方を考える問題。漢字が難しいけど、内容も難しいです。


問題

12345を並び替えたとき、どの数字もはじめの位置にならないような並べ方(攪乱順列)は何通りありますか。

例)53412 → ○  54312 → ×


いきなり求めようとしても大変なので、、こういうときはやはり漸化式の出番です。

12345・・・nのn個のときの並べ方をA通りとして、漸化式(AとAn+1とAn+2の間に成り立つ関係)を作ってみます。

ここがポイントですが、An+2は次の(ア)(イ)の2パターンに分けることができます。


(ア)An+1で、1〜n+1までのどの数字と数字n+2を入れ替えたとしても攪乱順列になるので、このパターンは(n+1)×An+1通り

例)4312 → 53124、45123、43521、43152

で、1〜4までのどの数字と数字5を入れ替えたとしても攪乱順列になるので、このパターンは4×A通り


(イ)n+1個の数字で、1個の数字●だけが●番目にあるものは(n+1)×A通りで、
その数字●と数字n+2を入れ替えたら攪乱順列になるので、このパターンは(n+1)×A通り


例)3241 → 35412

4個の数字で、1個の数字●だけが●番目にあるものは4×A通りで、
その数字●と数字5を入れ替えたら攪乱順列になるので、このパターンは4×A通り


(ア)(イ)より、An+2=(n+1)×An+1+(n+1)×A

は並び替えることができないので0通り、Aは21だけなので1通りで、以上まとめると、、

漸化式

=0、A=1、n+2=(n+1)×(An+1+A


あとは繰り返しの計算するだけ。

=0、A=1より、A=2×(1+0)=2、A=3×(2+1)=9、A=4×(9+2)=44





ではもう1問。プレゼント交換の有名な問題。

類題

6人でプレゼント交換するとき、自分のプレゼントをもらわない組み合わせは何通りか。


6人を1、2、3、4、5、6、プレゼントを@、A、B、C、D、Eとして、だれも自分のプレゼントをもらわないということは、
123456を並び替えたとき、どの数字もはじめの位置にならないような並べ方と同じこと。

だから、A=0、A=1より、A=2×(1+0)=2、A=3×(2+1)=9、A=4×(9+2)=44、A=5×(44+9)=265



[←戻る]