集合的划分与排列计数
1、集合 `S` 的非空子集之集`\{S_1, S_2, ..., S_k\}`称为`S`的一个划分，当且仅当诸子集之并`\bigcup{S_i}=S`，而两两之交为空。问题：计`\text{Div}(n)`为一个 `n` 元集可有的不同划分数，求`\text{Div}(n)`的通项公式。
2、给一个划分中的子集编上序号便得划分的一个排列 ，称为 `S` 的一个划分排列。
问题：计 `\text{Pd}(n)` 为一个 `n` 元集可有的不同划分排列数，求 `\text{Pd}(n)` 的通项公式。
比如S={1,2,3}
共有5个不同的划分：{{1,2,3}}, {{1},{2,3}}, {{2},{1,3}},{{3},{1,2}},{{1},{2},{3}}
以及13个划分排列：
{1,2,3},
{1,2}{3}, {3}{1,2},
{1}{2,3}, {2,3}{1},
{1,3}{2}, {2}{1,3},
{1}{2}{3}, {1}{3}{2},{2}{1}{3}, {2}{3}{1}, {3}{1}{2}, {3}{2}{1}
所以`\text{Div}(3)=5, \text{Pd}(3)=13`.
划分的计数程序
这里有一个关于集合划分数Div(n)的计算程序，不知道对不对。 1. 这个是贝尔数 `B_n`，参见http://baike.baidu.com/link?url=HK9Me1IMSFaAImW1QnDKVGQrE9CYENbZNdwdC0vSNHI2V3h6EHe-Vg9uP6W5EYcYG9wjJLlEYaZj-sa0mlnbya其计算可以通过递归公式，或者直接对第二类Stirling数求和，本身没有一般通项公式。
2. 这个就简单了，每次计算出第二类Stirling数S(n,k)，然后乘以全排列k!，所得积求和即可（k从1到n）。
下面是MMA代码：
div:=Total@StirlingS2];
pd:=Dot],StirlingS2]];
页:
[1]