Burnsideovo lemma

Buď $X$ libovolná konečná množina. Symbolem $S(X)$ značíme všechny permutace množiny $X$.

Připomeňme si, že permutace $n$ prvků je uspořádaná $n$-tice sestavená z těchto prvků tak, že se v ní každý vyskytuje právě jednou. Což můžeme říci i slovy, že permutace na množině $X$ je zobrazení z $X$ do $X$, které je prosté (žádné dva prvky se nezobrazí na stejný prvek) a na každý prvek se nějaký prvek zobrazí.

Množinu všech permutací na množině $X$ budeme značit $S(X)$, jednotlivé permutace budou značeny řeckými písmeny $(\pi, \rho, \ldots)$.

Permutace lze skládat a k dané permutaci lze najít permutaci inverzní.

Poznamenejme jenom, že $\pi \circ \rho$ značí permutaci vzniklou provedením $\rho$ a pak provedením $\pi$.

Pro další úvahy ještě vezměme jednu pevnou podmnožinu množiny $S(X)$, která je uzavřená na skládání permutací, a označme ji $G$. Poznamenejme, že $G$ je podmnožina permutací taková, že s každou permutací obsahuje i její inverzi a se dvěma permutacemi obsahuje i jejich složení (mj. tedy obsahuje i identitu, tj. permutaci, která všechny prvky nechává na místě).

Pro $x \in X$ označme $O_x = \{\pi(x) | \pi \in G\}$ takzvanou orbitu prvku $x$; to jsou body, kam se můžeme z $x$ dostat použitím permutací z $G$. Množinu všech orbit, tj. $\{O_x | x \in X\}$, budeme značit $\mathscr{O}$.

Všimněte si, že pokud $y \in O_x$, tak $O_x = O_y$. Intuitivně — pokud se z $x$ mohu dostat do $y$, tak se z obou mohu dostat do týchž míst.

Z toho ovšem plyne důležitý důsledek: orbity tvoří rozklad množiny $X$. Tzn., že každé $x \in X$ leží v právě jedné orbitě. Zjevně totiž $x \in O_x$. Pokud by $x$ ležel ještě v nějaké jiné orbitě, tj. $x \in O_y$ a $O_x \neq O_y$, pak dle předchozího odstavce $O_x = O_y$, což je spor. V množině $\mathscr{O}$ jsou tedy množiny, které jsou po dvou disjunktní a jejichž sjednocení je celé $X$.

Je-li $\pi \in S(X)$, označme $P_{\pi} = \{x \in X \ | \ \pi(x) = x\}$ množinu tzv. pevných bodů permutace $\pi$, tj. těch bodů, které $\pi$ nechává na místě.

Pro $x \in X$ označme $St_x = \{\pi \in G \ | \ \pi(x) = x\}$ množinu těch permutací z $G$, pro které je $x$ pevným bodem.

K důkazu použijeme následující lemma.

Lemma: (Vlastnosti St)
Je-li $x \in X$, tak $|O_x| \cdot |St_x| = |G|$.
Jsou-li $x, y \in X$ a $y \in O_x$, tak $|St_x| = |St_y|$.

(1) Pro $y \in O_x$ označme $\pi_y$ libovolnou permutaci z $G$, která převádí $x$ na $y$, tj. $\pi_y(x) = y$ (nějaká taková určitě existuje, jinak by $y$ nebylo v $O_x$).

Chceme ukázat, že dvojic $(y, \rho)$, $y \in O_x$, $\rho \in St_x$, je stejný počet jako prvků $G$. Nejlépe to uděláme tak, že najdeme předpis, jak takové dvojici přiřadit prvek $G$ tak, aby různým dvojicím odpovídaly různé prvky $G$ a každý prvek v $G$ byl použit.

Dvojici $(y, \rho)$ přiřaďme prvek $F(y, \rho) = \pi_y \circ \rho$. Protože $\pi_y$ i $\rho$ byly prvky $G$, je i jejich složení prvek $G$. Nyní je třeba ukázat, že zobrazení $F$ je prosté a na každý prvek se nějaký prvek zobrazí.

