在离散数学课堂上与贝尔数不谋而合

前言

今天不更新「外源推文」，来一个特别篇。

分划方案问题

昨天的离散数学课上，教授留下了一个问题没有讲：给定有 $n$ 个元素的集合，求其分划方案数。一个有效的分划需满足“不重不漏”，任意两个子集相交为 $\varnothing$，所有子集相并为父集。

为了简便，不妨设 $n$ 个元素的集合为 $\{1,2,\cdots ,n\}$。

例如，3 个元素的集合有 5 种分划方案：

$\{\{1,2,3\}\}$，$\{\{1,2\},\{3\}\}$，

$\{\{1,3\},\{2\}\}$，$\{\{2,3\},\{1\}\}$，

$\{\{1\},\{2\},\{3\}\}$

我独立进行的工作

教授说“以后再讲”。下课后，我稍加思索，感觉可以用动态规划：利用已解出的子问题解决更大的子问题，递推到原问题。

设 $f(n)$ 为 $n$ 个元素的集合的分划方案数，定义边界 $f(0)=1$（类似 $C_n^0=1$），易得 $f(1)=1$，$f(2)=2$。

我以 $f(3)$ 为例，进行了如下推导：

$\{1,2,3\}$，相当于向 $\{1,2\}$ 添加一个新元素 3，讨论 3 与原有元素的分组情况：

• 保留整个 $\{1,2\}$：2 选 2，为 $C_2^2$；$\{1,2\}$ 含 2 个元素，有 $f(2)$ 种分划；方案数为 $C_2^2\ast f(2)=2$。
  • 对应 $\{\{1,2,3\}\}$，$\{\{1,2\},\{3\}\}$
• 从 $\{1,2\}$ 中拆出 1 个：2 选 1，为 $C_2^1$；$\{1,2\}$ 还剩 1 个元素，有 $f(1)$ 种分划；方案数为 $C_2^1\ast f(1)=2$。
  • 对应 $\{\{1,3\},\{2\}\}$，$\{\{2,3\},\{1\}\}$
• 不保留 $\{1,2\}$ 的元素：2 选 0，为 $C_2^0$；$\{1,2\}$ 还剩 0 个元素，有 $f(0)$ 种分划；方案数为 $C_2^0\ast f(0)=1$。
  • 对应 $\{\{1\},\{2\},\{3\}\}$

合并所有分支，得$f(3)=C_2^2\ast f(2)+C_2^1\ast f(1)+C_2^0\ast f(0)=5$

验证 $f(4)$，与上课算得的 15 一致，由此，我合理猜想通项公式为$f(n+1)=\underset{k=0}{\sum ^n}{C}_n^k\ast f(k)$

解释为，每个子问题的答案为先前所有子问题的答案分别乘以一个组合数再求和。

顺手写了动态规划的伪代码：

贝尔数

只验证 $f(4)$ 怎么能行，我又验证了 $f(5)$ 和 $f(6)$。

$f(5)$ 的手算、公式结果一致，都为 52；但 $f(6)$ 手算 333，公式 203。

公式推错了？

于是我上网搜索这个数列的前 6 项：

原来，我跟贝尔数不谋而合，通项写得一模一样，只是我手算 $f(6)$ 算错了🤣

Python 实现

虽然叫“通项”，但其实不能直接求 $f(n)$，仍需把 $f(0)$ 到 $f(n-1)$ 都求出，还要与组合数相乘再累加，计算量可想而知。

所以，请 Python 来帮忙吧！

def bell_number(n: int) -> List[int]:
    f = [0 for _ in range(0, n + 1)]
    f[0] = 1
    for i in range(1, n + 1):
        f[i] = sum(comb(i - 1, k) * f[k] for k in range(0, i))
    return f

$f(10)$ 就到 11 万了，真是没法手算😴

感触

第一次独立推导出已被公认的数学公式，虽然式子很简单，但还是挺开心的😸

再就是，动态规划的思想在课堂上得到应用，感觉算法题也不是白做的😚

最后

主系列「力扣题解」&「外源推文」&「生活分享」关注公众号：