2025/2026
Введение в перечислительную комбинаторику
Статус:
Маго-лего
Кто читает:
Факультет математики
Где читается:
Факультет математики
Когда читается:
1, 2 модуль
Онлайн-часы:
111
Охват аудитории:
для своего кампуса
Преподаватели:
Семенов Павел Владимирович
Язык:
английский
Кредиты:
6
Контактные часы:
8
Course Syllabus
Abstract
Enumerative combinatorics deals with finite sets and their cardinalities. In other words, a typical problem of enumerative combinatorics is to find the number of ways a certain pattern can be formed. In the first part of our course we will be dealing with elementary combinatorial objects and notions: permutations, combinations, compositions, Fibonacci and Catalan numbers etc. In the second part of the course we introduce the notion of generating functions and use it to study recurrence relations and partition numbers
Learning Objectives
- Learning objectives of Introduction to Enumerative Combinatorics: Master fundamental principles and techniques of counting discrete objects. Understand and apply concepts such as permutations, combinations, binomial coefficients, and generating functions. Solve problems related to enumeration of sequences, arrangements, and configurations. Develop analytical thinking and problem-solving skills within combinatorial contexts. Explore connections between combinatorics and other areas of mathematics, such as algebra and probability theory.
Expected Learning Outcomes
- The planned outcome of the lecture is to master basic combinatorial techniques for calculating the number of combinations of elements in a given set and understand the role of binomial coefficients in solving combinatorial problems, including a combinatorial proof of Fermat's Little Theorem.
- Planned outcomes include understanding advanced applications of binomial coefficients in multiselection problems and mastering the principle of inclusion-exclusion for computing sizes of unions and intersections, particularly in derangements.
- The planned learning outcome is to develop skills in solving linear recurrence relations using the Fibonacci sequence as a primary illustration.
- The intended learning outcome is to understand different definitions of Catalan numbers through geometric interpretations like polygon triangulations, Dyck paths, and binary trees, culminating in proving an explicit formula for these numbers.
- The expected learning outcome is to grasp the concept of generating functions, explore properties of formal power series, and utilize generating functions effectively to solve linear recurrence relations.
- The anticipated learning result is to deepen understanding of formal power series by proving a generalized binomial theorem applicable to any rational exponent, and applying it to derive the generating function for Catalan numbers.
- The intended learning outcome is to understand the concept of integer partitions, derive their generating function, and analyze its key properties, notably Euler’s celebrated Pentagonal theorem.
- The goal of this lecture is to explore the concept of "q-analogues," transforming numerical identities into polynomial identities involving a parameter q, thereby enriching combinatorial structures across diverse mathematical fields such as number theory and representation theory.
Course Contents
- Permutations and binomial coefficients
- Binomial coefficients, continued. Inclusion and exclusion formula
- Linear recurrences. The Fibonacci sequence
- A nonlinear recurrence: many faces of Catalan numbers
- Generating functions: a unified approach to combinatorial problems. Solving linear recurrences
- Generating functions, continued. Generating function of the Catalan sequence
- Partitions. Euler’s generating function for partitions and pentagonal formula
- Gaussian binomial coefficients. “Quantum” versions of combinatorial identities
Assessment Elements
- TestTesting within the course "Introduction to Enumerative Combinatorics" on the online platform SmartLMS is an essential component of the educational process aimed at assessing students' level of knowledge acquisition. Test assignments allow for evaluating the degree of understanding of the studied material, identifying gaps in knowledge, and determining areas requiring additional study.
- Final exam
