MATA140 Introduction to Discrete Mathematics (4 cr)

Combinatorics, linear recurrence relations, graph theory

The contents correspond to Anderson: A First Course in Discrete Mathematics, chapters 1-6.

After completing the course, the student

• can apply the basic principles of combinatorics, factorials, selections and repetitions, binomial coefficients and Pascal's triangle
• is familiar with the inclusion-exclusion principle and some of its applications
• knows how to calculate the number of partitions of a set and knows Stirling's numbers
• knows the basic properties of recurrence equations and knows some solution methods
• can model and solve combinatoric problems using linear recurrence equations
• knows graphs and the associated basic results, paths, trees, spanning trees, bipartiate graphs, and planar graphs
• knows Hamilton's graphs, the travelling salesman's problem, and Euler's graphs
• can model and solve combinatoric problems with graphs

Good command of the long mathematics curriculum of high school. Courses "How to prove it?" and "Introduction to mathematics" are useful.

Lecture notes (in Finnish)

Anderson: A First Course in Discrete Mathematics,

Springer & Biggs: Discrete Mathematics,

Matoušek & Nešetril: Invitation to Discrete Mathematics,

Hein: Discrete Mathematics