Kombinatorika 2

2021/2022
Program:
Interdisciplinarni magistrski študijski program 2. stopnje Računalništvo in matematika
Letnik:
1 ali 2 letnik
Semester:
prvi ali drugi
Vrsta:
temeljni izbirni
Skupina:
B
ECTS:
6
Jezik:
slovenski, angleški
Izvajalec (kontaktna oseba):
Ure na teden – 1. ali 2. semester:
Predavanja
3
Seminar
0
Vaje
2
Laboratorij
0
Vsebina

Dvanajstera pot (binomski koeficienti, Stirlingova števila 1. in 2. vrste, Lahova števila, razčlenitve ..., z rodovnimi funkcijami)
Običajne in eksponentne rodovne funkcije: kombinatorični pomen operacij vsote, produkta, odvoda, kompozicije (eksponentna formula)
Formalne potenčne in Laurentove vrste, Lagrangeeva inverzija
Druge uporabe rodovnih funkcij (računanje povprečij in varianc, asimptotika koeficientov ...)
Pólyeva teorija
Načelo vključitev in izključitev, incidenčna algebra, Möbiusova funkcija, Möbiusova inverzija
Reducirane algebre, Dirichletova rodovna funkcija
Predavatelj izbere še eno izmed naslednjih tem: politopi, incidenčne strukture, simetrične funkcije, diskretna geometrija, upodobitve simetrične grupe

Temeljni literatura in viri

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.

Cilji in kompetence

Študent spozna glavne tehnike kombinatornega preštevanja.

Predvideni študijski rezultati

Znanje in razumevanje: Študentje poznajo in razumejo vlogo rodovnih funkcij in algebrskih struktur pri študiranju kombinatornih problemov.
Uporaba: Študentje znajo uporabljati teorijo rodovnih funkcij in algebrskih struktur za reševanje kombinatornih problemov.Refleksija: Študentje spoznajo povezavo med strukturo kombinatornega problema in algebraično naravo pripadajočih rodovnih funkcij oziroma drugih struktur.Prenosljive spretnosti – niso vezane le na en predmet: Uporaba rodovnih funkcij v verjetnosti, poglobljeno razumevanje klasične Möbiusove funkcije, delovanje grup na množici.

Metode poučevanja in učenja

predavanja, vaje, domače naloge, konzultacije

Načini ocenjevanja

Izpit iz vaj (2 kolokvija ali pisni izpit)
Ustni izpit
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)

Reference nosilca

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]