Burnsideova lema

Često nam se u problemima prebrajanja može dogoditi da ne znamo prebrojiti objekte tako da simetrične objekte brojimo samo jednom.
Klasičan primjer je prebrojati ogrlice koje se sastoje od perli, a svaka perla može biti u jednoj od boja. Dvije ogrlice su iste (simetrične) ako se jedna može dobiti od druge rotacijom. Kako bi si olakšali život možemo ogrlice zamisliti kao lance s tim da su posljednja i prva perla susjedne. Budući da svaka perla može biti u jednoj od boja, imamo različitih lanaca. No ako ih gledamo kao ogrlice, neke smo prebrojali više puta. Na primjer, recimo da je i da imamo na raspolaganju dvije boje - crvenu (označimo ju slovom ) te plavu (označimo ju slovom ), lanci i predstavljaju iste ogrlice jer prvu možemo rotirati za jedno mjesto udesno i dobit ćemo drugu. Da bi doskočili ovom problemu koristit ćemo Burnsideovu lemu.

Definicija

Neka je skup objekata, a skup transformacija nad njima. Transformacija je bijekcija iz u . Kažemo da su dva elementa iz simetrična (ista) ako se jedan može dobiti od drugoga primjenom niza transformacija.
Burnsideova lema nam tada kaže da je broj elemenata iz koji su različiti s obzirom na skup transformacija jednak:

gdje predstavlja skup elemenata iz koji ostaju nepromjenjeni primjenom transformacije , tj. .

Primjer

Vratimo se prebrajanju ogrlica, skup je skup svih različitih lanaca od perli i boja. Skup transformacija je skup svih mogućih različitih rotacija:

Ako je broj lanaca koji ostanu isti rotiramo ih li za mjesta udesno, tada prema lemi vrijedi da je broj različitih ogrlica jednak:

Preostaje nam izračunati . Lanac ostaje isti kad se rotira za mjesta udesno ako i samo ako za svaku perlu vrijedi da je perla koja se nalazi mjesta desno od nje iste boje.
Te jednakosti će proizvesti klase ekvivalencije tj. skupine perli koje moraju biti iste boje. Konkretno, u ovom slučaju broj klasa ekvivalencije jednak je pa vrijedi:

Provjerimo i na konkretnom primjeru za . Izračunajmo prvo bitne vrijednosti funkcije :

Broj različitih ogrlica je . Zaista, postoji 6 različitih ogrlica:

.

O skupu transformacija

Pažljiv čitatelj zapitat će se može li skup transformacija biti baš bilo kakav. Odgovor je: ne može. Važno svojstvo koje mora zadovoljavati je zatvorenost tj. ako uzmemo bilo koje dvije (ne nužno različite) transformacije iz skupa tada i njihova kompozicija mora biti u .

Primjeri za vježbu

  1. Na koliko načina možemo obojati kocku, ako svaku stranu možemo obojati u jednu od tri boje. Dvije obojane kocke su iste ako se jedna od druge može dobiti rotacijama. (Rješenje: 57)
  2. Na koliko načina možemo obojati 3x3 ploču u dvije boje. Bojanja smatramo jednakima ako se jedno od drugoga može dobiti rotacijom ili refleksijom ploče. (Rješenje: 102)
© Ivan Katanić Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License