Kaisa_2012_3_photo by Veikko Somerpuro

Enrol
9.12.2019 at 08:00 - 29.12.2019 at 23:59

Timetable

Description

This is an optional course.

Bachelor's Program in Mathematics and Statistics is responsible for the course.

The course is available to students from other degree programs.

Basic set theory, logic, and basic properties of functions.

All the prerequisites are covered by the course MAT11001: Johdatus yliopistomatematiikkaan (Introduction to University Mathematics).

(course page [https://courses.helsinki.fi/fi/mat11001/119967105],

lecture notes [https://courses.helsinki.fi/sites/default/files/course-material/4540840/...)

This course is about the basic mathematical methods of counting (=enumerative combinatorics). The goal is to:

(1) Understand basic principles for computing the sizes of finite sets, such as the addition/multiplication principle and the inclusion-exclusion principle.

(2) Understand basic combinatorial objects like sequences, permutations, combinations, mappings, and how to count them.

(3) Learn to use generating functions to solve simple recursion relations.

The course will be accessible to 1st year students. However it is recommended to 2nd or 3rd year students, because some practical experience in mathematics will be very helpful in following this course.

Term/teaching period when the course will be offered in the next academic years: varying.

Computing the size of a finite set is a fundamental problem in discrete mathematics, since knowing the number of elements in a finite set is usually the first step in understanding the structure of those elements.

The fundamental idea for computing the size of a set is to construct bijections. In this course, we will see how this idea gives rise to the basic principles of enumerative combinatorics such as the addition principle.

We then apply these tools to enumerate some of the most classical objects in combinatorics, such as sequences, permutations, combinations and mappings.

When counting more complicated objects, such as trees, the above method will give rise to recursion relations instead of explicit formulas. A very efficient tool for dealing with recursion relations is the generating function. The course introduce the generating functions, and show how to use them to solve simple linear and quadratic recursion relations.

Taking the final exam and completing weekly exercises.

Course material (lecture notes and exercises) will be uploaded to the course page as the course goes on.

Recommended reading material: Chapter 6 of "The art and craft of problem solving" (2017, 3rd Edition) by Paul Zeitz, and the first chapters of "Combinatorics: a guided tour" (2010) by David R. Mazur.

Lectures and weekly exercises.

Final exam and weekly exercises. The final exam will be graded with grades 1-5. Extra points can be earned by completing weekly exercises.

Taking the final exam and completing weekly exercises.