Discrete Mathematics 3

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Mathematics

Synopsis:

The subject is devoted to elementary proofs of non-trivial combinatoriwal identities and to generating functions and their applications. In the seminar students present a problem with solution chosen from the given literature.

Requirements:

Knowledge of the first year Calculus (sequences and series, in particular power series) and Linear Algebra is required.

Syllabus of lectures:

1. Methods of combinatorial proof.

2. Stirling, Bernoulli, Catalan and Bell numbers.

3. Ordinary, exponential and Dirichlet generating functions. 4. Evaluation of sums, solution of linear and non-linear difference equations.

5. Combinatorial interpretation of product and composition of generating functions.

6. Applications in number theory and graph theory.

Syllabus of tutorials:

Study Objective:

Students learn methods of combinatorial proof, use of generating functions for solution of difference equations and for proving combinatorial identities. Students also learn comprehension of English written mathematical text and learn to present it to others.

Study materials:

M. Aigner, G. M. Ziegler, Proofs from the Book, Springer-Verlag 2004

A. T. Benjamin, J. J. Quinn, Proofs that Really Count, The Art of Combinatorial Proof, The Mathematical Association of America, 2003.

A. M. Yaglom, I. M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, Dover Publications, 1987.

H. Dörrie, 100 Great Problems of Elementary Mathematics, Dover Publications, 1965.

Kombinatorické počítání 1999 , KAM-DIMATIA Series preprint no. 451 (1999), 59 p

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: