確率（というか場合の数）の問題

2011年7月28日雑記コメント (4)

ゆうﾊﾟﾊﾟＨさんのところであげられていたので考えてみた。

フィーリングカップルでペアができない確率を求める問題でしたが、一般化してk組ペアができる確率を求めてみました。
とりあえず場合の数を求める漸化式はできたので、あとはこれを解けば…（できるか？）

男の数をx,女の数をyとしたとき(ただしx > yとする)、ペアがk組できる場合の数Count(x, y, k)は以下。

Count(x, y, k) = Comb(x,k) * Comb(y, k) * Fact(k) * c(x, y, k)

Combは組み合わせ、Factは階乗でcは以下の通り。

c(x, y, k)
= x ^ (y - k) * y ^ (x - k) - Sum(t=1... y-k ) { Comb(x - k, t) * Comb(y - k, t) * Fact(t) * c(x, y, k + t) }

--------------------------------------------------
解説
まず前提条件のx > yは簡単にするため。y > xの時はCount(y, x, k)を求めればよし。

Count()でやってることは簡単で、まず男子からペアになる人をk人選び(Comb(x,k))、女子からペアになる人をk人選ぶ(Comb(y,k))。ペアの作り方はFact(k)通り(男子を固定して、女子を並べ替える)。そして、ペアとならない人が相手を選ぶ場合の数を求めて、全部掛けあわせれば求める数。

c()で求めているのは、ペアが固定されたとき、ペアとならない人が相手を選ぶ場合の数。

考え方は、(ペアとなっていない人が相手を選ぶ場合の数) - (ペアになってない所から1組ペアができる場合の数) - (ペア…2組…)-…-(ペア…(y-k)組…)。

ペアとなっていない人が相手を選ぶ場合の数
=男(x-k)人が女y人から相手を選び、女(y - k)人が男x人から相手を選ぶ場合の数（すでにペアとなっている人を選んでも問題なし）
=y ^ (x - k) * x ^ (y - k)

男x-k人、女y-k人からt組のペアを選ぶ場合の数はCount()と同じ考え方で
Comb(x - k, t) * Comb(y - k, t) * Fact(t)だから、
ペアになってない所からt組ペアができる場合の数
=(男x-k人、女y-k人からt組のペアを選ぶ場合の数) * (k+t組のペアが固定されたとき、ペアとならない人が相手を選ぶ場合の数)
=Comb(x - k, t) * Comb(y - k, t) * Fact(t) * c(x, y, k + t)

-----------------------------------
正直自分は情報屋ですので、ここまでできればあとはプログラムで求めちゃえみたいになってしまいますが、数学屋さんはもうちょっときれいになるまで解くんでしょうね。

とりあえずプログラムを書いて求めてみました。

(x,y,k) 場合の数確率

(1,1,0) 0 0.000
(1,1,1) 1 1.000
(2,1,0) 0 0.000
(2,1,1) 2 1.000
(3,1,0) 0 0.000
(3,1,1) 3 1.000
(4,1,0) 0 0.000
(4,1,1) 4 1.000
(5,1,0) 0 0.000
(5,1,1) 5 1.000
(6,1,0) 0 0.000
(6,1,1) 6 1.000
(7,1,0) 0 0.000
(7,1,1) 7 1.000
(2,2,0) 2 0.125
(2,2,1) 12 0.750
(2,2,2) 2 0.125
(3,2,0) 12 0.167
(3,2,1) 48 0.667
(3,2,2) 12 0.167
(4,2,0) 48 0.188
(4,2,1) 160 0.625
(4,2,2) 48 0.188
(5,2,0) 160 0.200
(5,2,1) 480 0.600
(5,2,2) 160 0.200
(6,2,0) 480 0.208
(6,2,1) 1344 0.583
(6,2,2) 480 0.208
(7,2,0) 1344 0.214
(7,2,1) 3584 0.571
(7,2,2) 1344 0.214
(3,3,0) 156 0.214
(3,3,1) 423 0.580
(3,3,2) 144 0.198
(3,3,3) 6 0.008
(4,3,0) 1224 0.236
(4,3,1) 2808 0.542
(4,3,2) 1080 0.208
(4,3,3) 72 0.014
(5,3,0) 7560 0.249
(5,3,1) 15795 0.520
(5,3,2) 6480 0.213
(5,3,3) 540 0.018
(6,3,0) 40500 0.257
(6,3,1) 79704 0.506
(6,3,2) 34020 0.216
(6,3,3) 3240 0.021
(7,3,0) 197316 0.263
(7,3,1) 372519 0.497
(7,3,2) 163296 0.218
(7,3,3) 17010 0.023
(4,4,0) 16920 0.258
(4,4,1) 33184 0.506
(4,4,2) 13968 0.213
(4,4,3) 1440 0.022
(4,4,4) 24 0.000
(5,4,0) 173280 0.271
(5,4,1) 311680 0.487
(5,4,2) 137280 0.214
(5,4,3) 17280 0.027
(5,4,4) 480 0.001
(6,4,0) 1480320 0.279
(6,4,1) 2520576 0.475
(6,4,2) 1140480 0.215
(6,4,3) 161280 0.030
(6,4,4) 5760 0.001
(7,4,0) 11192832 0.285
(7,4,1) 18350080 0.466
(7,4,2) 8451072 0.215
(7,4,3) 1290240 0.033
(7,4,4) 53760 0.001
(5,5,0) 2764880 0.283
(5,5,1) 4581225 0.469
(5,5,2) 2088800 0.214
(5,5,3) 316200 0.032
(5,5,4) 14400 0.001
(5,5,5) 120 0.000
(6,5,0) 35366400 0.291
(6,5,1) 55638000 0.458
(6,5,2) 25884000 0.213
(6,5,3) 4356000 0.036
(6,5,4) 252000 0.002
(6,5,5) 3600 0.000
(7,5,0) 389487000 0.297
(7,5,1) 591224375 0.450
(7,5,2) 278670000 0.212
(7,5,3) 50242500 0.038
(7,5,4) 3360000 0.003
(7,5,5) 63000 0.000
(6,6,0) 650696400 0.299
(6,6,1) 973830816 0.447
(6,6,2) 460350000 0.211
(6,6,3) 85521600 0.039
(6,6,4) 6231600 0.003
(6,6,5) 151200 0.000
(6,6,6) 720 0.000
(7,6,0) 10024771680 0.304
(7,6,1) 14496257664 0.440
(7,6,2) 6923659680 0.210
(7,6,3) 1371081600 0.042
(7,6,4) 114760800 0.003
(7,6,5) 3628800 0.000
(7,6,6) 30240 0.000
(7,7,0) 210105425628 0.310
(7,7,1) 293840040823 0.433
(7,7,2) 141537806928 0.209
(7,7,3) 29771976150 0.044
(7,7,4) 2849330400 0.004
(7,7,5) 116794440 0.000
(7,7,6) 1693440 0.000
(7,7,7) 5040 0.000