字母表(Alphabet)的长度为m,单词(Word)的长度为n,字母表中的每一个字母都用到的单词有多少?

字母表(Alphabet)的长度为m,单词(Word)的长度为n,字母表中的每一个字母都用到的单词有多少?这个问题又是一个可以通过递归分析来解决的组合数学题目。

我们先假定这样的单词总数是 X(n, m)。当字母表的长度为m,单词的长度为n的时候,所有可能的单词总数是:

(1)   \begin{equation*} m^n \end{equation*}

在上面这么多单词中,只含有一个字母的单词总数是:

(2)   \begin{equation*} m \end{equation*}

只含有两个字母,并且这两个字母都用到了的单词总数是多少呢?首先从m个字母中选取两个字母的组合数目是:

(3)   \begin{equation*} C_{m}^2 \end{equation*}

而这两个字母组成的长度为 n ,而且这两个字母都用到了的单词,按照我们上面的递归定义则是 X(n, 2)。因为每个组合中的字母都不一样,而每个单词用到了所有的字母,所以所有这些组合代表的字母表形成的单词互相既不重复,又涵盖了所有长度为n而且用到了两个不同字母的单词。综上所述,所有两字母而且这两个字母都被用到的单词总数是:

(4)   \begin{equation*} C_{m}^2 \cdot X(n, 2) \end{equation*}

以此类推,所有三个字母而且这三个字母都被用到的单词总数是:

(5)   \begin{equation*} C_{m}^3 \cdot X(n, 3) \end{equation*}

这样可以一直推到 m-1。另外我们注意到在单词表只有一个字母的情况下,用到这个字母的长度为 n 的单词为 1,也就是 X(n, 1) = 1。那么我们把上面讨论过的只含有一个字母的单词总数可以表示为:

(6)   \begin{equation*} m = C_{m}^1 \cdot X(n, 1) \end{equation*}

我们从所有可能的 m^n 的单词中去除掉那些只有一个字母的单词、二个字母而且每个字母都被用到的单词、三个字母而且每个字母都被用到的单词、…、一直到m-1 个字母而且每个字母都被用到的单词,就得到了 m 个字母都被用到的单词,也就是:

(7)   \begin{equation*} \begin{split} X(n, m) &= m^n \\ &- C_{m}^1 \cdot X(n, 1) \\ &- C_{m}^2 \cdot X(n, 2) \\ &- ... \\ &- C_{m}^{m-1} \cdot X(n, m-1) \end{split} \end{equation*}

上面就是 X(n, m) 的一个递归定义,具体的实现在这里

from math import factorial

# combination
def C(n,m):
  return factorial(n) / (factorial(m) * factorial(n-m))


# Cache table for X, see below.
X_cache = {}

# A vocabulary of size 'm', a sample of size 'n' with replacement,
# How many possible results with all the 'm' items in it.
def X(n, m):
  if (n, m) in X_cache:
    return X_cache[(n, m)]

  if m == 1:
    result = 1
  elif n < m:
    result = 0
  else:
    # Start with total.
    result = int(m ** n)

    for i in range(1, m):
      # Pick a sub-vocabulary with 'i' items, calculate how many
      # samples can be made by using all of them, remove it from total. 
      result = result - C(m, i) * X (n, i)

  X_cache[(n, m)] = result
  return result


def CallX(n, m):
  result = X(n, m)
  print(f'n={n}, m={m}: {int(result)}')

CallX(25, 5)
print(f'Total: {5**25}')
print(X(25, 5) / 5**25)

在William Feller 的老爷爷原题中,字母表中有5个字母,单词的长度是25,问所有字母的出现的概率是多大,按照上面的公式计算我们有:

(8)   \begin{equation*} \dfrac{X(25, 5)}{5^{25}} = \dfrac{292402196893290112}{298023223876953125} = 98.1 \% \end{equation*}

而当字母表中有3个字母,单词的长度是3的时候,所有字母都出现的概率则是:

(9)   \begin{equation*} \dfrac{X(3, 3)}{3^3} = \dfrac{6}{27} = 22.2 \% \end{equation*}

看来单词一变长,基本上所有的字母也就都包括了。 🙂