$F$ je prosté: vezměme $(y_1, \rho_1) \neq (y_2, \rho_2)$. Nechť nejprve $y_1 \neq y_2$. Potom $F(y_1, \rho_1)(x) = y_1$, $F(y_2, \rho_2)(x) = y_2$, a tedy zobrazení $F(y_1, \rho_1)$ a $F(y_2, \rho_2)$ se liší alespoň hodnotou v prvku $x$. Nechť je tedy $y_1 = y_2 = y$, a tudíž $\rho_1 \neq \rho_2$. Existuje proto nějaké $z \in X$, pro něž $\rho_1(z) \neq \rho_2(z)$. Ovšem pak i $F(y, \rho_1)(z) \neq F(y, \rho_2)(z)$. Takže $F$ je prosté.

Na každý prvek se nějaký prvek zobrazí: mějme $ \sigma \in G$ a hledejme $y \in X$, $\rho \in St_x$, že $F(y, \rho) = \sigma$. Stačí vzít $y = \sigma(x)$ a $\rho = \pi_{y}^{−1} \circ \sigma$.

(2) Abychom ukázali, že $|St_x| = |St_y|$, najdeme nějaké zobrazení $F: St_x \rightarrow St_y$, které bude prosté a kde na každý prvek se nějaký prvek zobrazí. Položme $F(\rho) = \pi_y \circ \rho \circ \pi_{y}^{−1} $. Ihned vidíme, že pro $\rho \in St_x$ je $F(\rho) \in St_y$. Nepříliš těžko vidíme, že F je prosté a na každý prvek se nějaký prvek zobrazí.

Dokazovanou rovnost upravme na tvar $ |\mathscr{O}| \cdot |G| = \sum_{\pi \in G}|P_{\pi}|$. Uvažme nyní množinu $A = \{ (\pi, x) \ | \ \pi \in G, x \in P_{\pi} \}$. Nyní použijeme poměrně častý trik: budeme počítat velikost množiny $A$ dvěma způsoby. Nejprve berme permutace $\pi$ z $G$ jednu po druhé a pro každou zjistěme, kolik $x \in X$ je možno k $\pi$ přidat, aby vznikla dvojice z $A$. Tímto postupem zjistíme, že $|A| = \sum_{\pi \in G}|P_{\pi}|$ .

A teď naopak probírejme prvky $X$ a pro každý určeme, kolik k němu můžeme přidat permutací $\pi$. Takto zjistíme, že $|A| = \sum_{x\in X} |St_x|$. Vzhledem k předchozímu lemmatu, části (2), je toto rovno $ \sum{O\in \mathscr{O}} |O_{x_O} | \cdot |St_{x_O} |$, kde $x_O$ je libovolný prvek $O$. Vzhledem k lemmatu, části (1), můžeme toto dále upravit na $\sum_{O\in \mathscr{O}} |G| = |\mathscr{O}| \cdot |G|$. Dohromady tedy dostáváme $|\mathscr{O}| \cdot |G| = \sum_{\pi\in G} |P_{\pi}|$, což jsme chtěli dokázat.

S náhrdelníkem můžeme provést celkem osm rotací $R_0, R_1, R_2, R_3, R_4, R_5, R_6, R_7$, přičemž $R_k$ je rotace o $k \cdot 45°$ ($360°/8=45°$ - pootočení o jeden drahokam).

Každé této rotaci odpovídá permutace na množině všech pevných náhrdelníků. Např. rotaci $R_1$ odpovídá permutace $\pi_1$, která každý pevný náhrdelník zobrazí na jiný pevný náhrdelník, oproti původnímu otočený o $45°$.

Nyní počet orbit, tj. $|\mathscr{O}|$, je hledaný počet různých náhrdelníků. Jedna orbita je totiž tvořena pevnými náhrdelníky, které jdou na sebe převést otočením a které tedy považujeme za jeden náhrdelník. Burnsideovo lemma nám říká, že tento počet můžeme zjistit tak, že pro $\pi_0, \ldots, \pi_7$ určíme počet pevných bodů a spočteme průměr.

$\pi_0$ je identita, má $|X| = 56$ pevných bodů, (je to počet různých pevných náhrdelníků). Snadno se rozmyslí, že ostatní permutace žádné pevné body nemají (pokud otočím jakkoli uspořádaný náhrdelník, nikdy jej nemohu otočit na stejně uspořádaný). Průměrný počet pevných bodů je tedy $$|\mathscr{O}|=\dfrac{1}{8} \cdot (56+0+0+0+0+0+0+0) = 7.$$ Hledaný počet náhrdelníků je tedy $7$.

