Esercizio lemma di Burnside

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
LoreGanz
Messaggi: 2
Iscritto il: 10 nov 2020, 21:57

Esercizio lemma di Burnside

Messaggio da LoreGanz »

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.
MatteD
Messaggi: 5
Iscritto il: 16 gen 2020, 20:01

Re: Esercizio lemma di Burnside

Messaggio da MatteD »

Sei sicuro di avere considerato tutte le trasformazioni possibili?
LoreGanz
Messaggi: 2
Iscritto il: 10 nov 2020, 21:57

Re: Esercizio lemma di Burnside

Messaggio da LoreGanz »

No, non sono sicuro, infatti ho anche scritto su un'altro forum dove mi è stato detto che devo prendere in considerazione anche il caso "scambio di riga e scambio di colonna".
In questo modo burnside con la griglia 2x2 effettivamente mi fornisce come risultato 7 Orbite.

In realtà mi è anche stato spiegato come espandere il tutto a griglie con un numero qualsiasi di righe e colonne, ma sto faticando a capire.

Questa è la mia domanda su tale forum: https://math.stackexchange.com/question ... 85_3902356

Oltre alla mia, mi hanno indicato anche queste altre due, dove è già presente una risposta più completa:
https://math.stackexchange.com/question ... g-rows-and
https://math.stackexchange.com/question ... nd-columns
Rispondi