Příklady na užití Burnsidova lemmatu v kombinatorice
Představme si, že máme n barev, kterými chceme obarvovat vrcholy šestiúhelníka. Ptáme se, kolik obarvení můžeme udělat. Dokud je šestiúhelník nehybný, je to snadné: r?6.
Ale co když chceme ztotožňovat ta obarvení, která na sebe přejdou při nějaké symetrii šestiúhelníka? To lze formulovat i jinak: máme dost korálků od každé z n barev, a děláme dětské náramky: navlékneme na nitku šest korálků a zavážeme. Kolik je takových náramků (poloha uzlíku není podstatná)?
Pro dvě barvy to lze provést probráním všech možností: 13.
Na řešení této úlohy lze užít Burnsidovo lemma: Hledaný počet získáme jako aritmetický průměr následujících čísel: pro každou symetrii spočítáme, kolik obarvení se touto symetrií nezmění.
Dostáváme ^(n6+2n + 2n2+4n3+3n4), pro n = 1 je to 1, pro n = 2 je to ^(64 + 4 + 8 + 32 + 48) = ^ = 13.
Příklad: barvíme stěny/hrany/vrcholy krychle n barvami
Kolika způsoby lze obarvit stěny (případně hrany či vrcholy) krychle n barvami, jestliže nerozlišujeme mezi obarveními, které na sebe přejdou nějakou rotací krychle?
Kolik má prvků grupa rotací krychle? Máme na mysli jen ty rotace, kdy krychle po rotaci zabírá stejný prostor jako před ní. To jsou tyto rotace:
► identita;
► rotace kolem osy procházející středy protějších stěn o 90°, 180°, 270°, celkem 3-3 = 9 rotací;
► rotace kolem osy procházející protějšími vrcholy o 120°, 240°, celkem 4-2 = 8 rotací;
► rotace kolem osy procházející středy protějších hran o 180°, celkem 6 rotací.
Máme dohromady 24 rotací. Jsou to všechny rotace krychle? Ano: je přece šest stěn, na kterých může krychle stát, a pro každou z nich čtyři stěny, kterými může být natočena směrem k nám.
Kolik krychlí vznikne obarvením stěn n barvami?
Barvíme stěny nehybné krychle. Ztotožňujeme ta obarvení, která na sebe přejdou nějakou rotací krychle. Podle Burnsidova lemmatu pro každou rotaci spočítáme, kolik obarvení se touto rotací nezmění, hledaný počet získáme jako aritmetický průměr těchto počtů.
► identita: r?6;
► rotace kolem osy procházející středy protějších stěn o 180°, celkem 3 rotace: 3r?4;
► rotace kolem osy procházející středy protějších stěn o 90° nebo 270°, celkem 3-2 = 6 rotací: 6r?3;
► rotace kolem osy procházející protějšími vrcholy o 120°, 240°, celkem 4-2 = 8 rotací: 8r?2;
► rotace kolem osy procházející středy protějších hran o 180°, celkem 6 rotací: 6r?3.
Hledaný počet krychlí je ^j(r?6 + 3r?4 + 12r?3 + 8r?2), pro n = 2 je to i(64 + 48 + 96 + 32) = ^ = 10 krychlí.
Kolik krychlí vznikne obarvením hran n barvami?
Barvíme hrany nehybné krychle. Ztotožňujeme ta obarvení, která na sebe přejdou nějakou rotací krychle. Opět pro každou rotaci spočítáme, kolik obarvení se touto rotací nezmění, hledaný počet získáme jako aritmetický průměr těchto počtů.
► identita: r?12;
► rotace kolem osy procházející středy protějších stěn o 180°, celkem 3 rotace: 3r?6;
► rotace kolem osy procházející středy protějších stěn o 90° nebo 270°, celkem 3-2 = 6 rotací: 6r?3;
► rotace kolem osy procházející protějšími vrcholy o 120°, 240°, celkem 4-2 = 8 rotací: 8r?4;
► rotace kolem osy procházející středy protějších hran o 180°, celkem 6 rotací: 6r?7.
Hledaný počet krychlí je ^(n12 + 6r?7 + 3r?6 + 8r?4 + 6r?3), pro n = 2 je to ^(4096 + 768 + 192 + 128 + 32) = 5§2 = 2i$ krychlí.
Kolik krychlí vznikne obarvením vrcholů n barvami?
Barvíme vrcholy nehybné krychle. Ztotožňujeme ta obarvení, která na sebe přejdou nějakou rotací krychle. Opět pro každou rotaci spočítáme, kolik obarvení se touto rotací nezmění, hledaný počet získáme jako aritmetický průměr těchto počtů.
► identita: r?8;
► rotace kolem osy procházející středy protějších stěn o 180°, celkem 3 rotace: 3r?4;
► rotace kolem osy procházející středy protějších stěn o 90° nebo 270°, celkem 3-2 = 6 rotací: 6r?2;
► rotace kolem osy procházející protějšími vrcholy o 120°, 240°, celkem 4-2 = 8 rotací: 8r?4;
► rotace kolem osy procházející středy protějších hran o 180°, celkem 6 rotací: 6r?4.
Hledaný počet krychlí je ^(ns + 17n4 + 6r?2), pro n = 2 je to ^(256 + 272 + 24) = ^ = 23 krychlí.