blog

设有 N 个数，从 1, 2, …, N 中取值（可重复可不用）；它们按顺序排成一列，要求在出现 2 之前必须出现 1，在 3 之前必须出现 2，以此类推。试问共有多少种排列方式？

设有$N$个数，从$1,2,...,N$中取值（可重复可不用）；它们按顺序排成一列，要求在出现$2$之前必须出现$1$，在$3$之前必须出现$2$，以此类推。试问共有多少种排列方式？

举例

当$n=3$时，共有$111,112,121,122,123$五种;

当$n=4$时，共有$1111$, $1112$, $1121$, $1122$, $1123$, $1211$, $1212$, $1213$, $1221$, $1222$, $1223$, $1231$, $1232$, $1233$,$1234$十五种。

研究

二维数组递推

在一个个排数字时，设$T(m,n)$表示已经出现的最大数字为$m$,后面还需要排$n$个数字时，接下去排列方式的种数。 考虑接下去一个数字，它可以从$1$到$m+1$取值。如果它落在$[1,m]$内，之后就共有$m\times T(m,n-1)$种方式; 如果它等于$m+1$,之后就共有$1\times T(m+1,n-1)$种方式。 因此，可得到方程

$$T(m,n)=mT(m,n-1)+T(m+1,n-1)$$

另外，画一下递推图可知只需$T(m,1)$的边界条件就能确定整个数组。由定义，显然

$$T(m,1)=m+1$$

最终我们得到了数组的递推关系。

$$\begin{aligned} T(m,n)&=mT(m,n-1)+T(m+1,n-1)\\ T(m,1)&=m+1 \end{aligned}$$

现在考虑我们的问题，第一个数字只能为$1$，显然共有$T(1,N-1)$种排列方法。

一些尝试

$$\begin{aligned} T(m,2)&=mT(m,1)+T(m+1,1)=m^{2}+2m+2\\ T(m,3)&=mT(m,2)+T(m+1,2)=m^3+3m^2+6m+5 \end{aligned}$$

于是$T(1,1)=2,T(1,2)=5,T(1,3)=15$，分别对应$n=2$,$n=3$,$n=4$的情况。

贝尔数

贝尔数$B_n$为$n$元素集合划分的种类数，它正好就是$T(1,n-1)$

证明：

对${a_1,\ldots,a_n}$的任意一种划分，由集合元素无序性，可将含有$a_1$的集合$S_1$排在第一位。接着在$S_1$集合中的元素外的元素中找编号最小的元素，将其所在的集合排在第二位，依次类推。最终将$a_k$所在的集合数列在一起即可得到从$1$到$n$的一个排列。易验证这个排列就是我们问题所需要的。如$\{\{a_1,a_3\},\{a_2,a_5\},\{a_4\}\}$就对应$12132$.

将这个过程反过来，同样能由$1$到$n$的一个排列得到集合的一个划分，而由排列的限制可知这个对应关系是不重的。因此这个排列的问题和贝尔数的定义是两个等价的问题。

贝尔数的公式和问题的解

贝尔数是对应的一组第二类斯特林数的和，即

$$ B_n=\sum_{m=0}^{n}{\sum_{k=0}^m{(-1)^kC_m^k(m-k)^n}}$$

由此公式即可算出问题的答案,并且我们知道了$T(1,n-1)=B_n$,但是关于$T(m,n)$仍然不知道它的通项公式。