|
|
有多少种方法可以将 $\{1,2,\ldots,n\}$ 分成三个不交的集合 $A$、$B$ 和 $C$，使得集合 $A$ 中没有两个连续的数
combinatorics - partitions of sets
从 $1,2,\dots,n$ 中选择 $k$ 个数使得没有两个数连续的方法数是$\dbinom{n-k+1}{k}$见此处
之后，我们将剩余的数划分为 $B$ 和 $C$。划分的方式数是$2S(n-k,2) + 2$。其中 $S(a,b)$ 是第二类Stirling数（有关解释请参见上面链接的答案）。因此答案是
$$\sum_{k=0}^{n} \binom{n-k+1}{k} (2S(n-k,2) + 2)$$ |
|
