Сколько разных возможных способов сидения людей за круглым столом?

Question

Я разрабатываю алгоритм и изучаю возможность максимального числа итераций, прежде чем прийти к выводу.

В реальном мире это похоже на проблему классического сидения за круглым столом. Подскажите, пожалуйста, максимальное количество способов, которыми n человек могут сидеть за круглым столом без повторений?

Спасибо

Answer 1

Классическая задача перестановки: разбить ее на две части: 1) Все возможные комбинации 2) Разделите на n количество начальных локаций (поскольку они не имеют значения)

Я получаю (n-1)! возможности. Я что-то здесь упускаю? (Я не делаю статистику много, поэтому я немного ржавый)

Answer 2

Давайте проследим решение этой проблемы.

Во-первых, давайте посмотрим, сколько способов мы можем расположить n человек в строке.Есть n разных людей, которых мы можем выбрать для начала.Из оставшихся n - 1 любой n - 1 может быть поставлен во вторую позицию.Из оставшихся n - 2 любые n - 2 могут быть помещены в третью позицию и т. Д. В более общем случае мы получаем формулу

Num договоренности = 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

Однако мы не можем сделать выводиз того что количество рассадки в п!потому что мы создали одну и ту же рассадку несколько раз здесь.В качестве трюка, давайте предположим, что мы всегда выписываем цикл так, чтобы 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)!различные способы посадить людей в кольцо.

Надеюсь, это поможет!