Obarvení rulety Mějme kolo rulety rozdělené do n sektorů. Každý z těchto sektorů obarvíme jednou barvou z celkového počtu k barev tak, aby žádné dva sousední sektory nebyly obarvené stejnou barvou. Klademe otázku, kolik obarvených kol takto může vzniknout, považujeme-li za stejná taková dvě obarvení, z nichž jedno vznikne z druhého nějakým pootočením rulety. Zjistěme nejprve, kolik takových obarvení můžeme dostat, není-li možné s ruletou otáčet. Pak můžeme sektory rulety očíslovat. První sektor můžeme obarvit kteroukoliv z daných k barev, to je tedy k možností. Je-li první sektor obarven, pak druhý sektor můžeme obarvit kteroukoliv z daných k barev odlišnou od té barvy, kterou je obarvený první sektor, to je tedy k — 1 možností, takže počet obarvení prvních dvou sektorů je k(k — 1). Jsou-li první dva sektory obarveny, pak třetí sektor můžeme obarvit kteroukoliv z daných k barev odlišnou od té barvy, kterou je obarvený druhý sektor, to je zase k — 1 možností. Je tedy počet obarvení prvních tří sektorů roven k(k — l)2. Takto by bylo možno pokračovat dále, takže by se mohlo zdát, že celkový počet obarvení všech n sektorů by byl roven k(k — l)"-1. Avšak nemáme přitom zajištěno, že poslední sektor bude obarvený barvou, která bude odlišná také od barvy prvního sektoru. Musíme tedy od nalezeného počtu odečíst počet všech obarvení našich n sektorů, která budou přípustná s tou jedinou výjimkou, že první a poslední sektor budou obarveny stejnou barvou. Můžeme si tak představit, že první a poslední sektor splynou do jediného sektoru. Vidíme tedy, že budeme muset odečíst počet všech přípustných obarvení rulety o n — 1 sektorech. Kdyby naše předchozí úvaha byla beze zbytku správná, bylo by těchto možných obarvení rulety o n — 1 sektorech celkem k(k — l)"-2, takže bychom dospěli k výslednému počtu k(k - I)"'1 - k(k - l)n~2. Avšak naše předchozí úvaha nebyla úplně správná, což vedlo k tomu, že jsme v našem posledním odpočtu odečetli také počet těch obarvení rulety o n — 1 sektorech, kdy první a poslední sektor byly obarveny stejnou barvou. Musíme tedy tento počet zase přičíst. Opět si můžeme představit stejně jako v předchozím kroku, že první a poslední sektor splynou do jediného sektoru. Budeme tedy muset přičíst počet všech přípustných obarvení rulety mající n — 2 sektorů. Kdyby naše prvotní úvaha byla zcela správná, bylo by těchto možných obarvení rulety o n — 2 sektorech celkem k(k — l)"-3, takže bychom celkem dospěli k výslednému počtu k(k - I)"'1 - k{k - iy~2 + k(k - I)""3. Avšak naše dřívější úvaha nebyla úplně správná, což teď vedlo k tomu, že jsme v našem posledním připočtu přičetli více obarvení, než by bylo třeba. Budeme tedy muset nějaká obarvení zase odečíst. Budeme-li takto postupovat dále, dospějeme posléze k počtu k(k-l) k(k - I)""2 + • • • + (-l)"-1/^ - l)2 + {-l)nk(k - 1). Dále už není potřeba nic přičítat ani odečítat, poněvadž poslední sčítanec k(k — 1) dává přesně počet všech obarvení rulety o dvou sektorech k barvami, kdy dotyčné dva sektory jsou obarvené různými barvami. Ještě posledně nalezené vyjádření hledaného počtu přípustných obarvení pevné rulety o n sektorech k barvami poněkud upravíme. Tento počet je roven Představíme-li si zde činitele k ve tvaru 1 + (k — 1) a roznásobíme-li tímto upraveným činitelem závorku vpravo, všechny sčítance s výjimkou prvního a posledního se odečtou, takže nakonec dospějeme k vyjádření Tolik je tedy celkem všech možných obarvení pevné rulety o n sektorech k barvami, nesmějí-li být sousední sektory obarveny stejnou barvou. Označme tento nalezený počet obarvení symbolem 7(17, k). k(k-i)((k-i) n-2 (k - I)""3 + • • • + {-l)n-\k - 1) + (-1)"). Ke každému takovému přípustnému obarvení pevné rulety uvažujme nejmenší kladné celé číslo d takové, že pootočením rulety o d sektorů přejde dotyčné obarvení samo na sebe. Takové kladné celé číslo d určitě existuje, v krajním případě jím může být samo číslo n. V obecném případě číslo d dělí číslo n. Kdyby tomu totiž tak nebylo, dospěli bychom ke sporu s minimalitou čísla d. Pak bychom totiž místo čísla d mohli vzít největšího společného dělitele čísel nad. To je vidět z toho, že podle Bezoutovy věty je onen největší společný dělitel nějakou celočíselnou lineární kombinací čísel nad. Kdyby pak d nedělilo n, byl by tento největší společný dělitel menší než samo číslo d. Takže opravdu d dělí n a dotyčné obarvení rulety se skládá z celkového počtu ^ stejně obarvených úseků délky d. Nazvěme takto určené číslo d periodou uvažovaného obarvení naší pevné rulety. Je jasné, že všechna obarvení, která vzniknou z tohoto výchozího obarvení nějakým pootočením rulety, pak mají tutéž periodu d, takže můžeme mluvit o periodách také u obarvení otočné rulety. Pro každé kladné celé číslo i označme symbolem k) počet všech těch přípustných vzájemně rozlišitelných obarvení otočné rulety o £ sektorech k barvami, která mají největší možnou periodu, to jest periodu £. Snadno lze nahlédnout, že pak pro každé kladné celé číslo d dělící číslo a? je počet všech přípustných vzájemně rozlišitelných obarvení otočné rulety o n sektorech k barvami s periodou d roven číslu £(c/, k). Úseky takového obarvení délky d pak totiž lze vnímat jako přípustná obarvení otočné rulety o d sektorech, která mají Za této situace číslo d^(d, k) udává počet všech přípustných obarvení pevné rulety o n sektorech k barvami s periodou d. Sumací těchto hodnot přes všechny dělitele d čísla n dostaneme počet všech možných přípustných obarvení pevné rulety o n sektorech k barvami, kterýžto počet jsme výše označili symbolem 7(a7, k). Dostáváme tak vztah 7(n, k) = y£fd£(d, /c), d\n který platí pro všechna kladná celá čísla n. Podle věty o Móbiových inverzních formulích pak platí rovněž vztah n£(n,/c) = X>(3)7((ib(c, /c) = EE >(£h(c *) c\d e\n c\^ Z dřívějších poznatků o Eulerově funkci ip však víme, že pro libovolné kladné celé číslo m platí ¥>M = 5>(f)/». Podle tohoto vztahu je ale poslední suma uvedená v závorkách na konci předchozího odvození rovna číslu ^(c)- Dostáváme tak rovnost ô(n,k)='-^(!1cHc>k)- c\n Konečně dosazením dříve vypočtených hodnot 7(0, k) do této rovnosti dostáváme výsledný vztah 5(n>k) = \ E ^X* -- i)c_1 +1-1)0) c\n pro počet všech možných přípustných vzájemně rozlišitelných obarvení otočné rulety o n sektorech k barvami.