一个包含 k 元素的集合可以组成多少个具有 n 个部分的不同分区？
集合 {1,2,3,4} 可以组成多少个恰好具有两个部分的不同分区？ 此列表中有 4 个元素需要分为 2 部分。我把这些写出来，总共得到了 7 种不同的可能性：
- {{1},{2,3,4}}
- {{2},{1,3,4}}
- {{3},{1,2,4 }}
- {{4},{1,2,3}}
- {{1,2},{3,4}}
- {{1,3},{2,4}}
- {{1,4},{2 ,3}}
现在我必须回答同样的问题{1,2,3,...,100}。 此列表中有 100 个元素需要分为 2 部分。我知道分区的一部分的最大尺寸是 50（即 100/2），最小尺寸是 1（因此一个部分有 1 个数字，另一部分有 99）。如何确定两个部分的划分有多少种不同的可能性，而不写出每种可能组合的无关列表？ 答案能否简化为阶乘（例如 12！）？
是否有一个通用公式可以用来计算一个包含 k 元素的集合可以由多少个具有 n 个部分的不同分区组成？
How many different partitions with exactly two parts can be made of the set {1,2,3,4}?
There are 4 elements in this list that need to be partitioned into 2 parts. I wrote these out and got a total of 7 different possibilities:
- {{1},{2,3,4}}
- {{2},{1,3,4}}
- {{3},{1,2,4}}
- {{4},{1,2,3}}
- {{1,2},{3,4}}
- {{1,3},{2,4}}
- {{1,4},{2,3}}
Now I must answer the same question for the set {1,2,3,...,100}.
There are 100 elements in this list that need to be partitioned into 2 parts. I know the largest size a part of the partition can be is 50 (that's 100/2) and the smallest is 1 (so one part has 1 number and the other part has 99). How can I determine how many different possibilities there are for partitions of two parts without writing out extraneous lists of every possible combination?
Can the answer be simplified into a factorial (such as 12!)?
Is there a general formula one can use to find how many different partitions with exactly n parts can be made of a set with k-elements?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
1) stackoverflow 是关于编程的。您的问题属于 https://math.stackexchange.com/ 领域。
2) n 个元素的集合有 2n 个子集（因为每个 n 元素可能包含在特定子集中，也可能不包含在特定子集中）。这为我们提供了将 n 元素集划分为两个子集的 2n-1 个不同分区。这些分区之一是琐碎分区（其中一部分是空子集，另一部分是整个原始集），从您的示例来看，您似乎不想计算琐碎分区。所以答案是 2n-1-1（对于 n=4，给出 23-1=7）。
1) stackoverflow is about programming. Your question belongs to https://math.stackexchange.com/ realm.
2) There are 2n subsets of a set of n elements (because each of n elements may either be or be not contained in the specific subset). This gives us 2n-1 different partitions of a n-element set into the two subsets. One of these partitions is the trivial one (with the one part being an empty subset and other part being the entire original set), and from your example it seems you don't want to count the trivial partition. So the answer is 2n-1-1 (which gives 23-1=7 for n=4).
n 个部分和 k 个元素的一般答案是第二类斯特林数 S(k, n)。
请注意，通常的约定是元素总数为 n，因此 S(n,k)
计算通用公式相当难看，但对于 k=2 是可行的（使用通用符号）：
因此S(n,2) = 1/2 ( (+1) * 1 * 0n +(-1) * 2 * 1n + (+1) * 1 * 2n ) = (0-2+2n)/2 = 2n-1-1
The general answer for n parts and k elements would be the Stirling number of the second kind S(k,n).
Please beware that the usual convention is with n the total number of elements, thus S(n,k)
Computing the general formula is quite ugly, but doable for k=2 (with the common notation) :
Thus S(n,2) = 1/2 ( (+1) * 1 * 0n +(-1) * 2 * 1n + (+1) * 1 * 2n ) = (0-2+2n)/2 = 2n-1-1