# Discrete mathematics 1

2019/2020
Programme:
Mathematics, First Cycle
Year:
2 year
Semester:
second
Kind:
mandatory
ECTS:
5
Language:
slovenian
Hours per week – 2. semester:
Lectures
2
Seminar
0
Tutorial
2
Lab
0
Content (Syllabus outline)

Basics of combinatorial counting:
Basic principles of counting. Binomial coefficients, set partitions, Stirling numbers of the first and second kind, Bell numbers, Lah numbers, partitions of an integer. Twelve-fold way. Inclusion-exclusion principle and rook polynomials. Recurrence equations, solutions via generating functions and, algebra of formal power series, Catalan numbers.
Basics of graph theory:
Basic definitions. Homomorphisms, isomorphisms and automorphisms of graphs. Connectivity. Trees and binary graphs. Closed walks and cycles. Eulerian circuit and Hamiltonian cycle. Planar graphs and Euler's formula. Vertex and edge colorings.

R. J. Wilson, J. J. Watkins: Uvod v teorijo grafov, DMFA-založništvo, Ljubljana, 1997.
J. H. van Lint, R. M. Wilson: A Course in Combinatorics, 2nd edition, Cambridge Univ. Press, Cambridge, 2001.
M. Juvan, P. Potočnik: Teorija grafov in kombinatorika, DMFA-založništvo, Ljubljana, 2000.
D. Veljan: Kombinatorna i diskretna matematika, Algoritam, Zagreb, 2001.

Objectives and competences

Students get familiar with elementary discrete structures, basic concepts from combinatorics and basic graph theory.

Intended learning outcomes

Knowledge and understanding: Knowledge about basic concepts from classical combinatorics and graph theory, and understanding of basic connections among them. Basic knowledge of exact enumeration of objects with specific properties.
Application: Use of discrete mathematical structures for representation of various objects and processes. Such representations play a key role in computerized data processing.
Reflection: Connection of theoretical knowledge with applications, for instance in solving optimization problems and in programming. Capability of recognizing problems that could be successfully described using discrete mathematical models.
Transferable skills: Knowledge of basic techniques for applications of discrete mathematical structures. Exactness in thinking and problem solving. Capability of reading and understanding specialized literature on discrete mathematics and related fields.

Learning and teaching methods

Lectures, exercises, homework, 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. Generalized Lucas cubes. Applicable analysis and discrete mathematics, ISSN 1452-8630, 2012, vol. 6, no. 1, str. 82-94. [COBISS-SI-ID 16242265]
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]