Combien de façons différentes les personnes peuvent-elles être assises autour d'une table ronde?

Question

Je développe un algorithme et je cherche la possibilité du nombre maximum d'itérations avant d'arriver à une conclusion.

Dans le monde réel, c'est similaire au problème classique du placement à la table ronde. Pouvez-vous me dire le nombre maximum de façons dont n personnes peuvent être assises à une table ronde sans répétitions ?

Merci

Answer 1

Problème de permutation classique : Divisez-le en deux sections : 1) Toutes les combinaisons possibles 2) Divisez par n comme le nombre d'emplacements de départ (puisqu'ils n'ont pas d'importance)

Je trouve (n-1)! possibilités. Est-ce que j'oublie quelque chose ici? (Je ne fais pas beaucoup de stats, donc je suis un peu rouillé)

Answer 2

Recherchons la solution à ce problème.

Tout d'abord, voyons combien de façons on peut organiser n personnes en ligne. Il y a n personnes différentes que l'on peut choisir pour mettre au début de la ligne. Parmi les n - 1 qui restent, n'importe lequel des n - 1 peut être placé en deuxième position. Parmi les n - 2 qui restent, n'importe lequel des n - 2 peut être placé en troisième position, etc. Plus généralement, on obtient la formule

Nombre d'arrangements = n x (n - 1) x (n - 2) x ... x 1 = n!

Donc il y a n! façons différentes de permuter les gens en ligne. Plus généralement, il y a n! façons différentes de réarranger n éléments uniques.

Maintenant, que se passe-t-il lorsque l'on organise les gens en cercle ? Pour chaque permutation linéaire, on peut convertir cet arrangement en un arrangement circulaire en connectant les deux extrémités. Par exemple, avec trois personnes, il y a six façons de les ordonner en ligne :

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

Ces correspondances aux cercles suivants :

           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

Cependant, on ne peut pas conclure que le nombre d'arrangements d'assise est de n! car nous avons créé le même arrangement d'assise plusieurs fois ici. Pour résoudre cela, supposons toujours que l'on écrive le cycle de sorte que 1 soit en haut du cycle. Alors on a généré les cycles suivants :

           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

Remarquez que nous avons généré ce qui suit :

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

En réalité, il y a seulement deux arrangements différents ; nous les avons juste générés chacun trois fois.

La raison de cela est que puisque le cercle n'a pas de point de départ et d'arrivée définitif, nous finirons par générer de multiples rotations de chacun des différents arrangements. En particulier, s'il y a n personnes à placer, nous finirons par générer n copies différentes de la même rotation, une avec chacun des invités différents en haut. Par conséquent, pour obtenir le nombre total d'invités, pour chacun des différents cercles, nous devons en ignorer tous sauf un. Comme il y a n différentes copies de chaque cercle, cela signifie que le nombre total est donné par

n! / n = (n - 1)!

Il y a donc (n - 1)! façons différentes de placer les gens en cercle.

J'espère que cela vous aidera !