第３８０問の解答
問題［場合の数］
 |
 |
 |
|
|
４組（男女８人）のカップルが円卓で昼食会を開くことになりました。 円卓の周りには８つのイスがあって、８人はどれかのイスに座ることになります。 このとき、８人のイスへの座り方は何通りあるでしょうか。 |
|
 |
|
 |
解答例１
Taroさん、呑さん、ヌオの母さん、ＡЯＯＴさん、みかんさん、拓パパさん、CRYING DOLPHINさん、はなうさん、DrKさん、小西孝一さん、小学名探偵さん、M.Hossieさん、ミミズクはくず耳さん、大岡 敏幸さん、ﾎﾟケモンハルカさん、 他多数
女性または男性が１人でいると、両隣が異性なのでどちらかは自分の恋人ではありえないので不適。よって、女性、男性とも２人以上で固まっていることになります。 （以降、固まりのことを連鎖と呼ぶことにします）
また、女性連鎖、男性連鎖は、互い違いに並ぶことになるので個数は等しい。・・・（１）
カップルが４組の場合、女性連鎖、男性連鎖は、
４個（ケース１）か、２個＋２個（ケース２）
の２通りになります。各ケースの数え方はいろいろありますが、次の方法が分かりやすいでしょう。
（ケース１）
・まず、女性４人を並べます。 ・・・ ４!＝４×３×２×１＝２４通り
・男性４人のうち、両端の２人は自分の恋人の隣に座ります。
残り２人の並び方 ・・・ ２!＝２×１＝２通り
→２４×２＝４８通り（ケース２）
・４組のカップルの並び方は４組の円順列 ・・・ ３!＝３×２×１＝６通り
・各カップル内の女性・男性の並び方は全て同じ ・・・ ２!＝２×１＝２通り
→６×２＝１２通りよって、
座り方合計＝４８＋１２＝６０通り
と求まります。答： ６０通り
以上
解答例２
小学名探偵さん、中村明海さん、ほげさん、他
この問題の一般化に３人の方が取り組まれました。その結果をご紹介いたします。
カップルがn組（n≧２）のときの座り方をＰ（n）とします。
解答例１の（１）から、女性連鎖、男性連鎖がk個（１≦k≦n×１/２）のときの座り方を、Q（n、k）と すると、
Ｐ（n）＝ΣQ（n、k）
と表すことができます。まず、Q（n、k）を求めます。
（１）k個ずつある女性連鎖、および男性連鎖で、それぞれの両端にいる人たちは、恋人と隣り合っています。逆に恋人と隣り合っているカップルは、互いに女性連鎖または男性連鎖の端にいます。これら２k組のカップルをn組のカップルから選ぶ並び方は、
・・・ nC2k通り（２）選ん２k組のカップルをの並び方は、 ちょうど解答例１のケース２と同じになるので
・・・ （２k-1）!×２!通り（３）残りの女性（n−２k）人は、連鎖の内側にいることになります。
まず１人目を並べることのできる位置は、n個の連鎖（２人ずつ並んでいる）のうち、
いずれかの間なので ・・・ k通り２人目は、２人ずつ並ぶ女性の組は１つ増えて（k＋１）組となるので、・・・ （k＋１）通り
以下同様にして、最後の女性は（n-２k）人目なので、
・・・ ｛k＋（n−２k）−１｝＝（n-k-1）通り従って、
合計＝k×（k＋１）×（k＋１）×・・・×（n-k-1）＝（n-k-1）!/（k-1）!通り（４）残りの男性（n−２k）人の並べ方も（３）と全く同じなので、
・・・ （n-k-1）!/（k-1）!通りよって以上から、
Q（n、k）＝nC2k×（２k-1）!×２!×｛（n-k-1）!/（k-1）!｝2 通り
となり、
P（n）＝Σ(k=1..[n/2]) nC2k×（２k-1）!×２!×｛（n-k-1）!/（k-1）!｝2 通り
と求まります。なお、n=1のときP（１）＝１なので、これを加えてn＝１〜１０までを計算すると、
下表のようになります。
（追補）本問の数列がオンライン整数列大辞典に登録されました。
直接のリンク先はこちらです。
（参考）n→∞のとき、P(n)/{(n-1)!}2→1.59063685463656
P(n)/{(n-1)!}2＝ΣQ(n,k)/{(n-1)!}2の第k項は、
Q(n,k)/{(n-1)!}2
＝n!/{(n-2k)!×(2k)!}×(2k)!/k×{(n-k-1)!}2/{(k-1)!}2
＝1/{k!×(k-1)!}×[n×(n-1)×・・・×(n-2k+1)/{(n-1)×(n-2)×・・・×(n-k)}2]
となり、
後半部分は、分母、分子とも2k個の積なので、それぞれn2kで割って、
1×(1-1/n)×・・・×{1-(2k-1)/n}/{(1-1/n)×(1-2/n)×・・・×(1-k/n)}2
となるので、n→∞のとき、１に収束。従って、
Q(n,k)/{(n-1)!}2→1/{k!×(k-1)!}よって、
P(n)/{(n-1)!}2＝Σ(k=1..∞)1/{k!×(k-1)!}実際に計算すると、
k=1〜１１の和＝1.59063685463733
・・・
k=1〜１５の和＝1.59063685463733
ただし、Q(n,k)/{(n-1)!}2自身の収束は、かなり遅く、
n=10のとき、1.6482087743
n=1000のとき、1.5913250049
n=100000のとき、1.5906437440
n=10000000のとき、1.5906368615
