De combien de façons différentes les personnes peuvent-elles s'asseoir dans une table ronde?

Question

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

Dans le monde réel, il est similaire au problème des sièges de table ronde classique. Pouvez-vous s'il vous plaît me dire le nombre maximum de façons n personnes être assis dans une table ronde sans répétitions?

Merci

Answer 1

Trouvons la solution à ce problème. Premièrement, voyons de combien de façons nous pouvons organiser n personnes dans une ligne. Il y a n personnes différentes que nous pouvons choisir de mettre en première ligne. Parmi les n-1 qui restent, n'importe quel n-1 peut être placé en deuxième position. Parmi les n - 2 qui restent, n - 2 d 'entre eux peuvent être placés en troisième position, etc. Plus généralement, nous obtenons la formule

Num arrangements = nx (n - 1) x (n - 2) x ... x 1 = n!

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

Maintenant, que se passe-t-il lorsque nous organisons des personnes dans un ring? Pour chaque permutation linéaire, nous pouvons convertir cet arrangement en un arrangement en anneau en reliant les deux extrémités. Par exemple, avec trois personnes, il y a six façons de les commander en ligne:

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

Ces carte aux anneaux 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, nous ne pouvons pas conclure que la nombre de places assises dans n! parce que nous avons créé le même arrangement de sièges plusieurs fois ici. Comme une astuce, supposons que nous écrivons toujours le cycle de sorte que 1 soit en haut du cycle. Ensuite, nous avons 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 

Notez que nous avons généré les suivantes:

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

Alors, vraiment, il n'y a que deux arrangements différents; nous venons de générer chacun d'eux trois fois.

La raison en est que, parce que l'anneau n'a pas de point de début et de fin définitifs, nous finirons par générer plusieurs rotations de chacun des différents arrangements. En particulier, s'il y a n personnes que nous devons asseoir, 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 anneaux, nous devons ignorer tous sauf un d'entre eux.Comme il y a n copies différentes de chaque anneau, cela signifie que le nombre total est donné par

n!/n = (n - 1)!

Donc il y a (n - 1)! différentes façons de placer les gens dans un ring.

Espérons que cela aide!

Answer 2

problème de permutation classique: diviser en deux sections: 1) Toutes les combinaisons possibles 2) Diviser par n comme le nombre d'emplacements de départ (car ils ne comptent pas)

I obtenir (n-1)! possibilités. Est-ce que je manque quelque chose ici? (Je ne fais pas beaucoup de statistiques, donc je suis un peu rouillé)