18/10/28 20:30:37.13 x624ZJMX.net
>>161の若干の一般化とその導出を備忘録的に書いておきます。
>>60
まず、部屋を探る順番が一般の場合を考える。
部屋がNあり、その集合をＲとする。Ａ君、Ｂ君が探る順番を表わす全単射写像をそれぞれf,gとする：
f,g: Ｒ→{0,1,…,N-1} （順番は0から始まるとする。）
部屋自体の位置はなんら答えに影響しない。
σ=g・f^{-1} と置くと、σは{0,1,…,N-1}の置換。（・は写像の合成）
Ａ君がi番目に探る部屋はＢ君がσ(i)番目に探る部屋ということ。
以下、「Ａ君がi番目に探る部屋」のことを「部屋i」ということにする。
求めたいのは、「Ａ君がＢ君よりも早く宝を見つける宝の配置の数」であるが、宝の数をcとすると、それは
Σ[σ(i)>i] binomial(#{j| j>i, σ(j)>i}, c-1) （0≦i,j≦N-1、binomialは二項係数）
である。
なぜか？
「Ａ君が初めて宝を見つける部屋（部屋iとする）」で場合分けしよう。
（つまり部屋0～i-1には宝がなく、部屋iに宝がある場合）
部屋iはＢ君がσ(i)番目に探る部屋だからσ(i)>iでないと
少なくともＢ君はＡ君よりも前か同時に部屋iで宝を見つける
（Ｂ君はその前に別の部屋で宝を見つけることもある）ことになりＡ君は勝てない。
したがって、σ(i)>iが必要。
残りのc-1個の宝は部屋i+1～N-1にあるが、宝がある部屋を部屋jとすると、
やはりσ(j)>iでないといけない。逆に全部の宝でそうであればＡ君が勝つ。
よって