Permutace v tomto případě představují $4$ rotace a $4$ osové souměrnosti.

Rotace o 0°, 90°, 180° a 270°, osové souměrnosti s osou horizontální($h$), vertikální($v$) a 2 diagonální osy($d_1$, $d_2$), viz obrázek:

Podle lemmatu dostáváme: $$ |\mathscr{O}| = \dfrac{1}{8}\cdot(|P_0| + |P_{90}| + |P_{180}| + |P_{270}| + |P_h| + |P_v| + |P_{d1}| + |P_{d2}|), $$

$P_0$ je identita a počet pevných bodů je roven počtu různých rozmístění 1 monomina, tj. $|P_0|=64$

V dalších otočeních $P_{90}, P_{180}$ a $P_{270} $ ať umístíme monomino kamkoli, po otočení se nikdy nedostane do stejné pozice, tedy počet pevných bodů je v těchto případech $0$.

V osových souměrnostech $P_h$ a $P_v$ také není žádný pevný bod.

Ovšem pro $P_{d1}$ a $P_{d2} $ máme vždy $8$ pevných bodů, jsou to právě ty, které leží na příslušné diagonále (po převrácení se pozice monomina nezmění).

Dosazením: $$ |\mathscr{O}| = \dfrac{1}{8}\cdot (64+0+0+0+0+0+8+8) = 10. $$

Všechny různé možnosti, kam můžeme monomino umístit, jsou znázorněné níže:

S náramkem můžeme provést celkem 15 rotací $R_0, \ldots, R_{14}$, přičemž $R_k$ je rotace o $k \cdot 24°$ ($360°/15=24°$ - pootočení o jednu korálku). A 15 překlopení kolem osy procházející středem náramku (kruhu) a některým z korálků. Při překlopení zůstává jeden korálek na místě a sedm dvojic korálků si vymění místa. Nemá-li tato výměna mít vliv na barevnost náramku, musí být každá z dvojic stejnobarevná, což však v našem případě není možné.

Podobnou úvahu lze ověřit pro neidentická otáčení. Barevnost, která se otočením nezmění, existuje jen pro otočení o $ 72°, 144°, 216°$ a $288°$. Přitom pro každé z uvedených otočení existuje právě šest takových rozmístění korálků, které i po otočení náramku, barevnost náramku nezmění = 6 pevných bodů (každé tři po sobě jdoucí korálky mají různou barvu).

Z Burnsideova lemmatu plyne, že hledaný počet náramků je roven: $$ |\mathscr{O}| = \dfrac{1}{30}\cdot (\dfrac{15!}{5!5!5!}+6+6+6+6) = 25226. $$

A) Permutace v tomto případě představují $4$ rotace (o 0°, 90°, 180° a 270°).

Rotace o $0°$ (identita) má tolik pevných bodů, kolik je různých rozmístění dvou monomin do tabulky 8x8. Těch je $\dfrac{64!}{2!62!}=2016$.

Rotace o $90°$ nemá žádný pevný bod (ať umístíme monomina kamkoli, po otočení nikdy nepřejdou ve stejné pozice).

V rotaci o $180°$ jsou ty pevné body, které odpovídají pozicím monomin, kdy jedno umístíme do levé poloviny a druhé do pravé poloviny tabulky tak, aby po otočení si pozice vyměnily. Přičemž do levé poloviny, do tabulky 8x4 máme $32$ možností, jak monomino umístit. Pozice druhého v pravé polovině je určena jednoznačně umístěním prvního.

Rotace o $270°$ nemá žádný pevný bod stejně tak jako rotace o $90°$.

Celkem různých způsobů, jak umístit dvě monomina do tabulky 8x8, kdy nerozlišujeme situace vzniklé jen pootočením, je: $$ |\mathscr{O}| = \dfrac{1}{4}\cdot(2016 + 32) = 512. $$

