Project Euler 796

题目

A Grand Shuffle

A standard \(52\) card deck comprises thirteen ranks in four suits. However, modern decks have two additional Jokers, which neither have a suit nor a rank, for a total of \(54\) cards. If we shuffle such a deck and draw cards without replacement, then we would need, on average, approximately \(29.05361725\) cards so that we have at least one card for each rank.

Now, assume you have \(10\) such decks, each with a different back design. We shuffle all \(10 \times 54\) cards together and draw cards without replacement. What is the expected number of cards needed so every suit, rank and deck design have at least one card?

Give your answer rounded to eight places after the decimal point.

解决方案

把抽牌看成对 \(N\) 张牌做一个等概率随机排列，然后从前往后揭牌。令\(p(k)\)表示前\(k\)张牌已经集齐全部设计、花色、点数的概率。

则停止时刻 \(T\le k\) 等价于前 \(k\) 张已经完成，因此\(\Pr(T\le k)=p(k), \Pr(T>k)=1-p(k).\)

由于 \(T\in\{1,2,\dots,N\}\)，可用经典尾和公式得到：\(\displaystyle{\mathbb E[T]=\sum_{k=0}^{N-1}\Pr(T>k)=\sum_{k=0}^{N-1}(1-p(k)).}\)并利用 \(p(N)=1\) 得到更对称的形式：

\[ \mathbb E[T]=N+1-\sum_{k=0}^{N}p(k). \]

问题转化为：计算所有 \(p(k)\) 的总和。

接下来我们用容斥计算 \(p(k)\)。设我们允许的集合是：

• 允许某个选定的 \(d\) 种牌背设计；
• 允许某个选定的 \(s\) 种花色；
• 允许某个选定的 \(r\) 种点数。

那么在每一种允许的牌背设计里：

• 标准牌能用的组合是 \(r\times s\) 张；
• Joker 有 \(J\) 张，并且不受花色/点数限制。

因此每个允许设计贡献的可用牌数为 \(rs+J\)，总可用牌数\(M(d,s,r)=d(rs+J).\)

“前 \(k\) 张都来自这 \(M\) 张可用牌”这个事件等价于从 \(N\) 张牌中抽取一个长度为 \(k\) 的不重复序列，其所有元素都在可用集合内。

令长度为 \(k\) 的不重复序列数为排列数 \(P(x,k)=x(x-1)\cdots(x-k+1)=\dfrac{x!}{(x-k)!}.\)因此前\(k\)张牌都来自可用集合的概率为\(\dfrac{P(M(d,s,r),k)}{P(N,k)}.\)

我们真正想要的是“前 \(k\) 张同时覆盖全部 \(D\) 种设计、全部 \(S\) 种花色、全部 \(R\) 种点数”。因此用容斥原理求解：选择“允许集合”的方式有\(\dbinom{D}{d}\dbinom{S}{s}\dbinom{R}{r}\) 种；若允许集合规模小于全体，则对应的是“缺失某些设计/花色/点数”，符号由缺失数量决定。最终得到：

\[ p(k)=\sum_{d=0}^{D}\sum_{s=0}^{S}\sum_{r=0}^{R} (-1)^{D+S+R-d-s-r} \binom{D}{d}\binom{S}{s}\binom{R}{r} \frac{P(M(d,s,r),k)}{P(N,k)}. \]

把它代入期望公式后化简，得到

\[ \mathbb E[T]=N+1-\sum_{d=0}^{D}\sum_{s=0}^{S}\sum_{r=0}^{R} (-1)^{D+S+R-d-s-r} \binom{D}{d}\binom{S}{s}\binom{R}{r} \sum_{k=0}^{N}\frac{P(M(d,s,r),k)}{P(N,k)}. \]

为此，我们需要计算\(\displaystyle{\sum_{k=0}^{N}\frac{P(M,k)}{P(N,k)}.}\)注意到\(\dfrac{P(M,k)}{P(N,k)}=\dfrac{\binom{M}{k}}{\binom{N}{k}}\)，其中\(k\le M\)（\(k>M\)时为\(0\)）。因此\(\displaystyle{\sum_{k=0}^{N}\frac{P(M,k)}{P(N,k)}=\sum_{k=0}^{M}\frac{\binom{M}{k}}{\binom{N}{k}}.}\)

接下来通过给出一个非常直接的组合意义证明，进一步化简这个式子。我们将 \(N\) 张牌分成两类：

• “坏牌”共 \(M\) 张（对应允许集合）；
• “好牌”共 \(N-M\) 张（不在允许集合中）。

随机排列后从前往后翻牌，直到第一次出现“好牌”为止。设该位置为 \(X\)，并令\(Y=X-1\)表示在此之前出现的坏牌数量，则有\(\mathbb E[X]=1+\mathbb E[Y].\)

现在看每一张坏牌：它在第一张好牌之前出现的概率是对称的。把“第一张好牌”与某一张固定坏牌一起考虑，在 \(((N-M)+1)\) 个对象（所有好牌视为一个整体的“最早出现者”再加上这张坏牌）中，这张坏牌成为最早者的概率为\(\displaystyle{\dfrac{1}{(N-M)+1}=\dfrac{1}{N+1-M}.}\)

因此该坏牌对 \(\mathbb E[Y]\) 的贡献为 \(\dfrac{1}{N+1-M}\)，将 \(M\) 张坏牌累加得到\(\mathbb E[Y]=M\cdot\dfrac{1}{N+1-M}=\dfrac{M}{N+1-M}.\)从而得到\(\displaystyle{\sum_{k=0}^{N}\frac{P(M,k)}{P(N,k)}=\frac{N+1}{N+1-M}.}\)

回代到上面的结果，得到

\[ \sum_{k=0}^{N}p(k) =\sum_{d,s,r}(-1)^{D+S+R-d-s-r} \binom{D}{d}\binom{S}{s}\binom{R}{r} \frac{N+1}{N+1-M(d,s,r)}. \]

利用\(\dfrac{N+1}{N+1-M}=1+\dfrac{M}{N+1-M},\)并注意到容斥系数的总和为\(\displaystyle{\sum_{d,s,r}(-1)^{D+S+R-d-s-r}\binom{D}{d}\binom{S}{s}\binom{R}{r}=(1-1)^D(1-1)^S(1-1)^R=0,}\) 因此常数项 \(1\) 全部抵消，得到极其紧凑的形式：

\[ \mathbb E[T] = N+1- \sum_{r=0}^{R}\sum_{s=0}^{S}\sum_{d=0}^{D} (-1)^{R+S+D-r-s-d}\binom{R}{r}\binom{S}{s}\binom{D}{d} \frac{d(rs+J)}{N+1-d(rs+J)}. \]

代码

from tools import comb

D = 10
S = 4
R = 13
J = 2

def expected_cards(D,S,R,J):
    N = D * (S * R + J)
    total = 0
    for r in range(R + 1):
        cr = comb(R, r)
        for s in range(S + 1):
            cs = comb(S, s)
            rs = r * s
            for d in range(D + 1):
                cd = comb(D, d)
                M = d * (rs + J)
                if M == 0:
                    frac = 0
                else:
                    frac = M / ((N + 1) - M)
                sign = -1 if ((R + S + D - r - s - d) & 1) else 1
                total += sign * (cr * cs * cd) * frac

    return N + 1 - total


if __name__ == "__main__":
    ans = expected_cards(D,S,R,J)
    print(f"{ans:.8f}")