>>195
続き

部屋が縦m、横nの場合を考えているが、もう少し計算を進める。
#{j| j>i, σ(j)>i} をこの場合に具体的に表そう。

i,j (0≦i,j≦mn-1)をそれぞれ nk+l, nk'+l' (0≦k,k'≦m-1, 0≦l,l'≦n-1) とする。
σ(i)>i ⇔ lm+k>nk+l ⇔ (m-1)l>(n-1)k、
j>i ⇔ nk+l>nk'+l' ⇔ 「k=k' かつ l<l'」または「k<k'」、
σ(j)>i ⇔ l'm+k'>nk+l ⇔ l' + k'/m > (nk+l)/m　[ここで nk+lをmで割った商をq、余りをrとすると]
　　 ⇔ l' + k'/m > q + r/m ⇔ 「q≦l'≦n-1 ただし l'=q, k'≦r を除く」
を使って
#{j| j>i, σ(j)>i} = #{(k',l')|『「k=k' かつ l<l'」または「k<k'」』かつ l'm+k'>nk+l}
に出てくる『「k=k' かつ l<l'」または「k<k'」』かつ l'm+k'>nk+lを満たす組(k',l')の数を求める。
k=k' かつ l<l'のとき σ(i)>iからlm+k>nk+lだからl'm+k'>nk+lは常に成り立つので、l<l'≦n-1でn-1-l個。
k<k' のとき l'm+k'>nk+l ⇔ 「q≦l'≦n-1, k<k'≦m-1 ただし l'=q, k<k'≦r を除く」だから
(n-q)(m-1-k) - (r-k)δ(r>k)個、ただしδ(P)はPが真なら1、偽なら0である関数。
よって、#{j| j>i, σ(j)>i} = (n-1-l) + (n-q)(m-1-k) - (r-k)δ(r>k)。
したがって、求める数は
Σ[0≦k≦m-1, 0≦l≦n-1, (m-1)l>(n-1)k] binomial((n-1-l) + (n-q)(m-1-k) - (r-k)δ(r>k), c-1)。

これを使ったPythonコード：
#nloc(m,n,k,l)は縦m、横nの部屋で横優先が部屋(k,l)で初めて宝を発見する場合で
#宝が置かれても縦優先に先を越されない部屋の数。
def nloc(m,n,k,l):
q,r = divmod(n*k+l,m)
return (n-1-l) + (n-q)*(m-1-k) - (r-k if r > k else 0)

#部屋が縦m、横n、宝がc個で横優先が勝つ宝の配置の数
def nwinrect1(m,n,c):
return sum(binomial(nloc(m,n,k,l),c-1) for k in range(m) for l in range(n) if (m-1)*l>(n-1)*k)

続く