Discrete Mathematics
08 Aug -- 07 Dec 2023
Class Timings: Tuesday (11:30 to 13:00) and Friday (11:30 to 13:00)
Tentative Schedule
- Lecture 1--8: Introduction -- An Overview; Infinity of Primes. Pigeonhole Principle, Dirichlet's approximation, Monotone Sequences.
- Lecture 9: Generating functions, Stirling numbers of second kind, Bell numbers.Notes.
- Lecture 10: Theory of formal power series. Notes.
- Lecture 11: Unimodality I. Notes.
- Lecture 12,13, 14,15: Analytic aspects of power series. Notes.
- Lecture 16, 17: The Principle of Inclusion and Exclusion (PIE), Derangements, Eulers phi function. Notes
- Lecture 18: Mobius inversion on posets. Notes
- Lecture 19, 20: Two lectures on the polynomial method
- Lecture 21, 22: Unimodality II. Notes.
- Lecture 23, 24: Levy-Steinitz Theorem (including Steinitz Lemma) and Vector Balancing. Notes.
References
Books
- Peter Cameron: Combinatorics -- Topics, Techniques, Algorithms.
- J. Matousek and J. Nesetril: Invitation to Discrete Mathematics.
- J.H. van Lint and R.M. Wilson: Combinatorics.
- H. Wilf: Generatingfunctionology.
- M. Aigner and G.M. Ziegler: Proofs from THE BOOK.
- J. Matousek: Lectures in Discrete Geometry.
- Stanley: Enumerative combinatorics, both volumes
- Flajolet, Sdgewick: Analytic Combinatorics
Homework