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

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!)吗？
是否有一个通用公式可以用来计算具有 k 个元素的集合可以由多少个恰好有 n 个部分的不同分区组成？

Answer 1

1) stackoverflow 是关于编程的。您的问题属于https://math.stackexchange.com/境界。

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