math - 有多少个具有恰好 n 个部分的不同分区可以由具有 k 个元素的集合组成？

Question

集合 {1,2,3,4} 可以构成多少个具有恰好两个部分的不同分区？此列表中有 4 个元素需要分成 2 个部分。我把这些写出来，总共有 7 种不同的可能性：

1. {{1},{2,3,4}}
2. {{2},{1,3,4}}
3. {{3},{1,2,4}}
4. {{4},{1,2,3}}
5. {{1,2},{3,4}}
6. {{1,3},{2,4}}
7. {{1,4},{2,3}}

现在我必须为集合 {1,2,3,...,100} 回答同样的问题。此列表中有 100 个元素需要分成 2 个部分。我知道分区的一部分的最大尺寸是 50（即 100/2），最小的是 1（所以一部分有 1 个数字，另一部分有 99）。如何在不写出每个可能组合的无关列表的情况下确定两个部分的分区有多少种不同的可能性？答案可以简化为阶乘（比如 12！）吗？
有没有一个通用公式可以用来找出有多少个恰好有 n 个部分的不同分区可以由一个带有 k 元素的集合组成？

Answer 1

1）stackoverflow是关于编程的。您的问题属于https://math.stackexchange.com/领域。

2）n个元素的集合有2 ⁿ个子集（因为n个元素中的每一个都可能包含在特定子集中或不包含在特定子集中）。这给了我们一个 n 元素集的 2 ^{n-1 个}不同的分区到两个子集中。这些分区之一是微不足道的（其中一部分是空子集，另一部分是整个原始集），从您的示例来看，您似乎不想计算微不足道的分区。所以答案是 2 ^n-1 -1（对于 n=4 给出 2 ³ -1=7）。

Answer 2

n 部分和 k 元素的一般答案是第二类 S(k,n) 的斯特林数。

请注意，通常的约定是元素总数为 n，因此 S(n,k)

计算一般公式非常难看，但对于 k=2 是可行的（使用通用符号）：

因此 S(n,2) = 1/2 ( (+1) * 1 * 0 ⁿ +(-1) * 2 * 1 ⁿ + (+1) * 1 * 2 ⁿ ) = (0-2+2 ⁿ )/2 = 2 ^n-1 -1