匿名ゆき 2014-11-23 17:15:10 |
通報 |
完全順列
攪乱順列と教えてもらえていたら頭の中で反芻しているだろうに。
これは問題文が面白く作れますよね。
カップル5組があって、計10人で男女ペアを作り直す。
そのうちどの組も元のカップルが成立しないような場合の数は?
爆破願望の強い方におすすめの一問ですよ。
完全順列(全ての組が正しく並ばない)問題では
例を添えておくと
f(1)=0 ←一組のカップルしかいない場合、絶対にカップルが成立する。
f(2)=1 ←二組のカップルの場合は、片方の性別の人を入れ換える場合のみ。
n≧3のとき、f(n)=(n-1){f(n-1)+f(n-2)}
これが成り立つことが知られています。
モンモール数なんて呼ばれたりするらしいですよ。
数列、漸化式を学んでいなくてもこれなら使い方が分かりますね。
f(5)まで繰り返し用いると、答えは44通りになります。
組の総数5P5=5!=120で割合を計ると、およそ35%カップルは完全にバラバラになります。
おまけ
全ての組がバラバラ=44
1組だけ成立=5C1・f(4)=45
2組成立=5C2・f(3)=20
3組成立=5C3・f(2)=10
4組成立=全組成立=1
全ての場合を足すと120になりますね。
モンモールを覚えていなくても樹形図を用いれば解けるので、最初は3組バラバラなど少ない組で試すといいでしょう。
トピック検索 |