M8899 Combinatorics

Faculty of Science
Spring 2022
Extent and Intensity
2/2/0. 4 credit(s) (fasci plus compl plus > 4). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Jiří Kaďourek, CSc. (lecturer)
Guaranteed by
doc. RNDr. Jiří Kaďourek, CSc.
Department of Mathematics and Statistics – Departments – Faculty of Science
Supplier department: Department of Mathematics and Statistics – Departments – Faculty of Science
Timetable
Tue 16:00–17:50 M3,01023
  • Timetable of Seminar Groups:
M8899/01: Wed 12:00–13:50 M6,01011, J. Kaďourek
Prerequisites (in Czech)
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).
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives (in Czech)
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ů).
Learning outcomes (in Czech)
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.
Syllabus (in Czech)
  • 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í.
Literature
  • 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 pp. 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 and 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 pp. 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
Teaching methods (in Czech)
Přednáška doplněná cvičeními.
Assessment methods (in Czech)
Písemná zkouška ověřující teoretické znalosti i schopnost řešit konkrétní úlohy.
Language of instruction
Czech
Further Comments
The course is taught once in two years.
The course is also listed under the following terms Spring 2024.
  • Enrolment Statistics (Spring 2022, recent)
  • Permalink: https://is.muni.cz/course/sci/spring2022/M8899