可能的不同组合数量是多少？

Question

5

你将获得有m个空位和n个数字的组合。你需要填充这些m个位置，以使每个数字至少出现一次。

例如

当m为4且n为3时，你有4个位置和3个数字。因此，总共可能的组合数为36。

让我们来看一个简单的例子：

当m=3且n=2（假设是a和b）时，可能的组合如下：

aba aab abb bab bba baa

因此，只有6个组合是可能的。是否有任何公式可以计算出可能的组合数？

- heema

这个问题似乎不适合讨论，因为它涉及数学而非编程。 - Paul R

我能闻到一些动态规划的味道。也许一些递归函数可以解决这个问题。 - user3345047

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ACcreator · Accepted Answer

问题的答案

答案是n!S(m,n)，其中S是斯特林数第二类。

例如，对于m=4，n=3，n!=6，S(4,3)=6，因此n!S(m,n)=36，这就是预期的答案。

斯特林数第二类S(m,n)用于计算将m个元素分成n个非空子集的方法数量。因此，对于这个问题，S(m,n)计算将m个位置分成n组的方法数量，每组对应一个数字。在分组后，我们应该为每个组指定一个数字，有n!种方法可以做到这一点。因此，答案是n!S(m,n)。