>>398
p(1),…,p(n),q(1),…,q(n)を非特異(=分布関数が連続)な独立同分布な確率変数とし、それぞれを昇順に並べたものをa(1),…,a(n),b(1),…,b(n)とする。
a(i) < b(i)となる i の個数をNとする。
このときNの分布は一様分布である。
(∵)
a(1)〜b(n)共通の分布関数をFとする。
a(1),…,a(n),b(1),…,b(n)すべてを昇順に並べたものをc(1),…,c(2n)とする。
MをAをn文字、Bをn文字、計2n文字を並べたものの全体とする。
Mに値をとる確率変数μを
μ[i] = A ⇔ c(i) = a(k) (∃k)、μ[i] = B ⇔ c(i) = b(k) (∃k)、
で定める。
m∈Mに対し A[m] = μ^(-1)(m) とおく。
Gを{1,2,…,n}の置換の全体としg,h∈Gに対し
B[gh] = {ω| a[i] = p[g(i)], b[i] = q[h(i)]}
とおく。
長さ4nの狭義単調増大列の全体をVとし、v∈Vに対し
C[v] = {ω｜v[2i-1] < c[i] <v[2i]}
とおく。
このとき任意のμ、μ'、g、h、vに対し
P(A[μ] ∩ B[gh] ∩ C[v]) = P(A[μ'] ∩ B[gh] ∩ C[v]) = Π(F(v[2i]) - F(v[2i-1]))
である。
任意のv',v''に対しC[v']∩C[v'']は空でなければC[v']∩C[v'']=C[v]となるvがとれることとσ加法性により
A[μ] ∩ B[gh] = A[μ'] ∩ B[gh]
である。ことなるg,hの組に対しB[gh]は互いに排反であるから足し合わせて
A[μ] = A[μ']
である。
Mの各元 m に対し
L(m) = #{i | mの中のi番目のAがi番目のBより前}
とおくと
N(ω) = L(μ(ω))
であるから
P(N = k) = #{m∈M | L(m) = k}/C[2n,n]
である。
ここで任意のkに対し#{m∈M | L(m) = k}はカタラン数C[2n,n]/(n+1)に等しいから主張は示された。