PřF:M8899 Kombinatorika - Informace o předmětu
M8899 Kombinatorika
Přírodovědecká fakultajaro 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:
- 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
- Matematika (program PřF, N-MAT)
- 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.
- Statistika zápisu (jaro 2022, nejnovější)
- Permalink: https://is.muni.cz/predmet/sci/jaro2022/M8899