Discrete Mathematics 2007

Debrup Chakraborty

We shall review some basic combinatorial objects and techniques to manipulate such objects in this course. No previous background would be assumed.

The course notes would be posted in this webpage as the course progress. The course notes would be sufficient for this course. There exist numerous nice books which covers the topics that would be discussed in this course. Some of them are:

1) A first Course in Combinatorial Mathematics by IAN ANDERSON

2) Introduction to Combinatorial Mathematics by C.L. LIU

3) Applied Combinatorics by FRED ROBERTS

4) Modern Graph Theory by BÉLA BOLLÓBAS

Class Schedule

We shall meet at 8:00 AM on Mondays and Wednesdays in the class room in the first floor.

Grading

50% on home work and 50% on two tests.

Tenatative topics to be covered

1) Preliminaries
a) Sets, Relations and Functions (notes)
b) Integers (notes)

c) Infinite Sets: An introduction (notes)

d) Mathematical Induction

2) Combinatorics
a) Basic Counting Techniques: Permutations and Combinations
b) Generating Functions
c) Recurrence Relations
d) Inclusion Exclusion Principle
e) Polya’s Theory

3) Graph Theory
a) Connectedness
b) Paths
c) Trees and Spanning Trees
d) Graph Coloring
e) Planer Graphs