B) Permutace v tomto případě představují navíc oproti A) ještě $4$ osové souměrnosti (horizontální($h$), vertikální($v$) a 2 diagonální osy($d_1$, $d_2$).

Horizontální i vertikální osové souměrnosti mají stejný počet pevných bodů jako otočení o $180°$. Opět umístíme jedno monomino v jedné polovině a umístění druhého je jednoznačně určeno (po převrácení si monomina vymění pozice).

U diagonálních osových souměrností rozdělíme tabulku na diagonálou. Pokud umístíme jedno monomino na jedno z 28 políček nad diagonálou, umístění druhého je opět jednoznačně určené (tak, aby po překlopení si vyměnily místa), nebo můžeme obě monomina umístit kamkoli přímo na diagonálu, těchto možností je $\dfrac{8!}{2!6!}=28$. Celkem pevných bodů pro každou z diagonálních souměrností je $28+28=56$.

Celkem: $$ |\mathscr{O}| = \dfrac{1}{8}\cdot (2016+32+32+32+56+56) = 278. $$

Protože krychli můžeme položit na libovolnou z šesti stěn a čtyřmi způsoby ji otočit některou ze sousedních stěn dopředu, získáváme 24 různých permutací.

I) identita:
počet různých obarvení pevně postavené krychle dvěma barvami je $2^6=64$.

II) neidentické otáčení kolem osy procházející protějšími vrcholy:
(máme 4 dvojice protějších vrcholů a pro každou dvojici jsou dvě neidentická otočení - o $120°$ a o $240°$, celkem 8 neidentických otočení)
pevné body tvoří ta otočení, kdy tři stěny u vrcholu, kterým prochází osa otáčení, mají stejnou barvu. Takových různých obarvení krychle je $2^2=4$.

III) neidentické otáčení kolem osy procházející středy protějších hran:
(takových dvojic hran je 6 a pro každou dvojici je jediné otočení o $180°$, celkem 6 neidentických otočení)
pevné body tvoří ta otočení, kdy dvě stěny přiléhající k hranám, kterými prochází osa otáčení, mají stejnou barvu. I zbylá dvojice stěn musí mít stejnou barvu. Proto takových různých obarvení krychle je $2^3=8$.

IV) neidentické otáčení kolem osy procházející středy protějších stěn:
(máme 3 dvojice protějších stěn a pro každou dvojici tři neidentická otočení - o $90°$, o $180°$ a o $270°$, celkem 9 neidentických otočení)
v případě otočení o $90°$ a o $270°$ tvoří pevné body ta otočení, ve kterém všechny čtyři stěny, kterými neprochází osa, jsou obarveny stejnou barvou. Pro tato otočení (kterých je celkem 6) je $2^3=8$ různých obarvení. V případě otočení o $180°$ tvoří pevné body ta otočení, ve kterém jsou obě dvojice protějších stěn, kterými neprochází osa, obarveny stejnou barvou. Těchto různých obarvení je celkem $2^4=16$.

Popsali jsme $ 1+8+6+(6+3)=24 $ permutací. Podle lemmatu platí: $$ |\mathscr{O}| = \dfrac{1}{24}\cdot (64+8\cdot4+6\cdot8+6\cdot8+3\cdot16) = 10. $$

Permutace v tomto případě představují $4$ rotace a $4$ osové souměrnosti.

Rotace o 0°, 90°, 180° a 270°. Osové souměrnosti s osou horizontální($h$), vertikální($v$) a 2 diagonální osy($d_1$, $d_2$).

Rotace o $0°$ (identita) má $49$ pevných bodů.

Rotace o $90°$ má 1 pevný bod (umístění monomina na střed).

Stejně tak i rotace o $180°$ a o $270°$ mají každá $1$ pevný bod.

V osových souměrnostech je vždy $7$ pevných bodů (umístění monomina na jedno ze 7 políček na ose).

Stejně i na diagonálních souměrnostech je v každé $7$ pevných bodů.

Celkem: $$ \dfrac{1}{8}\cdot (49+1+1+1+7+7+7+7) = 10. $$

A) Permutace v tomto případě představují $4$ rotace (o 0°, 90°, 180° a 270°).

Rotace o $0°$ (identita) má $\dfrac{49!}{2!47!}=1176$ pevných bodů.

Rotace o $90°$ nemá žádný pevný bod.

V rotaci o $180°$ je 21 pevných bodů, kdy umístíme jedno monomino v levé polovině a druhé je opět jednoznačně určené. A 3 pevné body v situaci, kdy jedno monomino umístíme na prostřední sloupec na jedno ze 3 horních políček a druhé na jeho otočenou pozici. Celkem v této rotaci je $24$ pevných bodů.

Rotace o $270°$ nemá žádný pevný bod stejně tak jako rotace o $90°$.

