M8899 Kombinatorika

Přírodovědecká fakulta
jaro 2022
Rozsah
2/2/0. 4 kr. (příf plus uk plus > 4). Ukončení: zk.
Vyučující
doc. RNDr. Jiří Kaďourek, CSc. (přednášející)
Garance
doc. RNDr. Jiří Kaďourek, CSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Dodavatelské pracoviště: Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Rozvrh
Út 16:00–17:50 M3,01023
  • Rozvrh seminárních/paralelních skupin:
M8899/01: St 12:00–13:50 M6,01011, J. Kaďourek
Předpoklady
Základy matematické analýzy (derivace, integrály, mocninné řady, lineární diferenciální rovnice), lineární algebry (vektorové prostory, báze, dimenze, soustavy lineárních rovnic) a algebry (grupy, okruhy, tělesa, polynomy).
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
Základy kombinatorické enumerace (Möbiovy inverzní formule, princip inkluze a exkluze), rekurentní formule (generující funkce, řešení lineárních rekurentních formulí) a Pólova enumerační teorie (Burnsideovo lemma, Pólyova-de Bruijnova věta, enumerace vzájemně neizomorfních stromů).
Výstupy z učení
Student bude po absolvování předmětu znát:
- abstraktní větu o Möbiových vzájemně inverzních formulích;
- obecný tvar principu inkluze a exkluze;
- teorii generujících funkcí posloupností reálných čísel;
- principy řešení lineárních rekurentních formulí s konstantními koeficienty;
- východiska obecné Pólyovy enumerační teorie;
- Pólyovu-de Bruijnovu větu a její aplikace;
- odvození rekurentní formule pro počet vzájemně neizomorfních stromů.
Student bude po absolvování předmětu schopen:
- řešit kombinatorické úlohy užitím principu inkluze a exkluze;
- řešit kombinatorické úlohy vedoucí na užití lineárních rekurentních formulí;
- řešit vybrané úlohy kombinatorické enumerace zvládnutelné užitím Pólyovy věty.
Osnova
  • Základní pojmy: variace, kombinace, binomická věta.
  • Stirlingova čísla 1. a 2. druhu: rekurentní formule, kombinatorický význam, Stirlingovy vzájemně inverzní formule.
  • Incidenční algebry částečně uspořádaných množin, Möbiovy funkce částečně uspořádaných množin.
  • Abstraktní věta o Möbiových vzájemně inverzních formulích.
  • Princip inkluze a exkluze: obecný tvar, užívané varianty, odvození pomocí věty o Möbiových vzájemně inverzních formulích.
  • Věta o Möbiových vzájemně inverzních formulích pro množinu všech přirozených čísel uspořádanou dělitelností.
  • Generující funkce a exponenciální generující funkce posloupností reálných čísel, Vandermondova konvoluční formule, Catalanova čísla.
  • Bellova čísla: rekurentní formule, exponenciální generující funkce pro posloupnost Bellových čísel, explicitní formule.
  • Úvod do diferenčního počtu: obyčejné diferenční rovnice, lineární diferenční rovnice, lineární rekurentní formule.
  • Řešení homogenních lineárních rekurentních formulí s konstantními koeficienty užitím generujících funkcí.
  • Řešení nehomogenních lineárních rekurentních formulí s konstantními koeficienty metodou variace konstant.
  • Obecná Pólyova enumerační teorie: Burnsideovo lemma, Pólyova-de Bruijnova věta.
  • Cyklové indexy permutačních grup, Pólyova věta pro libovolná zobrazení.
  • Generující řada cyklových indexů symetrických grup na konečných množinách.
  • Pólyova věta pro injektivní zobrazení.
  • Rekurentní formule pro počty vzájemně neizomorfních kořenových stromů s danými počty vrcholů prostřednictvím Pólyovy věty pro libovolná zobrazení.
  • Generující řada pro počty obyčejných vzájemně neizomorfních stromů s danými počty vrcholů prostřednictvím Pólyovy věty pro injektivní zobrazení.
Literatura
  • AIGNER, Martin. Combinatorial theory : reprint of the 1979 edition. New York: Springer, 1997, viii, 483. ISBN 3540617876. info
  • HALL, Marshall, Jr. Combinatorial theory. New York: John Wiley & Sons, 1986, 440 s. ISBN 0-471-09138-3. info
  • KAUCKÝ, Josef. Kombinatorické identity : úvod do studia metod kombinatorické analýzy. 1. vyd. Bratislava: VEDA, vydavateľstvo Slovenskej akadémie vied, 1975, 475 s. info
  • NEŠETŘIL, Jaroslav. Kombinatorika. Vyd. 1. Praha: Státní pedagogické nakladatelství, 1975, 160 s. URL info
  • SEKANINA, Milan a Anna SEKANINOVÁ. Vybrané kapitoly z kombinatoriky a teorie grafů. Vyd. 1. Brno: Rektorát UJEP, 1987, 51 s. info
  • STANLEY, Richard P. Enumerative combinatorics. Volume 1. Second edition. Cambridge: Cambridge University Press, 2012, 626 s. ISBN 978-1-107-60262-5. info
  • STANLEY, Richard P. Enumerative combinatorics. Volume 2. 1st pub. Cambridge: Cambridge University Press, 1999, xii, 581 s. ISBN 0-521-56096-12. info
Výukové metody
Přednáška doplněná cvičeními.
Metody hodnocení
Písemná zkouška ověřující teoretické znalosti i schopnost řešit konkrétní úlohy.
Další komentáře
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích jaro 2024.