There are no prerequisites.
Combinatorics 2
2022/2023
Programme:
Computer Science and Mathematics, Second Cycle
Year:
1 ali 2 year
Semester:
first or second
Kind:
core mandatory
Group:
B
ECTS:
6
Language:
slovenian, english
Course director:
Hours per week – 1. or 2. semester:
Lectures
3
Seminar
0
Tutorial
2
Lab
0
Content (Syllabus outline)
Twelvefold way (binomial coefficients, Stirling numbers of the first and second kind, Lah numbers, partitions etc., using generating functions)
Ordinary and exponential generating functions: combinatorial meaning of sum, product, derivative, composition (exponential formula)
Formal power series, formal Laurent series, Lagrange inversion
Other applications of generating functions (computing the mean and variance, asymptotics of coefficients, etc.)
Pólya theory
Principle of inclusion and exclusion, incidence algebra, Möbius function, Möbius inversion
Reduced algebras, Dirichlet generating function
Instructor chooses an additional topic from the following list: polytopes, incidence structures, symmetric functions, discrete geometry, representations of the symmetric group
Readings
Richard P. Stanley: Enumerative Combinatorics, Vol. 1, Cambridge University Press, New York-Cambridge, 2011.
Richard P. Stanley: Enumerative Combinatorics, Vol. 2, Cambridge University Press, New York-Cambridge, 1999.
Francois Bergeron, Gilbert Labelle, Pierre Leroux: Combinatorial Species and Tree-like Structures, Cambridge University Press, Cambridge-New York-Melbourne, 1998.
Jack H. van Lint, Robin J. Wilson: A Course in Combinatorics, Cambridge University Press, Cambridge, 2001.
Objectives and competences
The student learns the main techniques of enumerative combinatorics.
Intended learning outcomes
Knowledge and understanding: Students understand the role of generating functions and algebraic structures in the study of combinatorial problems.Application: Students know how to use generating functions and algebraic structures to solve combinatorial problems.Reflection: The students learn the connection between the structure of the combinatorial problem and the algebraic nature of the corresponding generating functions and other structuresTransferable skills: Applications of generating functions in probability, a deeper understanding of the classical Möbius function, action of a group on a set.
Learning and teaching methods
lectures, exercises, homeworks, consultations
Assessment
2 midterm exams instead of written exam, written exam
Oral exam
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)
Lecturer's references
Sandi Klavžar:
ILIĆ, Aleksandar, KLAVŽAR, Sandi, RHO, Yoomi. The index of a binary word. Theoretical computer science, ISSN 0304-3975, 2012, vol. 452, str. 100-106. [COBISS-SI-ID 16340057]
KLAVŽAR, Sandi, SHPECTOROV, Sergey. Asymptotic number of isometric generalized Fibonacci cubes. European journal of combinatorics, ISSN 0195-6698, 2012, vol. 33, no. 2, str. 220-226. [COBISS-SI-ID 16055641]
FRONČEK, Dalibor, JEREBIC, Janja, KLAVŽAR, Sandi, KOVÁŘ, Petr. Strong isometric dimension, biclique coverings, and Sperner's theorem. Combinatorics, probability & computing, ISSN 0963-5483, 2007, vol. 16, iss. 2, str. 271-275. [COBISS-SI-ID 14286425]
Matjaž Konvalinka:
KONVALINKA, Matjaž, PAK, Igor. Triangulations of Cayley and Tutte polytopes. Advances in mathematics, ISSN 0001-8708, 2013, vol. 245, str. 1-33. [COBISS-SI-ID 16706905]
KONVALINKA, Matjaž. Skew quantum Murnaghan-Nakayama rule. Journal of algebraic combinatorics, ISSN 0925-9899, 2012, vol. 35, no. 4, str. 519-545. [COBISS-SI-ID 16250713]
KONVALINKA, Matjaž. Divisibility of generalized Catalan numbers. Journal of combinatorial theory. Series A, ISSN 0097-3165, 2007, vol. 114, iss. 6, str. 1089-1100. [COBISS-SI-ID 14354265]
