人们可以在圆桌会议上坐多少种不同的方式？

Question

我正在开发一种算法,并在得出最终迭代次数的可能性之前得出结论.

在现实世界中,它类似于经典圆桌座位问题.你能否告诉我一个人坐在圆桌旁而不重复的最大数量？

谢谢

Answer 1

经典排列问题:将其分为两部分:1)所有可能的组合2)除以n作为起始位置的数量(因为它们无关紧要)

我得到(n-1)!可能性.我在这里错过了什么吗？(我不做太多的统计,所以我有点生锈)

Answer 2

让我们来看看这个问题的解决方案.

首先,让我们看看我们可以在一条线上安排n个人的方式.我们可以选择将不同的人放在前线.在剩下的n - 1中,任何n - 1都可以放在第二位.在剩下的n - 2中,任何n - 2可以被置于第三位,等等.更一般地说,我们得到公式

数量排列= nx(n - 1)x(n - 2)x ... x 1 = n!

所以有n!在一条线上排列人的不同方式.更一般地说,有n!重新排序n个独特元素的不同方法.

现在,当我们安排人们进入戒指时会发生什么？对于每个线性排列,我们可以通过连接两端将该排列转换为环排列.例如,有三个人,有六种方法可以排成一行:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

这些映射到以下环:

           1
1 2 3  -> / \
         3---2

           1
1 3 2  -> / \
         2---3

           2
2 1 3  -> / \
         3---1

           2
2 3 1  -> / \
         1---3

           3
3 1 2  -> / \
         2---1

           3
3 2 1  -> / \
         1---2

但是,我们不能从中得出结论n座位安排的数量!因为我们在这里多次创造了相同的座位安排.作为一个技巧,让我们假设我们总是写出循环,使1处于循环的顶部.然后我们生成了以下周期:

           1
1 2 3  -> / \
         3---2

           1
1 3 2  -> / \
         2---3

           1
2 1 3  -> / \
         2---3

           1
2 3 1  -> / \
         3---2

           1
3 1 2  -> / \
         3---2

           1
3 2 1  -> / \
         2---3

请注意,我们已生成以下内容:

   1              1
  / \   x3       / \   x3
 2---3          3---2

所以真的,只有两种不同的安排; 我们刚刚生成了三次.

这样做的原因是因为环没有明确的起点和终点,我们最终会产生每个不同排列的多次旋转.特别是,如果我们需要安排n个人,我们最终将生成相同轮换的n个不同副本,每个副本位于顶部.因此,为了得到每个不同环的客人总数,我们需要忽略除了其中一个之外的所有客户.由于每个环有n个不同的副本,这意味着总数由下式给出

N!/ n =(n - 1)!

所以有(n - 1)!不同的方式让人们坐在一个环.

希望这可以帮助!