De Bruijnova věta Nechť M je neprázdná konečná množina mající m prvků a nechť Y je neprázdná konečná množina mající r\ prvků. Prvky množiny Y nazýváme obrazci. Nechť dále /-/je podgrupa v grupě Sm všech permutací množiny M a nechť K je podgrupa v grupě Sy všech permutací množiny Y. Uvažujme množinu YM, to jest množinu všech zobrazení M —>* Y. Pro libovolnou permutaci a G H a pro libovolnou permutaci r E K uvažme zobrazení r6" : YM —>► VM definované pro každé zobrazení f : M ^ Y předpisem ra(f) = r o f o a. Snadno se přesvědčíme o tom, že pak zobrazení ra je permutací množiny YM. Poněvadž množina YM je nyní konečná, stačí ukázat například, že zobrazení ra je injektivní. Jsou-li f^g.M^Y dvě zobrazení taková, že platí ra(f) = ra(g), čili rofoa = rogoa1 pak odtud plyne, že r-1 o r o f o a o a-1 = r-1 o r o g o a o a-1, tedy že f = g. Je tedy zobrazení t° opravdu injektivní, a poněvadž je to zobrazení konečné množiny YM do ní samotné, musí to být permutace množiny YM. Označme symbolem KH množinu všech permutací tvaru ra pro libovolné permutace a G H a r G K. Ukážeme, že pak KH je podgrupou grupy SyM všech permutací množiny YM. Pro libovolné permutace ► Syw, kde Hop je duální grupa ke grupě H, dané pro každá a E H b r E K předpisem £(t, cr) = ra, je homomorfismem grupy K x /-/op do grupy Syw, přičemž obrazem £(/< x Hop) je právě množina permutací KH. Je tedy KH homomorfním obrazem grupy K x Hop, a proto je KH podgrupou grupy SyM. Můžeme tedy uvažovat o orbitách prvků z YM, což jsou zobrazení M ^ Y, v podgrupě KH. Tyto orbity nazýváme opět konfiguracemi. Buď dále T nějaká podmnožina množiny YM s následující vlastností. Pro každou permutaci a E H, pro každou permutaci r E K a pro každé zobrazení f z T také zobrazení r o f o a náleží do T\ O takové podmnožině T množiny YM budeme říkat, že je uzavřená vzhledem k podgrupám H a K. Je jasné, že pak taková podmnožina J-*je sjednocením několika konfigurací, to jest několika orbit prvků z YM v podgrupě KH. Zúžení permutací tvaru ra z KH na podmnožinu ^jsou potom permutacemi této podmnožiny T. Můžeme tedy po tomto zúžení vnímat podgrupu KH jako podgrupu grupy Sjr všech permutací podmnožiny T množiny YM. Ještě podotkněme, že ve speciálním případě, kdy podgrupa K bude triviální grupou pozůstávající pouze z identické permutace množiny Y, přejde nynější situace přímo do situace popsané v paragrafu věnovaném Pólyově enumerační teorii (s konečnou množinou Y). Naše nynější podgrupa KH se pak stane podgrupou EH, kterou jsme studovali v onom paragrafu. 2/16 Směřujeme k definici odpovídajícího enumerátoru podmnožiny T. Viděli jsme v minulém paragrafu, že je vhodné v tomto kontextu uvažovat o rozkladech tt množiny obrazců Y, které jsou kompatibilní s nějakou permutací r této množiny Y. Nyní máme k dispozici celou podgrupu K grupy Sy všech permutací množiny Y. V nynější situaci budeme tedy žádat, aby rozklad tv množiny Y byl kompatibilní se všemi permutacemi r G K. Mezi všemi rozklady tt s touto vlastností existuje jeden, který je ze všech takových rozkladů ten nejjemnější. Očividně tímto nejjemnějším rozkladem kompatibilním se všemi permutacemi r G K je rozklad, jehož třídami jsou všechny orbity prvků p G Y v grupě K. Budeme dále předpokládat, že tt je právě tímto nejjemnějším rozkladem. Podobně jako v minulém paragrafu každé třídě C rozkladu tt, to jest každé orbitě C v grupě K, přiřadíme proměnnou xq- Každému zobrazení f G T pak přiřadíme člen, to jest součin proměnných, označený v7r(f) a definovaný následovně: vÁf)= II xin*)]*- Připomeňme jenom, že pro každý obrazec p G Y značíme symbolem [p]tt třídu rozkladu tt obsahující prvek p, to jest orbitu prvku p v grupě K. 3/16 Ukážeme, že jsou-li f,g G T dvě zobrazení náležející do téže orbity podgrupy K , to jest platí-li g = r o f o a pro nějaké permutace a G H a r G K\ pak členy v^íO a ^(g) Jsou s' rovny. Skutečně pak vychází vAs) = v^{r o f oa) = JJ X[r(/r(f7(a)))]7r = JJ x[r(/r(a))]7r = JJ X[f(a)]7r = vv(Oj aGM aGM a£M neboť a je permutací množiny M a rozklad 7r je kompatibilní s permutací r. Můžeme tedy pro každou orbitu O v podgrupě KH korektně definovat jí odpovídající člen v^(0) jako člen v7r(f), kde /"je některý (kterýkoliv) prvek orbity O. Označme ještě %JIj?,h,k množinu všech konfigurací, to jest množinu všech orbit prvků podmnožiny T v podgrupě KH. Pak definujeme již avizovaný enumerátor 77r(J7, A7, /<) následovně: *yir(F,H,K) = ^ ^(0). Poněvadž obě množiny M i V jsou nyní konečné, je konečná i množina %JIf,h,k všech konfigurací, takže výše uvedená suma bude obsahovat jenom konečný počet sčítanců. Má tedy smysl se ptát na počet zmíněných konfigurací. Tento počet dostaneme dosazením hodnoty 1 za všechny proměnné do enumerátoru. Poznamenejme už jen, že ve speciálním případě, kdy podgrupa K je triviální grupou pozůstávající pouze z identické permutace množiny Y, nejjemnějším rozkladem tv množiny Y kompatibilním s identickou permutací je triviální rozklad množiny Y na jednoprvkové třídy. V takovém případě je výše definovaný enumerátor 77r(J7, A7, K) identický s enumerátorem 7(J-*, H), který byl studován v paragrafu věnovaném Pólyově enumerační teorii. Abychom mohli dokázat avizovanou de Bruijnovu větu, budeme vedle právě zavedených pojmů a konstrukcí potřebovat také pojmy a konstrukce, které byly zavedeny v paragrafu o Pólyově enumerační teorii. Každá podmnožina T množiny YM, která je uzavřená vzhledem k podgrupám H a K, je jistě uzavřená vzhledem k podgrupě H v dřívějším smyslu. Vedle podgrupy KH grupy Sjr budeme pracovat také s dřívější podgrupou EH grupy Sjr. Budeme tedy uvažovat o orbitách prvků z7v podgrupě KH, ale také o orbitách těchto prvků v podgrupě EH. Je jasné, že každá orbita některého prvku z T v podgrupě EH je celá obsažena v nějaké orbitě tohoto prvku v podgrupě KH. To znamená, že každá orbita v podgrupě KH je sjednocením několika orbit v podgrupě EH. Pro každou orbitu Q v podgrupě EH označme symbolem KQ orbitu v podgrupě KH, jejíž je orbita Q podmnožinou. Podotkněme, že KQ = {rof:rEK1fE Q}. Dále pro každou orbitu O v podgrupě KH označme symbolem &(0) množinu všech těch orbit v grupě EH, jejichž sjednocením je orbita O. Jinými slovy, &(0) je rozklad orbity O na orbity v grupě EH. Při tomto označení jsme schopni zformulovat a dokázat následující výsledek. Lemma. Pro libovolnou orbitu Q v podgrupě EH platí rovnost &(KQ)\ = K\ {u e K : uQ = Q} Důkaz Buď tedy Q nějaká orbita v podgrupě EH. Uvažme orbitu KQ v podgrupě KH, jejíž je orbita Q součástí. Uvažme dále všechny orbity v podgrupě EH, jejichž sjednocením je orbita KQ. Označili jsme symbolem Q5(KQ) množinu všech těchto orbit. Poněvadž KQje orbita v podgrupě KH, pro každý prvek f G KQ a pro každou permutaci r G K je také r o f prvkem orbity KQ. Navíc pro danou permutaci r G K je přiřazení f i—>> r o f permutací prvků orbity KQ. Tato permutace indukuje permutaci na množině orbit &(KQ). Tato indukovaná permutace je dána předpisem 1Z i—^ tIZ pro každou orbitu 1Z v grupě EH obsaženou v orbitě KQ, kde tTZ = {r o g : g e 71}. Grupa permutací K tak dává vzniknout indukované grupě permutací na množině orbit &(KQ). Tato indukovaná grupa permutací má očividně jen jednu orbitu, jíž je množina &(KQ) sama. Jednou z orbit v množině &(KQ) je pak i výchozí orbita Q. Zkoumejme, pro které dvojice permutací r, r' E K zobrazí jim příslušné indukované permutace množiny &(KQ) tuto orbitu Q stejně. To nastane právě tehdy, když platí tQ = r'Q. K tomu ale dojde právě tehdy, když je splněno t_1(t/ô) = q, to jest právě když permutace r-1 o r' leží v podgrupě {ej E K : cjQ = Q} grupy K. To ale nastane právě tehdy, když permutace r, r' určují tutéž levou třídu grupy K podle její podgrupy {uj E K : cjQ = Q}. Celkem tedy odpovídají jednotlivé orbity z množiny ©(KQ) vzájemně jednoznačně levým třídám grupy K podle její podgrupy G K : cjQ = Q}. Počet orbit v množině &(KQ) je tedy roven podílu počtů prvků v grupě K a v její podgrupě {oj E K : ujQ = Q}. To je ale právě dokazované tvrzení. □ Připomeňme, že pro libovolnou podmnožinu T množiny YM uzavřenou vzhledem k podgrupě H a pro libovolnou permutaci r množiny Y jsme v minulém paragrafu označili symbolem TT podmnožinu množiny T pozůstávající ze všech těch zobrazení f E J7, pro něž platí r(fH) = fH, a ukázali jsme, že tato podmnožina TT je rovněž uzavřená vzhledem k podgrupě H. To znamená, že pro každé zobrazení f E TT je celá orbita fH prvku f v podgrupě EH obsažena v podmnožině TT. Je tedy podmnožina TT sjednocením celých orbit fH některých zobrazení f : M —>► Y v podgrupě EH, a sice těch zobrazení f E T, pro něž platí r(fH) = fH. Jinak to lze vyjádřit tak, že podmnožina TT je sjednocením těch orbit Q prvků z T v podgrupě EH, pro něž platí tQ = Q. Ještě jinak řečeno to znamená, že množina orbit 9JIjtt,h se skládá z těch orbit Q množiny OJtjr h, které splňují podmínku r Q = Q. Nyní jsme připraveni formulovat a dokázat následující de Bruijnovu větu, která je ústředním výsledkem tohoto paragrafu. Pro enumerátor 77r(J7, A7, K) platí Druhá z výše uvedených dvou rovností plyne okamžitě z vyjádření enumerátoru 77r(J7r, /-/), které jsme získali v první větě předchozího paragrafu. Zbývá tedy dokázat první z uvedených dvou rovností. Podle definice enumerátoru 77r(Jr, A7, K) máme ___ >yn{TiHiK) = ^ ^(0). Každá orbita O G TIj^h^k, to jest každá orbita O prvků z T v podgrupě KH je sjednocením těch orbit Q prvků z Jv podgrupě EH, které jsou obsaženy v orbitě O. To jsou ale právě ty orbity Q v podgrupě E , které tvoří rozklad &(0) orbity O na orbity v podgrupě EH. Poněvadž O je orbitou prvků z T v podgrupě KH, máme pro ni už definován člen v^(0). Z definice tohoto člene ale plyne, že je tento člen roven dříve definovanému členu vn(Q) pro každou orbitu Q v podgrupě EH, která je obsažena v orbitě O. Počet těchto orbit Q je roven počtu tříd v rozkladu &(0) a pro každou tuto orbitu její příslušný člen v7T(Q) roven členu vn(0). Navíc pro každou takovou orbitu Q platí vztah O = KQ, takže na místě rozkladu &(0) máme co do činění s rozkladem Q5(KQ). Z těchto úvah plyne rovnost Dosazením za \&(KQ)\ do tohoto vztahu z předchozího lemmatu obdržíme rovnost Odtud a z předchozí rovnosti pak plyne vztah neboli H, K) = K ujQ=Q anebo ještě jinak Vzhledem k úvahám předcházejícím této větě je možno tuto formuli ještě převést do tvaru Vzhledem k definici enumerátoru 7^(7-*^, H) z předchozího paragrafu odtud ale plyne vztah To je ale rovnost, kterou ještě zbývalo dokázat. □ Pokud jde o počet konfigurací v množině 97tjr h,k, jak již bylo výše řečeno, tento počet dostaneme, když do enumerátoru 77r(j7, H, K) dosadíme hodnotu 1 za všechny proměnné. Takto z předcházející de Bruijnovy věty odvodíme tento její bezprostřední důsledek. Důsledek. Počet všech konfigurací, to jest počet všech orbit prvků z T v podgrupě KH je roven 1 \%Rt,H,K H • K \{f E J7 :rof = f oa}\. □ Tento důsledek je přímým zobecněním posledního důsledku uvedeného v paragrafu věnovaném Pólyově enumerační teorii. Věnujme se nyní speciálnímu případu, kdy podmnožinou T množiny YM je celá tato množina YM. Všimněme si blíže rozkladu tv množiny Y na orbity prvků p G Y v grupě K. Vezměme libovolnou permutaci r množiny Y z podgrupy K. Poněvadž tato permutace r je kompatibilní s rozkladem tv množiny Y, lze uvažovat o zúženích permutace r na jednotlivé orbity C v grupě K. Tato zúžení t|c jsou sama o sobě permutacemi dotyčných orbit. Původní permutace r množiny Y je pak rovna součinu permutací r\c přes všechny orbity C v grupě K, to jest přes všechny třídy C rozkladu tt. V takovém případě máme následující výsledek formulovaný s pomocí cyklového indexu Z(H) permutační grupy H. Vystupují v něm také parametry z typů yi{r\c)2h{r\c) rqjv^lc) zúžení r|c permutací r z podgrupy K na jednotlivé třídy C rozkladu 7r. Enumerator ^(Y1^, H, K) je dán formulí ln(YM, H,K) = ^-Y1 Z{H- Ai(r), A2(r),..., Am(r)) /cc/e pro každé í = 1, 2,..., m je W = ^(1>(t|c))*£ cgtt Důkaz. Toto tvrzení plyne přímo z první rovnosti uvedené v de Bruijnově větě pro případ, kdy podmnožinou T je celá množina YM, a z druhé věty v předchozím paragrafu, kde je uvedeno, jak vypadá enumerator 77r(VrM, H) pro libovolnou permutaci r množiny V. □ Z této poslední věty bezprostředně plyne tento její následující důsledek. Připomeňme v této souvislosti ještě jednou, že počet konfigurací v množině TImyhk, to jest počet všech orbit prvků množiny MY v podgrupě KH obdržíme, když dosadíme hodnotu 1 za všechny proměnné do enumerátoru 77r(VM, /-/, K). Důsledel Počet konfigurací v množině 9JImy,h,k Je dán rovností my,h,k kde pro každé í = 1,2,..., m je \\t □ Jako příklad užití tohoto důsledku řešme následující úlohu. Mějme kolo rulety rozdělené do n sektorů. Dále mějme paletu barev kruhového tvaru, po jejímž obvodu je umístěno k barev. Každý sektor rulety obarvíme jednou barvou z naší palety. Klademe otázku, kolika způsoby můžeme sektory rulety obarvit, považujeme-li za stejná taková obarvení, z nichž jedno vznikne z druhého nějakým pootočením rulety, a považujeme-li za stejná také taková obarvení, z nichž jedno vznikne z druhého cyklickou záměnou barev danou nějakým pootočením kruhové palety. Podobně jako v dřívějších úlohách o obarvení sektorů rulety, i zde množinou M bude množina všech sektorů rulety a množinou Y bude množina všech barev na paletě. Podmnožinou T množiny YM bude nyní celá množina YM. Podgrupou H grupy Sm všech permutací množiny M bude grupa všech otočení rulety. Pak H bude cyklická grupa řádu n na množině M, kterou jsme dříve značili symbolem Cm- Podgrupou K grupy Sy všech permutací množiny Y bude grupa všech otočení kruhové palety. Pak K bude cyklická grupa řádu k na množině Y, kterou jsme dříve značili symbolem Cy. K těmto podgrupám Cm a Cy vezměme jim odpovídající podgrupu CyM grupy Sym všech permutací množiny YM. Pak orbity prvků z YM v podgrupě CyM budou odpovídat obarvením sektorů rulety, když na ně pohlížíme tak, jak je to specifikováno v zadání úlohy. Směřujeme k aplikaci předchozího důsledku. Grupou H tedy bude cyklická grupa Cm řády n. Grupou K bude cyklická grupa Cy řádu k. Zajímají nás jednotlivé permutace r z grupy K, to jest z grupy Cy. Grupa Cy je generována jedním cyklem ů délky k. Odpovídá to pootočení palety barev o jednu barvu. Pak jednotlivé permutace z grupy Cy lze vypsat jako mocniny permutace ů, to jest jako permutace $2,..., ůk, kde ůk je identická permutace na množině Y. Všimněme si podrobněji permutace ůy pro některý exponent v = 1, 2,..., k. Buď v, vy i v y lvi1, I v' I / r"v I v /f r"»v v v ' ■ I f Iv/ v-v' I k nejvetsi společný dělitel cisel v a k. Polozme e = Pri reseni jedné z dřívějších úloh jsme odvodili, že pak permutace ůy je součinem k nezávislých cyklů délky e. Zajímají nás dále hodnoty ni(ůu), kde í = 1, 2,..., a?, pro naši permutaci i?1'. Jestliže pak = sk = k. Jestliže ale e)(£, pak = 0. Vypočteme nyní sčítance Z(Cm\ ^(t?^), • • • 3 Mní^)) odpovídajícího naší permutaci i?1'. Tento sčítanec je roven Z(Cm\ 0,..., 0, /c, 0,..., 0, /c,...). £-1 £-1 Viděli jsme dříve, že cyklový index Z(Cm) grupy C/w je roven a7 z—' Do tohoto cyklového indexu nyní dosazujeme právě nalezené hodnoty ^(ů") za proměnné td pro všechna d\n. Taková hodnota je nenulová a je rovna k právě tehdy, když e\d. Jestliže tedy £)(n, pak iid{^u) = 0 pro všechna d\n, takže v tom případě máme Z{CM; /iiOH, MiT), ..., //„(i?")) = 0. Jestliže ale e\n, pak hodnoty ^d($u) jsou nenulové a jsou rovny k pro ty dělitele d\n, které splňují