第252問の解答
1.問題 [場合の数]
あるパーティに男性が5名、女性が5名参加しました。
この10人はそれぞれ、参加者の異性の1人を好きになっており、しかもどの参加者も1人の異性に好かれているそうですが、残念ながら両想いは一組もないそうです。
では、このような関係は何通り考えられるでしょうか。
2.解答例1(TORAさん、高橋道広さん、ちえんかん#2期さん、Michaelさん、ミミズクはくず耳さん、M.Hossieさん、小西孝一さん、他多数)
男性をM1、M2、・・、M5、女性をF1、F2、・・、F5とします。
MmがFnを好きだことを、Mm→Fnと表すことにします。M1→F3→M2→F4→・・・、というように好きな異性を次々と並べていくと、M1を好きな女性も1人いるので、最後はM1に戻ってきます。
また、このとき男性、女性とも好きな異性が1人ずついることから、それぞれ同数いることになります。
そこで、男、女がn人ずついる場合をn組連鎖と呼ぶことにします。
10人の男女では、5組連鎖と3組連鎖+2組連鎖の2ケースが考えられます。(1組連鎖がありえないので、1組連鎖+4組連鎖などはあり得ません)
(1)5組連鎖の場合
M1が選べる女性は、F1〜F5の5通り、(例1:F3)
F3が選べる男性は、M1以外の4通り、(例1:M2)
M2が選べる女性は、F3以外の4通り、(例1:F4)
・・・
となり、合計
(5×4)×(4×3)×(3×2)×(2×1)×(1×1)=2880通り
あります。(2)3組連鎖+2組連鎖の場合
- 3組連鎖のとき
5組連鎖と同様にして、(3×2)×(2×1)×(1×1)=12通り
- 2組連鎖のとき
同様にして、(2×1)×(1×1)=2通り
となります。
このとき、3組連鎖に入る男女の組み合わせは、それぞれ5C3=10通りあり、残りの2組連鎖の組み合わせは自動的に決まります。
従って、3組連鎖+2組連鎖の場合は、
合計10×10×12×2=2400通り
となります。
以上から、求める場合の数は、総計2880+2400=5280通りとなります。
答:5280通り
以上
3.解答例2(医学部性さん、数楽者さん、noetherさん、トトロ@Nさん、ヒデー王子さん、中村明海さん、長野美光さん、BossFさん、他)
まず男性がそれぞれ好きな女性を選ぶ選び方を考えます。
M1が選べる女性は、F1〜F5の5通り、(例4:F3)
M2が選べる女性は、F3以外の4通り、(例1:F4)
・・・
となり、合計
5×4×3×2×1=120通り
あります。次に、女性が好きな男性を選ぶ選び方は、それぞれ自分を好きな男性以外を選ぶことになるので、いわゆる5次の完全順列(攪乱順列ともいう)と考えられるので、44通りとなります。
従って、合計120×44=5280通りとなります。
(参考)完全順列(攪乱順列)について(詳しくは類題:第212回問題を参照)
1、2、・・、n を一列に並べる順列のうち、 任意のk(1≦k≦n)に対して、 k番目がkでないような順列のことをn次の完全順列といいます。
- n次の完全順列の個数は、納k=0..n](-1)k・n!/k! で表すことができます。
5次では、5!-5!/1!+5!/2!-5!/3!+5!/4!-5!/5!=120-120+60-20+5-1=44通り
となります。
- 完全順列では,漸化式から求めることもできます。
n次の完全順列の個数をfnとすると、
f1=0、f2=1、およびfn= (n-1)(fn-1+fn-2)が成り立つので、
f3=2(1+0)=2、f4=3(2+1)=9、f5=4(9+2)=44
と、順次求めることができます。
- あるいは、解答例1のn組連鎖の替わりにn次円順列を考えると、
5次の円順列=5!/5=24通り
3次の円順列+2次の円順列=3!/3×2!/2×5C3=2×1×10=20通り
合計24+20=44通りと求めることもできます。