# 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 |