Celkem různých způsobů, jak umístit dvě monomina do tabulky 7x7, kdy nerozlišujeme situace vzniklé jen pootočením, je: $$ |\mathscr{O}| = \dfrac{1}{4}\cdot(1176 + 24) = 300. $$

B) Permutace v tomto případě představují navíc oproti A) ještě $4$ osové souměrnosti (horizontální($h$), vertikální($v$) a 2 diagonální osy($d_1$, $d_2$).

Horizontální i vertikální osové souměrnosti mají 21 pevných bodů, kdy umístíme monomina v odpovídajících si políčkách v opačných polovinách. A $\dfrac{7!}{2!5!}=21$ pevných bodů, kdy jsou obě monomina na ose souměrnosti.

U diagonálních osových souměrností je situace velmi podobná jako u horizontální a vertikální souměrnosti. Pro každou diagonální souměrnost je $42$ pevných bodů.

Celkem: $$ \dfrac{1}{8}\cdot (1176+24+42+42+42+42) =171. $$

Uvažujeme 4 permutace ($4$ rotace):

A) $$ \dfrac{1}{4}\cdot (2^9+2^3+2^5+2^3) = 140 $$

B) $$ \dfrac{1}{4}\cdot (2^{16}+2^4+2^8+2^4) = 16456 $$

Uvažujeme 8 permutací ($4$ rotace a $4$ osové souměrnosti):

A) $$ \dfrac{1}{8}\cdot (2^9+2^3+2^5+2^3 +2^6+2^6+2^6+2^6 ) = 102 $$

B) $$ \dfrac{1}{8}\cdot \left(2^{16}+2^4+2^8+2^4 +2^8+2^8+2^{10}+2^{10} \right) = 8548 $$

4 permutace ($4$ rotace):

$$ \dfrac{1}{4}\cdot \left(\dfrac{9!}{3!3!3!}+0+0+0 \right) = 5040 $$

A) 6 pootočení: $$ \dfrac{1}{6}\cdot \left(\dfrac{6!}{2!4!}+0+0+3+0+0 \right) = 3 $$

B) 6 pootočení a 6 překlopení $$ \dfrac{1}{12}\cdot \left(\dfrac{6!}{2!4!}+0+0+3+0+0 +3+3+3 +3+3+3 \right) = 3 $$

A) 7 pootočení: $$ \dfrac{1}{7}\cdot \left(\dfrac{7!}{3!4!}+0+0+0 +0+0+0 \right) = 5 $$

B) 7 pootočení a 7 překlopení $$ \dfrac{1}{14}\cdot \left(\dfrac{7!}{3!4!}+0+0+0 +0+0+0 +3+3+3+ 3+3+3 +3 \right) = 4 $$

Poznámka: Všimněme si, že v tomto příkladě se 3 safíry a 4 rubíny je 5 různých náramků, pokud nerozlišujeme jen náramky vzniklé pootočením. Pokud navíc nerozlišujeme náramky vzniklé i překlopením, dostáváme 4 různé náramky. To znamená, že překlopením nám splynou 2 náramky, které jsme v možnosti za A) považovali za různé. Jsou to právě tyto dva:

A) $$ \dfrac{1}{10}\cdot \left(\dfrac{10!}{2!4!4!}+0+0+0+0+ 5 \cdot\dfrac{4!}{2!2!}+0+0+0+0\right) = 318 $$

B) $$ \dfrac{1}{20}\cdot \left[\dfrac{10!}{2!4!4!}+0+0+0+0+ 5 \cdot\dfrac{4!}{2!2!}+0+0+0+0 + 10 \cdot \left( 5 \cdot\dfrac{4!}{2!2!}\right)\right] = 174 $$

A) $$ \dfrac{1}{7}\cdot \left(\dfrac{7!}{2!2!3!} +0+0+0 +0+0+0\right) = 30 $$

B) $$ \dfrac{1}{14}\cdot \left[\dfrac{7!}{2!2!3!} +0+0+0 +0+0+0 + 7 \cdot \left( 3! \right)\right] = 18 $$

A) $$ \dfrac{1}{8}\cdot \left(\dfrac{8!}{2!3!3!} +0 +0+0+0 +0+0+0\right) = 70 $$

B) $$ \dfrac{1}{16}\cdot \left[\dfrac{8!}{2!3!3!} +0 +0+0+0 +0+0+0 + 4 \cdot 0 + 4 \cdot \left( 2 \cdot 3! \right) \right] = 38 $$