集合的划分与排列计数

manthanein

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`.

manthanein

这里有一个关于集合划分数Div(n)的计算程序，不知道对不对。

kastin

1. 这个是贝尔数 `B_n`，参见http://baike.baidu.com/link?url= ... jJLlEYaZj-sa0mlnbya
其计算可以通过递归公式，或者直接对第二类Stirling数求和，本身没有一般通项公式。

2. 这个就简单了，每次计算出第二类Stirling数S(n,k)，然后乘以全排列k!，所得积求和即可（k从1到n）。

下面是MMA代码：

1. div[n_]:=Total@StirlingS2[n,Range[n]];
   
2. pd[n_]:=Dot[Factorial[Range[n]],StirlingS2[n,Range[n]]];

复制代码