麻将取牌概率分析

前言

由于要实现麻将听牌查表算法，所以先考虑下在麻将34种136张牌下取14张并且不重复的概率。

分析

不去重的状况下有多少种可能

如果不考虑去重的情况，那么结果可以很简单的变为从136张牌中取14张牌的组合有多少的问题。表示为$\begin{pmatrix}136\\14\\ \end{pmatrix}$
即4,250,305,029,168,215,552约425京(一京为,$10^{16}$一种麻将最多是4张所以这个里面有大量重复的数据。（首先看下这个数量级，一个64位二进制可以表示的最大数是1.844674E+19，可见将这么大的数据建表是不现实的）

求通项式

通过推导通项式并借助动态规划在计算机上计算结果

设$\large i $表示牌种类,$\large j$表示牌张数,$\Large a_{i,j}$表示i种牌j张牌的情况下的组合数量。接下来考虑$\Large a_{i,j}$的性质。比如我们要计算$\Large a_{4,5}$时应该考虑以下几种情况：

新的种类一个都不添加时的情况：$\Large a_{3,5}$
新的种类添加一个时：$\Large a_{3,4}$
新的种类添加两个时：$\Large a_{3,3}$
新的种类添加三个时：$\Large a_{3,2}$
新的种类添加四个时：$\Large a_{3,1}$

对应：

$a_{4,5}=a_{3,5} +a_{3,4} + a_{3,3} + a_{3,2} + a_{3,1}$

可以得到对应的公式：

${\LARGE a_{i,j}}=\left\{ \begin{array}{ccl} \sum\limits_{k=j-4}^j a_{i-1,k}& &i >1 ,j>=0\ and \ j <=4i\\\\[1ex]1&&i=1,j=0,1,2,3,4\\\\[1ex]0&&i<=0\ or\ j < 0\ or\ j >4i \end{array}\tag1\right.$

这个公式需要$i>1$并且当j为负数或$ j>4*i $时$\Large a_{i,j}$为0(即这种取法不存在)。当$i=1$时我们可以得到$ a_{1,0}\space a_{1,1}\space a_{1,2}\space a_{1,3}\space a_{1,4} $都为1。（取零张是允许的视为一种）

编写代码计算

下面使用Python进行简单的代码编写

def A(i, j):
    ans = [[0]*(j + 1) for _ in range(0, i)]
    for n in range(0,min(5, j + 1)):
        ans[0][n] = 1
    for k in range(1, i):
        # 计算每个种类的数据
        for l in range(0, min((j + 1), 4 * (k+1) + 1)):
            # 计算每种张数对应的值
            for m in range(max(0, l - 4), l + 1):
                ans[k][l] += ans[k - 1][m]
    return ans[i - 1][j]

if __name__ == '__main__':
    print("所有组合可能个数:{}".format(A(34,14)))

运行得到结果为:326,520,504,500也就是3265亿种组合。

求通项代数式

没求出来