MTH409: (Discrete Mathematics)

        [Cr:4, Lc:3, Tt:1, Lb:0]

Course Outline

• Combinatorics: Counting principles, Permutations, Combinations and the Binomial Theorem, Permutation groups and applications, generating functions, recurrence relations, Partition function, difference equations.
• Graph Theory: Basics of Graph Theory, Euler and Hamilton, Planar Graphs, isomorphism of graphs, matchings.
• Trees: spanning trees, counting trees, Binary trees, enumeration of trees, decision and search trees.
• Mod p-arithmetic: Chinese remainder theorem, Fermat’s little theorem, Euler’s totient function, Wilson’s theorem, quadratic residues.
• Arithmetic functions and multiplicative functions, Mobius inversion, Dirichlet convolution.

Additional Topics: Graph coloring and Ramsey theory, Algorithms in Graph Theory Problems, Design Theory: Latin Squares, Designs. Dirichlet series and Euler products, asymptotic behaviour of arithmetical functions.

Reference texts

1. J. Morris: Combinatorics.
2. D. Knuth: Concrete Mathematics.
3. John M. Harris, Jeffry L. Hirst, Michael J. Mossinghoff: Combinatorics and Graph Theory.
4. R. Diestel: Graph Theory.
5. Niven and Zuckerman: An introduction to the theory of numbers.
6. T. Apostol: Introduction to Number Theory