type
status
date
slug
summary
tags
category
icon
password
最近复习离散数学的时候想到一个问题，记录一下。
首先科普一下集合的划分的知识：
对于集族 （奇妙定义法），如果其满足以下条件：
- 不含空集：
- 装住 A：
- 元素彼此不交：
那么称 为 A 的一个 划分 。
我想到的问题是：对于一个含有 n 个元素的有限集合，其有多少种划分？
也可以表述成一个更加接地气的形式：n 个不同的球，随便分，有多少种分法？
这道题目的结果称为 Bell 数 。看起来是一个简单的排列组合问题，但实际上比我们想象中复杂许多。利用现在的知识甚至难以给出一个显式的序列表达式，只能给出一个递归表达式：
直观意义就是将多出来的那个元素单独一类，和某一个元素一类，和某两个元素一类……和剩下 n 个元素一类。
最后附上一个我闲着没事写的 Bell 数计算代码（
千村万落生荆杞的动态规划.webp）。- 作者:Chlorine
- 链接:https://yoghurtlee.com/bell-number
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。