# Class materials

All references are taken from the course book:
מתמטיקה בדידה, של ליניאל/פרנס.

 Num. Topic Reference Date 1 Introduction, the sum and product principles Chap. 4.1 2 The pigeon-hole principle Chap. 4.5 3 Basic counting, choosing k out of n elements Chap. 4.2 4 The binomial coefficients Chap. 4.3 5 Combinatorial identities, Catalan numbers Chap. 4.3 6 The multinomial coefficients Chap. 4.7 7 The inclusion-exclusion principle Chap. 4.6 8 Applications of the inclusion-exclusion principle: disorders, Euler's function Chap. 4.6 9 Counting via recurrence relations Chap. 4.4 10 Solving linear homogeneous recurrence relations Chap. 6.1 11 More linear recurrences Chap. 6.2 12 Introduction to graph theory Chap. 5 13 Basic properties of graphs Chap. 5.1 14 Graph families, trees Chap. 5.2 15 Bipartite graphs, planar graphs Chap. 5.2 16 Graph coloring Chap. 5.5 17 Paths in graphs: Euler tour Chap. 5.3 18 Hamiltonian paths Chap. 5.3 19 Extremal graph theory: Ramsey, Mantel Chap. 5.7 20 Counting trees Chap. 5.6 21 Matchings in graphs, Hall's theorem Chap. 5.4 22 Introduction to discrete probability Chap. 8.1 23 Independence, conditional probability Chap. 8.2 24 Random variables, expectation, distributions Chap. 8.3 25 Variance and tail bounds Chap. 8.5,8.7 26 The probabilistic method Chap. 8.8