0

我正在尝试解决一个组合数学问题，这似乎很容易，但我遇到了一些麻烦。

如果我最多有 X 张桌子，并且 N 人坐在桌子上，每张桌子可以有 1 到 N 个座位，我只能坐在长方形桌子的一侧（所以人们坐的顺序很重要）。

我想编写一个代码，可以计算从 1 到 K 桌的所有座位分布。

例如，如果我有 12 个人和 1 张桌子，我有 479001600 种座位方式（这很容易计算，我使用了 12 的阶乘）。

但如果我有 12 个人和 3 张桌子，我有 4390848000 种座位方式。我尝试了不同的解决方案，但找不到正确的解决方案。

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

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

4

2 回答 2

3

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

于 2010-06-03T10:19:53.063 回答
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 大得多。

于 2010-06-03T10:11:41.457 回答