DSM2 Cv 11
Pólyova věta Budeme se zabývat objekty (na množině X - to jsou „vrcholy“ těchto objektů) s různými prvky symetrie (například to mohou být různé brože, tisky, ale také strukturní vzorce různých chemických sloučenin). Příslušné symetrie popisují permutace na množině X, popisující, jak se v dané symetrii navzájem zobrazují jednotlivé vrcholy. Jednou z nich je určitě identita, dále platí, že popisuje-li nějakou symetrii objektu permutace π , popisuje jinou symetrii i permutace π −1 . Rovněž platí, že jsou-li π 1 , π 2 permutace, popisující nějaké symetrie, je i π 2 π 1 permutace, popisující nějakou symetrii. Tedy systém permutací, popisujících všechny symetrie objektu tvoří permutační grupu G . Tuto grupu popíšeme následujícím způsobem: - každé permutaci π přiřadíme její typ - [ p1 , p2 ,⋯, pn ] (kde pi udává počet cyklů v permutaci o velikosti právě i – známe z DSM1), - dále přiřadíme každé permutaci cyklový jednočlen proměnných c1 , c2 ,⋯, cn , který definujeme takto: cykl (π ) = c1p1 ⋅ c2p2 ⋅… ⋅ cnpn , - pro každou permutační grupu G definujeme její cyklový index jako mnohočlen proměnných c1 , c2 ,⋯, cn vztahem: 1 cykl ( G ) = ⋅ ∑ cykl (π ) . G π ∈G Do vrcholů těchto objektů budeme umisťovat různé předměty (budeme je vlastně obarvovat tolika barvami, kolik různých předmětů máme k dispozici, někdy to nemusí být „předměty“, ale např. perforace políček jízdenky děrovacím strojkem, atomy prvků nebo dokonce skutečné barvy). Připomínám, že obarvenou množinou rozumíme objekt O = X , β , kde β : X → B je zobrazení množiny X do množiny barev B, β ( x ) je barva prvku při obarvení β .
Pro „ztotožnění“ stejně „vypadajících“ obarvených objektů zavádíme pojem G ekvivalence – symbol ≡G . Platí: X , β1 ≡G X , β 2 ⇔ ∃π ∈ G : β 2 = β1 π . To znamená, že jeden obarvený objekt můžeme převést pomocí nějaké permutace z grupy G (symetrie objektu) na druhý. Takové obarvené objekty jsou pak mezi sebou nerozlišitelné. Je dána n – prvková množina X a množina barev B, na X existuje permutační grupa G. Na množině všech objektů O = X , β , kde β : X → B , určuje relace ≡G rozklad na rozkladové třídy navzájem G ekvivalentních objektů. Pokusíme se vnést do této problematiky účinný nástroj – vytvořující funkce. Nejprve přiřadíme každé barvě číselnou hodnotu. Zavedeme váhovou funkci. Váhová funkce na množině B je libovolné zobrazení w : B → Z 0 (každé barvě přiřadíme jednoznačně celé nezáporné číslo, obvykle co možná nejjednodušeji, tedy malá celá nezáporná čísla). Definujeme váhu obarvené množiny O = X , β předpisem w ( O ) = ∑ w ( β ( x ) ) . x∈X
Platí, že dvě G ekvivalentní obarvené množiny mají stejnou váhu. Všechny objekty v určité rozkladové třídě mají stejnou váhu.
Zavedení vytvořující funkce: Na množině barev B je definovaná váhová funkce w. Pro libovolné i ∈ Z 0 definujeme číslo wi = w−1 ( i ) (číslo udává počet barev, které mají přiřazenu váhu i ). Váhové funkci ∞
w pak přiřadíme váhovou vytvořující funkci
f w ( x ) = ∑ wi x i i =0
(koeficient u i – té mocniny proměnné x udává počet barev, které mají přiřazenu váhu i)
Je-li na systému obarvených množin definována ekvivalence ≡G , která vytváří rozklad množiny všech objektů na třídy ekvivalentních (z hlediska našeho problému „stejně vypadajících“ objektů), pak označíme symbolem ei počet tříd této ekvivalence, které mají váhu rovnou právě i . Pak platí Polyova věta:
e0 + e1 x + e2 x 2 + … + ek x k + … = cykl ( G ) ↓ f w ( x ) kde symbol ↓ znamená speciální substituci, kdy pro každé j = 1,⋯ , n nahradíme v cyklovém indexu cykl ( G ) všechny výskyty symbolu c j vytvořující funkcí f w ( x j ) , tedy nahradíme c1 → f w ( x ) ,
c2 → f w ( x 2 ) atd.
Příklad: Je dán obdélník, který má tyto symetrie: identitu, dvě osové souměrnosti podle středních příček a středovou souměrnost podle středu. Jeho vrcholy budeme obarvovat dvěma barvami – bílou a černou. Na tomto příkladu ukážeme použití Polyovy věty.
a) Určíme symetrie pomocí grupy permutací:
1 2 3 4 , 1 2 3 4 1 2 3 4 π4 = . 3 4 1 2
1 2 3 4
π1 =
π2 = , 2 1 4 3
1 2 3 4 , 4 3 2 1
π3 =
Typy permutací jsou postupně: [4,0,0,0], [0,2,0,0], [0,2,0,0], [0,2,0,0]. Cyklový index tedy je cykl ( G ) =
1 4 c1 + 3c22 ) . ( 4
Pro obarvení dvěma barvami zvolíme následující váhovou funkci: w ( b ) = 0, w ( c ) = 1 . Váhová
vytvořující
funkce
je
potom
( w0 = w−1 ( 0 ) = 1, w1 = w−1 (1) = 1).
fw ( x ) = 1 + x
Aplikací Polyovy věty dostaneme:
cykl ( G ) ↓ f w ( x ) =
(
)
1 4 2 2 1 + x + 3 1 + x = 1 + x + 3x 2 + x3 + x 4 . ( ) ( ) 4
Význam mnohočlenu: 1 - 1objekt s žádným černým vrcholem (všechny bílé), váha 0, x - 1 objekt s jedním černý a třemi bílými vrcholy, váha 1, 3x 2 - 3 objekty se dvěma bílými a dvěma černými vrcholy, váha 2, x3 - 1 objekt s třemi černými a jedním bílým vrcholem, váha 3, x 4 - jeden objekt s čtyřmi černými a žádným bílým vrcholem, váha 4. Celkový počet různých objektů je 7, což se součtu koeficientů nebo také hodnotě výsledné vytvořující funkce pro x = 1 .
Příklady: 1. Řešte předcházející příklad pro případ, kdy do vrcholů obdélníka vkládáme některou z mincí 1 Kč, 2 Kč, 5 Kč. 2. Je dáno těleso tvaru kolmého kvádru (jako krabička od sirek). Každou ze 6 stěn máme obarvit černě nebo bíle. Jako symetrie uvažujeme kromě identity jen otáčení o 1800 kolem tří os, kdy stejně velké stěny přejdou na sebe. Zjistěte počty různých obarvení. 3. Představte si univerzální lístek městské dopravy (příklad pochází ze starých časů, kdy se v MHD lístky „procvakávaly“ ve strojku) s 9 políčky. Při čtení označeného lístku (s procvaknutými políčky od počtu 0 až po 9) musí být možné vkládat lístek do čtečky z libovolné strany a také rubem či lícem. Kolika způsoby může být lístek označen 4 dírkami? 4. Zlatá brož tvaru podlouhlého obdélníka s 5 místy pro osazení polodrahokamy má kromě identity ještě jednu symetrii, a to otočení kolem středového místa o 1800 . Máme k dispozici 2 druhy polodrahokamů – smaragdy a rubíny. Kolik je možností osazení?
Vytvořující funkce více proměnných: Pokud máme daný základní objekt obarvit více než dvěma rozlišitelnými barvami, které ale jinak dávají stejný vnější efekt (kromě barvy) – například kdybychom v předchozím příkladu měli drahokamy tří druhů, ale stejného tvaru. Pak používáme vytvořující funkce více (q) proměnných, které vycházejí z vícerozměrné váhové funkce β : B → Z 0q = Z 0 × Z 0 × … × Z 0 , kde q je počet barev. Jedná se tedy o váhové vytvořující funkce f w ( x1 , x2 ,⋯ , xq ) .
Příklad: Zavedeme-li na našem obdélníku obarvení vrcholů třemi barvami bílou, černou a modrou, pracujeme s 3-rozměrnou váhovou funkcí w ( b ) = [1,0,0] , w ( c ) = [ 0,1,0] , w ( m ) = [ 0,0,1] ,
w[1,0,0] = w−1 [1, 0, 0] = 1,
w[0,1,0] = w−1 [ 0,1, 0] = 1,
w1 = w−1 [ 0, 0,1] = 1 .
Váhová vytvořující funkce je pak f w ( x, y, z ) = 1 ⋅ x1 y 0 z 0 + 1 ⋅ x 0 y1 z 0 + 1 ⋅ x 0 y 0 z1 = x + y + z . Zobecněná Polyova věta: Pro získání počtu rozkladových tříd ekvivalence, které mají příslušnou vícerozměrnou váhu, použijeme obdobně speciální substituci do cyklového indexu: cykl ( G ) ↓ f w ( x1 , x2 ,⋯, xq ) , kde ve speciální substituci ↓ nahradíme všechny výskyty symbolu c j vytvořující funkcí f w ( x1j , x2j ,⋯, xqj ) .
V našem
příkladu
(
pokračujeme
speciální
)
substitucí
2 1 4 Počet ( x + y + z ) + 3 ( x2 + y 2 + z 2 ) . 4 všech objektů, obarvených třemi barvami pak bude roven součtu koeficientů u mnohočlenu o třech proměnných, který získáme použitím multinomické věty, případně roznásobováním. Tento součet se ale rovná hodnotě příslušného mnohočlenu pro x = 1, y = 1, z = 1, 1 4 1 108 kterou získáme dosazením: 3 + 3 ⋅ 32 ) = ( 81 + 27 ) = = 27 . ( 4 4 4 Pokud chceme znát počty příslušných obarvených objektů, musíme roznásobit.
cykl ( G ) ↓ ( x + y + z ) =
5. Řešte příklad 4 pro 3 druhy polodrahokamů – rubín, smaragd, ametyst. 6. Kruhový koláč má tvarohovou náplň, kterou rozdělíme na tři stejné segmenty. Do každého dáme buď 2 rozinky nebo 2 mandle nebo 1 rozinku a 1 mandli. Kolik různých koláčů lze připravit?
7. Máme navrhnout brož tvaru rovnostranného trojúhelníka, který má být osazen třemi kameny, každý má být umístěn do vrcholu trojúhelníka. K dispozici máme čtyři polodrahokamy – rubíny, smaragdy, ametysty a akvamaríny. Kolik je různě vypadajících broží? Brož je možné v rovině pootáčet, ale nikoli v prostoru převracet, protože na zadní straně je špendlík. 8. Při chloraci benzenu vznikají jeho chlorderiváty s chemickým sumárním vzorcem C6 H p Clq , kde p + q = 6 . V prostoru tedy máme pravidelný šestiúhelník představující tzv. benzenové jádro, které obsahuje 6 atomů uhlíku. Do jeho vrcholů vkládáme atomy H nebo Cl . Určete, kolik je teoreticky možných sloučenin C6 H p Clq , kde p + q = 6 , s uvážením izomerie. Dále určete, kolik izomerů teoreticky existuje pro sumární vzorec C6 H 2Cl2 Br2 ? 9. Klenotník vyrobil symetrický šperk (viz obrázek),
který má 2 prvky symetrie (identitu a otočení o 1800 ). Má jej osadit na 6 místech polodrahokamy (rubíny, safíry, akvamaríny). Určete všechny možnosti osazení tohoto šperku. Kolik je možností, chceme-li použít 2 rubíny, 2 safíry a 2 akvamaríny?
10.V šestiranném revolveru lze do každého otvoru v bubínku vložit jeden náboj. Bubínek se volně otáčí. Do každého otvoru v bubínku můžeme vložit buď ostrý nebo slepý náboj nebo nic. Určete všechny možnosti osazení bubínku. Kolik je možností, máme k dispozici 2 ostré a 2 slepé náboje. 11. Určete počet možností, jak může vypadat čtvercová brož, která má být osazena čtyřmi kameny stejného tvaru (na výběr máme rubíny, smaragdy, ametysty a akvamaríny), které mají být umístěny v místech u vrcholů čtverce.
