Syllabus  |   Lectures  |   Downloads  |   FAQ  |   Ask a question  |  
Course Co-ordinated by IISc Bangalore
Coordinators
 
Dr. L. Sunil Chandran
IISc Bangalore

 

Download Syllabus in PDF format



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

 

  1. Pigeon hole principle - (Part 1)

 

  1. Pigeon hole principle - (Part 2)

 

  1. Pigeon hole principle - (Part 3)

 

  1. Pigeon hole principle - (Part 4)

2.

Elementary Concepts

 

  1. Elementary concepts and basic counting principles

 

  1. Elementary concepts; Binomial theorem; Bijective proofs - Part (1)

 

  1. Bijective proofs – Part (2)

 

  1. Bijective proofs - Part (3); Properties of binomial coefficients; Combinatorial identities - Part (1)

 

  1. Combinatorial identities - Part (2); Permutations of multisets – Part (1)

 

  1. Permutations of multisets – Part (2)

 

  1. Multinomial Theorem, Combinations of Multisets – Part (1)

 

  1. Combinations of Multisets - Part (2)

 

  1. Combinations of Multisets – Part (3), Bounds for binomial coefficients

 

  1. Sterling’s Formula, Generalization of Binomial coefficients -  Part (1)

 

  1. Generalization of Binomial coefficients - Part (2)

 

  1. Generalization of Binomial coefficients - Part (3); Double counting - Part (1)

3.

Some Techniques

 

  1. Double counting - Part (2)

 

  1. Hall’s Theorem for regular bipartite graphs; Inclusion exclusion principle - Part (1)

 

  1. Inclusion exclusion principle - Part (2)

 

  1. Inclusion exclusion principle - Part (3)

 

  1. Inclusion exclusion principle - Part (4)

 

  1. Inclusion exclusion principle - Part (5)

4.

Recurrence relations and generating functions

 

  1. Recurrence Relations - Part (1)

 

  1. Recurrence Relations - Part (2)

 

  1. Recurrence Relations - Part (3)

 

  1. Recurrence Relations - Part (4)

 

  1. Recurrence Relations - Part (5)

 

  1. Generating functions - Part (1)

 

  1. Generating functions - Part (2)

 

  1. Solving recurrence relations using generating functions - Part (1)

 

  1. Solving recurrence relations using generating functions - Part (2)

 

  1. Exponential generating functions - Part (1)

 

  1. Exponential generating functions - Part (2), Partition Number - Part (1)

5.

Special numbers

 

  1. Partition Number - Part (2)

 

  1. Partition Number - Part (3)

 

  1. Partition Number - Part (4); Catalan Numbers - Part (1)

 

  1. Catalans Numbers - Part (2)

 

  1. Catalan Numbers - Part (3), Sterling numbers of the 2nd kind

 

  1. Difference Sequences

 

  1. 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.



Important: Please enable javascript in your browser and download Adobe Flash player to view this site
Site Maintained by Web Studio, IIT Madras. Contact Webmaster: nptel@iitm.ac.in