如果是純隨機的話其實有個方法可以做
令 P(n,k,m) (n,k≧m) 是 n 對牌翻 k 次翻出 m 對的機率
由於 n 對牌隨機翻兩張翻到一對牌的機率是 n/C(2n,2) = 1/(2n-1)
可以簡單得到下面的遞迴式:
P(n,k,m) = (1/(2n-1))*P(n-1,k-1,m-1) + (1-1/(2n-1))*P(n,k-1,m), n,k,m > 0
初始條件很容易得到:
P(n,0,m) = 1
P(n,k,0) = (1-1/(2n-1))^k
P(n,k,k) = 1/(2n-1)(2n-3)(2n-5)...(2n-2k+1)
有了這些就可以很簡單的寫程式 DP 了
(或者如果覺得計算順序很難決定的話用筆記法也是 OK)
我的程式 (筆記法 on Mathematica) 計算結果是:
P(6,6,0) = 1000000/1771561 ≒ 0.564473930
P(6,6,1) = 33518456608/104608905489 ≒ 0.320416856
P(6,6,2) = 2124501072016/22833271098099 ≒ 0.093044096
P(6,6,3) = 536959299248/28829887750125 ≒ 0.018625092
P(6,6,4) = 122612704/41601569625 ≒ 0.002947310
P(6,6,5) = 14282/36018675 ≒ 0.000396517
P(6,6,6) = 1/10395 ≒ 0.000096200