Combinazione in simmetria
Supponiamo di avere i sei vertici identici collegati con due linee differenti colorate come verde e nero.
Voglio contare in quanti modi unici possiamo creare una partizione in questo sistema. Ad esempio, se voglio creare partizioni 1x5,
Il modo più semplice a cui possiamo pensare è 6C1 = 6 casi. Tuttavia, il sistema ha una simmetria rotazionale con un angolo di 60 gradi. Quindi avremo solo 2 partizioni uniche. Se ignoriamo ulteriormente l'ordinamento del colore, abbiamo solo una partizione unica . La partizione può contenere solo uno verde e uno nero.
Per le partizioni 3x3, diventa un po 'più complicato. Innanzitutto, possiamo scoprire che esistono un totale di 6C3 = 20 partizioni. Una volta eliminato il doppio conteggio, abbiamo solo 10 casi.
Tuttavia, dobbiamo tenere conto della simmetria. Conosco la risposta facendolo a mano, abbiamo solo 4 casi unici. abbiamo (1 (3 verdi e 3 neri) +3 (verde + nero) +3 (3 neri e uno verde) +3 (3 verdi e uno nero).
Utilizzando questa regola, sono stato in grado di contare le soluzioni uniche come segue
(4 scegli 1) abbiamo 1 caso unico
(4 scegli 2) abbiamo 3 casi unici
(6 scegli 1) abbiamo 1 caso unico
(6 scegli 2) abbiamo 4 casi unici
(6 scegli 3) abbiamo 4 casi unici
C'è un modo per trovare la soluzione di combinazione generalizzata con la simmetria del sistema?
Risposte
Stai chiedendo il numero di partizioni di un insieme (qui, un esagono) che sono diverse rispetto ad alcune simmetrie (in questo caso, simmetria rotazionale). In generale questa è una domanda importante e ben studiata in matematica. È fantastico che tu abbia trovato questo materiale studiando questo esempio in profondità.
Il modo molto generale per risolvere questo problema è usare qualcosa chiamato lemma di Burnside . Se vuoi saperne di più, dovresti cercare un libro di testo sulla teoria dei gruppi.
Per risolvere questo esempio specifico in modo sistematico , possiamo usare le idee dal lemma di Burnside senza bisogno esplicitamente del background della teoria dei gruppi. Ad esempio, riformuliamo la tua prova che ci sono$4$ partizioni distinte dell'esagono in due serie di tre punti ciascuna.
Hai correttamente sottolineato che ci sono $\binom{6}{3} = 20$ possibili sottoinsiemi di dimensione $3$, quindi ci sono $\binom{6}{3} / 2 = 10$possibili partizioni. Per una partizione$P$, permettere $f(P)$ denotano il numero di modi di diverse copie ruotate di $P$.
Ad esempio, nella tua immagine (copiata sotto), lascia $P$ essere la partizione in alto a sinistra e $P'$essere la partizione in alto a destra. Poi$f(P) = 3$ e $f(P') = 1$.
Considera l'elenco di tutti $10$ partizioni $P_1, \dots, P_{10}$. Ogni partizione$P$, è esattamente "sovrastimato" $f(P)$volte. Per fare in modo che ogni partizione diversa rispetto alla rotazione venga contata una volta, eseguiamo il seguente trucco. Consideriamo la somma
$$ \sum_{i=1}^{10} \frac{1}{f(P_i)} .$$
Nel caso in cui stiamo cercando le partizioni dell'esagono in due serie di dimensione tre, questa diventa la somma
$$ \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + 1 = 4,$$
che è esattamente quello che hai contato!
Questa formula funziona anche nel caso in cui dividiamo l'esagono in un insieme di dimensioni $1$ e un insieme di dimensioni $5$. Ci sono$6$ partizioni totali e per ogni partizione che abbiamo $f(P) = 6$(perché ogni partizione è una rotazione l'una dell'altra). Quindi la somma è
$$ \sum_{i=1}^6 \frac{1}{f(P)} = \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = 1.$$
Prova questa formula su altri casi se sei confuso come funziona. Funziona anche se sostituisci l'esagono con uno diverso$n$-gon, per esempio. La parte difficile diventa calcolare$f(P)$ per ogni partizione $P$(ed enumerando tutte le possibili partizioni). Spero che questo risponda alla tua domanda.