# Class materials

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

Num. |
Topic |
Reference |
Date |

1 | Introduction, the sum and product principles | Chap. 4.1 | 24/02/19 |

2 | The pigeon-hole principle | Chap. 4.5 | 25/02/19 |

3 | Basic counting, choosing k out of n elements | Chap. 4.2 | 03/03/19 |

4 | The binomial coefficients | Chap. 4.3 | 04/03/19 |

5 | Combinatorial identities, Catalan numbers | Chap. 4.3 | 10/03/19 |

6 | The multinomial coefficients | Chap. 4.7 | 11/03/19 |

7 | The inclusion-exclusion principle | Chap. 4.6 | 17/03/19 |

8 | Applications of the inclusion-exclusion principle: disorders, Euler's function | Chap. 4.6 | 24/03/19 |

9 | Counting via recurrence relations | Chap. 4.4 | 25/03/19 |

10 | Solving linear homogeneous recurrence relations | Chap. 6.1 | 31/03/19 |

11 | More linear recurrences | Chap. 6.2 | 01/04/19 |

12 | Introduction to graph theory | Chap. 5 | 07/04/19 |

13 | Basic properties of graphs | Chap. 5.1 | 08/04/19 |

14 | Graph families, trees | Chap. 5.2 | 28/04/19 |

15 | Bipartite graphs, planar graphs | Chap. 5.2 | 29/04/19 |

16 | Graph coloring | Chap. 5.5 | 12/05/19 |

17 | Paths in graphs: Euler tour | Chap. 5.3 | 13/05/19 |

18 | Hamiltonian paths | Chap. 5.3 | 19/05/19 |

19 | Extremal graph theory: Ramsey, Mantel | Chap. 5.7 | 20/05/19 |

20 | Counting trees | Chap. 5.6 | 26/05/19 |

21 | Matchings in graphs, Hall's theorem | Chap. 5.4 | 27/05/19 |

22 | Introduction to discrete probability | Chap. 8.1 | 02/06/19 |

23 | Independence, conditional probability | Chap. 8.2 | 03/06/19 |

24 | Random variables, expectation, distributions | Chap. 8.3 | 10/06/19 |

25 | Variance and tail bounds | Chap. 8.5,8.7 | 16/06/19 |

26 | The probabilistic method | Chap. 8.8 | 17/06/19 |