0369 百得之
* * * *
拉格朗日计划
* * * *
百得之

百得之(Badugi,也译作巴杜吉)是一种扑克游戏。从一副52张(移除鬼牌)的扑克牌中取出4张,若其中任意两张牌的点数和花色都不同,就称作百得之。

记$f(n)$为选择n张牌,使得其中有4张牌构成百得之的选数总数。例如,从52张牌中取出5张,共有2598960种取法,其中有514800种能包含4张构成百得之的牌,因此$f(5)=514800$。

求$\sum_{n=4}^{13}f(n)$。

本题难度:



解答

本题同第345题的思路类似,考虑一个$13\times 4$的二元矩阵,行标为A到K的点数,列标为四种花色,值为1表示该点数和花色被选中,否则表示未被选。

从上到下枚举每一行的选法,若在第k行首次出现了百得之牌,则后面的牌可以任选,否则继续枚举,如此可以保证不重复。

最后汇总即得最终结果是$8624005584484$。

注:因用到math.prod和math.comb函数,以下代码为Python 3。

import math

suits=[(0,0,0,1),(0,0,1,0),(0,0,1,1),(0,1,0,0),(0,1,0,1),(0,1,1,0),(0,1,1,1),(1,0,0,0),(1,0,0,1),(1,0,1,0),(1,0,1,1),(1,1,0,0),(1,1,0,1),(1,1,1,0),(1,1,1,1)]

getDivision=lambda n,k:[((suits[i],h),)+d for i in range(k,15) for h in range(1,n//sum(suits[i])+1) for d in getDivision(n-h*sum(suits[i]),i+1)] if n>0 else [(),]

isBadugi=lambda d,k:k==4 or any(isBadugi({i:j-(i==c) for i,j in d.items()},k+1) for c,t in d.items() if c[k]==1 and t!=0)

countHands=lambda d,n:math.factorial(n)//(math.prod(math.factorial(m) for k,m in d)*math.factorial(n-sum(m for k,m in d)))

print(sum(countHands(d,13) for n in range(4,14) for d in getDivision(n,0) if isBadugi(dict(d),0)))