算法combinatorics

Question

我想解决组合问题，它似乎很容易，但我有一些麻烦。

如果我最多有X个桌子和N个人坐在桌子上，每张桌子可以有1到N个座位，我只能坐在长方形桌子的一边坐下来）。

我想做一个代码，可以计算从1到K表的所有座位位置的分布。例如，如果我有12个人和1张桌子，我有479001600个座位人员的方法（这很容易计算，我使用了12的阶乘）。

但是，如果我有12人和3桌我有4390848000座位的人的方式。我尝试过不同的解决方案，但我无法找到正确的解决方案。

我试图将3分为12，然后使用结果的阶乘（它没有工作），我试着用12！ * 3（它也没有工作）。

有人能给我一个我可以使用的算法的提示吗？

Answer 1

阅读关于Lah Numbers的文章，应该有所帮助。

Answer 2

我不认为4,390,848,000是一个正确的答案（如果计算空座位）。

将N人安排到X个N个座位表中的方法的数量等同于将N个人安排到1个（N * X）个座位表。结果非常明显：（NX选择N × N！）。

• NX选择N =将N人纳入NX座位而不考虑排列的方法数量。
• N！ =这N个人的排列数。

例如

[a b|_ _] [a _|b _] [a _|_ b] 
[_ a|b _] [_ a|_ b] [b a|_ _] 
[_ _|a b] [b _|a _] [_ b|a _] = 4 choose 2 * 2! = 12. 
[b _|_ a] [_ b|_ a] [_ _|b a] 

但是（36选12 × 12）！= 599,555,620,984,320,000。

即使表格是相同的（去除因子3！= 6），结果99,925,936,830,720,000仍然远远大于4,390,848,000。