Combinatorial Counting - NDMI015

• Title: Kombinatorické počítání
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2018
• Semester: summer
• E-Credits: 3
• Hours per week, examination: summer s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Additional information: http://kam.mff.cuni.cz/~klazar/KPOC19.html
• Guarantor: doc. RNDr. Martin Klazar, Dr.
• Teacher(s): doc. RNDr. Martin Klazar, Dr.
• Class: Informatika Mgr. - Diskrétní modely a algoritmy
• Classification: Informatics > Discrete Mathematics

Annotation

English

Introduction to enumerative combinatorics. Basic techniques (ordinary and exponential generating functions, Lagrange inversion formula, bijective proofs) are explained on a number of concrete examples in which we shall count combinatorial structures of various kinds.

Last update: T_KAM (07.05.2001)

Czech

Kombinatorická enumerace se zabývá počítáním konečných kombinatorických struktur, např. stromů, grafů, posloupností, rozkladů čísel a mnoha dalších. Pracuje s metodami elementárními, jako je počítání bijekcemi, ale i méně elementárními (o to zajímavějšími), jako jsou generující funkce. Generující funkce jsou fascinující technikou, která se používá kromě kombinatoriky i při analýze algoritmů, v teorii pravděpodobnosti a v teorii čísel. V přednášce se podíváme na základní výsledky a postupy kombinatorické enumerace.

Last update: ()

Aim of the course

English

Students learn the fundamental technique of combinatorial enumeration, which are generating functions.

Last update: T_KAM (20.04.2008)

Czech

Studenti se seznámí se základní technikou kombinatorické enumerace, vytvořujícími funkcemi.

Last update: T_KAM (20.04.2008)

Course completion requirements

English

Oral exam, with written preparation. Exam question are/will be given on the course page,

see teacher's web page.

************************************************************************

As to situation caused by the current coronavirus pandemia in spring and summer 2020.

Form of exam (contact or distant) will be determined for each term in SIS

according to actual situation. Contact exam will be writen one with possible oral part.

For this course the contact form in small groups (<6, <11 people) appears probable.

Last update: Klazar Martin, doc. RNDr., Dr. (14.05.2020)

Czech

Zkouška je ústní, s písemnou přípravou. Konkrétní požadavky jsou/budou na stránce předmětu,

viz stránka vyučujícího.

************************************************************************

Aktualizace v souvislosti s koronavirovou pandemií a návaznými opatřeními na jaře

a v létě r. 2020. Forma zkoušky (kontaktní či distanční) bude určena pro každý

termín zvlášť podle aktuálních okolností, forma a průběh zkoušení bude stanovena při vypsání příslušného termínu v SISu.

Kontaktní zkouška bude písemná s možností ústního dozkoušení. U tohoto předmětu se nicméně jeví pravděpodobnou

kontaktní forma v malých skupinách (<6, <11 lidí?).

Last update: Klazar Martin, doc. RNDr., Dr. (30.04.2020)

Literature

English

R.P. Stanley: Enumerative combinatorics I, Wandswort & Brooks, 1986.

R.P. Stanley: Enumerative combinatorics II, Cambridge University Press, 1999.

Last update: T_KAM (20.04.2008)

Czech

R.P. Stanley: Enumerative combinatorics I, Wandswort & Brooks, 1986

R.P. Stanley: Enumerative combinatorics II, Cambridge University Press, 1999

Last update: Zakouřil Pavel, RNDr., Ph.D. (05.08.2002)

Requirements to the exam

English

Oral exam, with written preparation. Exam question are/will be given on the course page,

see teacher's web page.

************************************************************************

As to situation caused by the current coronavirus pandemia in spring and summer 2020.

Form of exam (contact or distant) will be determined for each term in SIS

according to actual situation. Contact exam will be writen one with possible oral part.

For this course the contact form in small groups (<6, <11 people) appears probable.

Last update: Klazar Martin, doc. RNDr., Dr. (14.05.2020)

Czech

Zkouška je ústní, s písemnou přípravou. Konkrétní požadavky jsou/budou na stránce předmětu,

viz stránka vyučujícího.

************************************************************************

Aktualizace v souvislosti s koronavirovou pandemií a návaznými opatřeními na jaře

a v létě r. 2020. Forma zkoušky (kontaktní či distanční) bude určena pro každý

termín zvlášť podle aktuálních okolností, forma a průběh zkoušení bude stanovena při vypsání příslušného termínu v SISu.

Kontaktní zkouška bude písemná s možností ústního dozkoušení. U tohoto předmětu se nicméně jeví pravděpodobnou

kontaktní forma v malých skupinách (<6, <11 lidí?).

Last update: Klazar Martin, doc. RNDr., Dr. (30.04.2020)

Syllabus

English

1. Problems of combinatorial enumeration. 2. Bijections. 3. Generating functions. 4. Exponential and composition formula. 5. Lagrange's inversion formula. 6. Asymptotic estimates.

Last update: T_KAM (20.04.2008)

Czech

1) Úlohy kombinatorické enumerce.

2) Bijekce.

3) Generující funkce.

4) Kompoziční a exponenciální formule.

5) Lagrangeova inverzní formule.

6) Asymptotika.

Last update: ()