Quanti modi diversi possibili le persone possono essere seduti in una tavola rotonda?

Question

Sto sviluppando un algoritmo e sto osservando una possibilità del numero massimo di iterazioni prima di arrivare a una conclusione.

Nel mondo reale, è simile al problema dei posti a sedere nella tavola rotonda classica. Puoi dirmi per favore il numero massimo di modi in cui le persone possono essere sedute in una tavola rotonda senza ripetizioni?

Grazie

Answer 1

Tracciamo la soluzione a questo problema.

In primo luogo, vediamo in quanti modi possiamo organizzare le persone in fila. Ci sono n persone diverse che possiamo scegliere di mettere in prima linea. Del n - 1 che rimane, qualsiasi n - 1 di loro può essere messo in seconda posizione. Del n - 2 che restano, ogni n - 2 di loro può essere messo in terza posizione, ecc Più in generale, si ottiene la formula

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

Quindi ci sono n! diversi modi di permutare le persone in una linea. Più in generale, ci sono n! diversi modi per riordinare n elementi unici.

Ora, cosa succede quando organizziamo le persone in un ring? Per ogni permutazione lineare, possiamo convertire quella disposizione in una disposizione ad anello collegando le due estremità. Ad esempio, con tre persone, ci sono sei modi per ordinare loro in una riga:

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

Questi mappa per i seguenti anelli:

  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 

Tuttavia, non si può concludere che il numero di posti a sedere in n! perché abbiamo creato la stessa disposizione dei posti qui più volte. Come trucco, supponiamo di scrivere sempre il ciclo in modo che 1 sia in cima al ciclo. Poi abbiamo generato i seguenti cicli:

  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 

noti che abbiamo generato il seguente:

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

Quindi, in realtà, ci sono solo due modalità differenti; abbiamo appena generato ciascuno di essi tre volte.

La ragione di ciò è che poiché l'anello non ha un punto iniziale e finale definitivo, finiremo per generare più rotazioni di ciascuna delle diverse disposizioni. In particolare, se ci sono n persone che abbiamo bisogno di sedersi, finiremo per generare n copie diverse della stessa rotazione, una con ciascuno dei diversi ospiti in cima. Di conseguenza, per ottenere il numero totale di ospiti, per ciascuno dei diversi anelli, dobbiamo ignorare tutti tranne uno di essi.Poiché vi sono n copie diverse di ciascun anello, ciò significa che il numero totale è dato da

n!/n = (n - 1)!

Quindi ci sono (n - 1)! modi diversi di sedere le persone in un anello.

Spero che questo aiuti!

Answer 2

classico problema permutazione: spezzare in due sezioni: 1) tutte le possibili combinazioni 2) dividere per n come il numero di posizioni di partenza (dal momento che non importa)

I prendi (n-1)! possibilità. Mi sto perdendo qualcosa qui? (Non faccio statistiche molto, quindi sono un po 'arrugginito)