Course Co-ordinated by IISc Bangalore
 Coordinators IISc Bangalore

Untitled Document

This course covers the topics typically covered in a first level combinatorics course. It introduces the elementary notions in combinatorics and presents the most elementary techniques in combinatorics – pigeon hole principle, inclusion-exclusion principle, recurrence relations and generating functions.

 Module No. Topics 1. Pigeon hole Principle Pigeon hole principle - (Part 1) Pigeon hole principle - (Part 2) Pigeon hole principle - (Part 3) Pigeon hole principle - (Part 4) 2. Elementary Concepts Elementary concepts and basic counting principles Elementary concepts; Binomial theorem; Bijective proofs - Part (1) Bijective proofs – Part (2) Bijective proofs - Part (3); Properties of binomial coefficients; Combinatorial identities - Part (1) Combinatorial identities - Part (2); Permutations of multisets – Part (1) Permutations of multisets – Part (2) Multinomial Theorem, Combinations of Multisets – Part (1) Combinations of Multisets - Part (2) Combinations of Multisets – Part (3), Bounds for binomial coefficients Sterling’s Formula, Generalization of Binomial coefficients -  Part (1) Generalization of Binomial coefficients - Part (2) Generalization of Binomial coefficients - Part (3); Double counting - Part (1) 3. Some Techniques Double counting - Part (2) Hall’s Theorem for regular bipartite graphs; Inclusion exclusion principle - Part (1) Inclusion exclusion principle - Part (2) Inclusion exclusion principle - Part (3) Inclusion exclusion principle - Part (4) Inclusion exclusion principle - Part (5) 4. Recurrence relations and generating functions Recurrence Relations - Part (1) Recurrence Relations - Part (2) Recurrence Relations - Part (3) Recurrence Relations - Part (4) Recurrence Relations - Part (5) Generating functions - Part (1) Generating functions - Part (2) Solving recurrence relations using generating functions - Part (1) Solving recurrence relations using generating functions - Part (2) Exponential generating functions - Part (1) Exponential generating functions - Part (2), Partition Number - Part (1) 5. Special numbers Partition Number - Part (2) Partition Number - Part (3) Partition Number - Part (4); Catalan Numbers - Part (1) Catalans Numbers - Part (2) Catalan Numbers - Part (3), Sterling numbers of the 2nd kind Difference Sequences Sterling Numbers

Basic familiarity with sets relations, function, partial orders etc. is assumed.

• Discrete and Combinatorial mathematics – An applied introduction.
R.P. Grimaldi, B.V. Ramana
Pearson Education (2007)
• Introductory Combinatorics
Richard A Brnaldi
Pearson Education, Inc. (2004)
• Introduction to Enumerative Combinatorics
Miklos Bona
Mc Graw Hill (2007)
• A walk through Combinatorics – An introduction to enumeration and graph theory – Miklos Bona
World Scientific Publishing Co. Pvt. Ltd. (2006)
• A course in Combinatorics
J.H. Vanlint, R.M. Wilson
Cambridge University Press – (1992, 2001)
• External Combinatorics – With applications in computer science
Stasys Jukna
Springer-Verlag (2001)

The books given under references contain a lot more topics which the student may want to read.