Kaisa_2012_3_photo by Veikko Somerpuro

ENUMERATIVE COMBINATORICS

This course introduces the basic mathematical methods for computing the sizes (= numbers of elements) of finite sets.

The course will cover the following material:

(1) Basic principles for computing the sizes of finite sets, such as the addition/multiplication principle and the inclusion-exclusion principle.
(2) Basic combinatorial objects like sequences, permutations, combinations, mappings, and how to count them.
(3) Generating functions, and how to use them to solve simple recursion relations.

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.

## Linxiao Chen

Published, 2.12.2019 at 14:00

Dear all,

The section "Conduct of the course" was updated for the exam, with the following new information:
-- The exam on 11 Dec will take place in room CK107 instead of the usual room C322 on Wednesdays.
-- No printed document is allowed during the exam. However you can bring one sheet of A4 (or similarly sized) paper of your own hand-written notes. Calculators are allowed, but will not be of much help.

Also, if you would like to take the second exam on 8 Jan (whether or not you take the first exam on 11 Dec), please send me an email. (You don't have to explain why you choose the second exam, just tell me about it.) Thank you.

Best regards,
Linxiao Chen

### Timetable

Here is the course’s teaching schedule. Check the description for possible other schedules.

DateTimeLocation
Mon 28.10.2019
14:15 - 15:45
Tue 29.10.2019
14:15 - 15:45
Wed 30.10.2019
14:15 - 15:45
Mon 4.11.2019
14:15 - 15:45
Tue 5.11.2019
14:15 - 15:45
Wed 6.11.2019
14:15 - 15:45
Mon 11.11.2019
14:15 - 15:45
Tue 12.11.2019
14:15 - 15:45
Wed 13.11.2019
14:15 - 15:45
Mon 18.11.2019
14:15 - 15:45
Tue 19.11.2019
14:15 - 15:45
Wed 20.11.2019
14:15 - 15:45
Mon 25.11.2019
14:15 - 15:45
Tue 26.11.2019
14:15 - 15:45
Wed 27.11.2019
14:15 - 15:45
Mon 2.12.2019
14:15 - 15:45
Tue 3.12.2019
14:15 - 15:45
Wed 4.12.2019
14:15 - 15:45
Mon 9.12.2019
14:15 - 15:45
Tue 10.12.2019
14:15 - 15:45
Wed 11.12.2019
14:15 - 15:45

### Material

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.

## Lecture material

• Linxiao Chen
• Linxiao Chen
• Linxiao Chen
Some typo in the original statements of the exercises are corrected in red.
• Linxiao Chen
• Linxiao Chen
• Linxiao Chen
• Linxiao Chen
• Linxiao Chen
• Linxiao Chen
• Linxiao Chen
• Linxiao Chen
Some typo in the original statements of the exercises are corrected in red.
• Linxiao Chen
• Linxiao Chen
• Linxiao Chen

### Conduct of the course

---------------- Schedule ----------------
3 classes per week on Mon - Wed @ 14:15 - 15:45,
Mon, room C123: Exercise class for the previous week's homework
Tue, room C122: Lecture 1 of the week
Wed, room C322: Lecture 2 of the week

Exceptions:
-- The first week will have 3 lectures.
-- The last week's 2 lectures will be replaced by a Q&A session (Tuesday) and the final exam (Wednesday). And the final exam will take place in room CK107 (larger room).

---------------- Homework ----------------
Exercise sheet will be posted on the course page following each Wednesday's lecture.
The exercises on the sheet will be discussed next Monday.

If you are unable to come, you can email your solutions to me. I will go through them and try to give some feedback, but will not be able to do so if I receive a large number of solutions.
Model solution will be posted on the course page following each Monday's exercise class. (So the solutions submitted by email should be sent before the exercise class.)

Some homework problems are designed to be a guided excursion on a topic not covered during the lectures. Don't worry if you cannot solve all of them.

---------------- Exam ----------------
The final exam is on 11 Dec 2019.
For those unavailable on 11 Dec, another exam will be organized on 08 Jan 2020 @ 10:00-13:00.
To retake it, tell me in advance and register to the MAT21018 Combinatorics General Examination at
https://courses.helsinki.fi/en/mat21018/130634388
If you are unavailable on both 11 Dec and 08 Jan, please write me an email to fix another date.

No printed document is allowed during the exam. However you can bring one sheet of A4 (or similarly sized) paper of your own hand-written notes. Calculators are allowed, but will not be of much help.

The final exam will be graded over 20 points.
Condition to pass: take the exam, and get at least X points.
(The value of X to be decided based on overall performance of the class, mostly likely X=2 or 3.)

Additional points can be earned by solving homework exercises.
The exercise sheets will come with stars after each problem. Solving that problem gives 0.2 point/star.
Those coming to the exercise class will fill a form to claim which problems they have solved, where "solving" means being able to present your solution on the blackboard when asked to do so.
Points will also be given to those submitting their solutions by email.

The grades 1~5 will be determined based on the total points Exam + Homework, so that about 10~30% of the students have each of the grades 1~5.

### 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],

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 thanks to its low amount of prerequisites. 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.

Lectures and exercise classes.

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.

Exam and excercises. 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.

Linxiao Chen