Kombinatorika

Osnovna načela preštevanja. Binomski koeficienti, razdelitve, Stirlingova števila 1. in 2. vrste, Bellova števila, Lahova števila, razčlenitve naravnega števila. Dvanajstera pot. Načelo vključitev in izključitev in trdnjavski polinomi. Polyeva teorija: delovanje grupe na množici, Burnsidova lema, število orbit. Rodovne funkcije in uporaba pri rekurzivnih enačbah. Catalanova števila. Delno urejene množice in mreže: verige in antiverige, Dilworthov izrek, Spernerjev izrek. Teorija načrtov: načrti, t-načrti, ciklične konstrukcije načrtov.

Miklos Bona, A Walk Through Combinatorics, 2nd ed. World Scientific, New York, 2006.
N. Biggs, Discrete Mathematics, 2nd ed., Oxford Univerisity Press (2002)
M. Juvan, P. Potočnik: Teorija grafov in kombinatorika, DMFA-založništvo, Ljubljana, 2000.
Primož Potočnik, Zapiski predavanj iz Diskretne matematike I, http://www.fmf.uni-lj.si/~potocnik/Ucbeniki/DM-Zapiski2010.pdf

Študent se spozna z nekaterimi klasičnimi problemi kombinatorike in se jih nauči samostojno reševati.

Znanje in razumevanje: Poznavanje osnovnih pojmov iz klasične kombinatorike ter razumevanje osnovnih povezav med njimi. Osnovno znanje natančnega štetja objektov z določenimi lastnostmi iz dane množice.
Uporaba: Uporaba diskretnih matematičnih struktur za predstavitev različnih objektov in procesov. Tovrstne predstavitve so nepogrešljive na primer pri obdelavi podatkov z računalniki.
Refleksija: Povezovanje teoretičnih spoznanj s praktičnimi uporabami na primer v optimizaciji in pri programiranju. Sposobnost prepoznavanja problemov, ki jih lahko uspešno opišemo z diskretnimi matematičnimi modeli.
Prenosljive spretnosti – niso vezane le na en predmet: Poznavanje osnovnih prijemov za delo z diskretnimi matematičnimi strukturami. Natančnost pri razmišljanju in reševanju problemov. Sposobnost prebiranja strokovne literature iz diskretne matematike in sorodnih področij.

Predavanja in vaje.

Pisni in ustni izpit

Sandi Klavžar:
BREŠAR, Boštjan, KLAVŽAR, Sandi, RALL, Douglas. Domination game and an imagination strategy. SIAM journal on discrete mathematics, ISSN 0895-4801, 2010, vol. 24, no. 3, str. 979-991. [COBISS-SI-ID 15648089]
HAMMACK, Richard H., IMRICH, Wilfried, KLAVŽAR, Sandi. Handbook of product graphs, (Discrete mathematics and its applications). Boca Raton, London, New York: CRC Press, cop. 2011. XVIII, 518 str., ilustr. ISBN 978-1-4398-1304-1. [COBISS-SI-ID 15916121]
IMRICH, Wilfried, KLAVŽAR, Sandi, RALL, Douglas F. Topics in graph theory : graphs and their Cartesian product. Wellesley (Mass.): A. K. Peters, 2008. XIV, 205 str., ilustr. ISBN 978-1-56881-429-2. [COBISS-SI-ID 14965081]
Matjaž Konvalinka:
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ž, PAK, Igor. Geometry and complexity of O'Hara's algorithm. Advances in applied mathematics, ISSN 0196-8858, 2009, vol. 42, iss. 2, str. 157-175. [COBISS-SI-ID 15545945]
KONVALINKA, Matjaž. On quantum immanants and the cycle basis of the quantum permutation space. Annals of combinatorics, ISSN 0218-0006, 2012, vol. 16, no. 2, str. 289-304. [COBISS-SI-ID 16310873]
Primož Potočnik:
POTOČNIK, Primož. Tetravalent arc-transitive locally-Klein graphs with long consistent cycles. European journal of combinatorics, ISSN 0195-6698, 2014, vol. 36, str. 270-281. [COBISS-SI-ID 16862041]
POTOČNIK, Primož, SPIGA, Pablo, VERRET, Gabriel. Cubic vertex-transitive graphs on up to 1280 vertices. Journal of symbolic computation, ISSN 0747-7171, 2013, vol. 50, str. 465-477. [COBISS-SI-ID 16520537]
POTOČNIK, Primož. Edge-colourings of cubic graphs admitting a solvable vertex-transitive group of automorphisms. Journal of combinatorial theory. Series B, ISSN 0095-8956, 2004, vol. 91, no. 2, str. 289-300. [COBISS-SI-ID 13087321]