Esercizio lemma di Burnside
Inviato: 10 nov 2020, 22:16
Ciao ha tutti, ho questo esercizio di calcolo combinatorio il quale credo vada risolto tramite il lemma di Burnside.
Ho preso questo link come riferimento per studiare: https://brilliant.org/wiki/burnsides-lemma/
Sembra piuttosto semplice ma non riesco a far quadrare i conti.
Ho una griglia RxC nella quale ognuna delle celle può assumere valore 0 oppure 1.
Mi viene chiesto di calcolare il numero di possibili orbite ottenibili in base ad un criterio di equivalenza tra griglie.
Il criterio in questione stabilisce che date due griglie, le due sono equivalenti se partendo da una e applicando un qualsiasi numero di scambi tra colonne oppure di scambi tra righe (colonna con colonna, riga con riga, NON riga con colonna) è possibile ottenere la seconda griglia.
Un'orbita è definita come l'insieme di griglie equivalenti.
Detto questo, sto cercando di partire da una griglia semplice, una 2x2.
Ignorando momentaneamente Burnside, e scrivendo tutte le combinazioni, mi risultano 2^4 = 16 griglie.
Ho direttamente scritto le 16 possibilità e ho potuto vedere che da queste ottengo 7 orbite.
Burnside stabilisce che il numero di Orbite equivale alla sommatoria di Fixed Points diviso per il numero di Simmetrie (trasformazioni) della griglia.
Vorrei riuscire ad arrivare ad ottenere 7 orbite applicando Burnside alla griglia 2x2 ma i conti non quadrano.
Infatti al momento considero 3 possibili Simmetrie, in base al criterio fornito dal testo
- L'identità, per cui non applico alcuna trasformazione
- Scambio di colonne
- Scambio di righe
Per ognuna di queste verifico anche a mano il numero di fixed points e mi risulta
- Identità --> 16
- Colonna --> 4
- Riga --> 4
Applico Burnside: Orb = (16+4+4)/3 = 8 mentre dovrebbero risultare 7.
Grazie.
Ho preso questo link come riferimento per studiare: https://brilliant.org/wiki/burnsides-lemma/
Sembra piuttosto semplice ma non riesco a far quadrare i conti.
Ho una griglia RxC nella quale ognuna delle celle può assumere valore 0 oppure 1.
Mi viene chiesto di calcolare il numero di possibili orbite ottenibili in base ad un criterio di equivalenza tra griglie.
Il criterio in questione stabilisce che date due griglie, le due sono equivalenti se partendo da una e applicando un qualsiasi numero di scambi tra colonne oppure di scambi tra righe (colonna con colonna, riga con riga, NON riga con colonna) è possibile ottenere la seconda griglia.
Un'orbita è definita come l'insieme di griglie equivalenti.
Detto questo, sto cercando di partire da una griglia semplice, una 2x2.
Ignorando momentaneamente Burnside, e scrivendo tutte le combinazioni, mi risultano 2^4 = 16 griglie.
Ho direttamente scritto le 16 possibilità e ho potuto vedere che da queste ottengo 7 orbite.
Burnside stabilisce che il numero di Orbite equivale alla sommatoria di Fixed Points diviso per il numero di Simmetrie (trasformazioni) della griglia.
Vorrei riuscire ad arrivare ad ottenere 7 orbite applicando Burnside alla griglia 2x2 ma i conti non quadrano.
Infatti al momento considero 3 possibili Simmetrie, in base al criterio fornito dal testo
- L'identità, per cui non applico alcuna trasformazione
- Scambio di colonne
- Scambio di righe
Per ognuna di queste verifico anche a mano il numero di fixed points e mi risulta
- Identità --> 16
- Colonna --> 4
- Riga --> 4
Applico Burnside: Orb = (16+4+4)/3 = 8 mentre dovrebbero risultare 7.
Grazie.