Введение в перечислительную комбинаторику

2026/2027

ID 1106600

Статус: Майнор

Кто читает: Факультет математики

Где читается: Факультет математики

Онлайн-часы: 40

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Бычков Борис Сергеевич

Язык: русский

Кредиты: 5

Контактные часы: 40

Дополнительные материалы в LMS Задать вопрос

Аннотация

Перечислительная комбинаторика имеет дело с конечными множествами и их мощностями. Другими словами, типичная проблема перечислительной комбинаторики состоит в том, чтобы найти сколькими способами можно составить ту или иную структуру определенного образца. В первой части нашего курса мы будем иметь дело с элементарными комбинаторными объектами и понятиями: перестановками, сочетаниями, разложениями, числами Фибоначчи и Каталана и т.д. Во второй части курса мы введем понятие производящих функций и используем его для изучения рекуррентных соотношений и числа разбиений.

Цель освоения дисциплины

Целями освоения дисциплины «Перечислительная комбинаторика» являются: знакомство с основными концепциями, используемыми в современных комбинаторике и дискретной математике (перестановки, сочетания, разложения), знакомство с техникой производящих функций.

Планируемые результаты обучения

Владеть техникой работы с производящими функциями.
Знать основные типы перечислительных задач и базовые инструменты для их решения.
Понимать основные идеи работы с перестановками, сочетаниями, разбиениями, производящими функциями
Уметь формализовать возникающие на практике перечислительные задачи.

Содержание учебной дисциплины

Перестановки и биномиальные коэффициенты. Треугольник Паскаля.
Формула включения-исключения. Целочисленные разложения.
Линейные рекуррентные соотношения, последовательность Фибоначчи.
Примеры нелинейных рекуррент: многогранные числа Каталана.
Производящие функции. Решение линейных рекуррентных соотношений при помощи производящих функций.
Производящая функция для чисел Каталана.
Разбиения. Производящая функция Эйлера для числа разбиений, теорема Эйлера о пятиугольных числах.
Гауссовы биномиальные коэффициенты, «квантовые» аналоги комбинаторных соотношений.

Элементы контроля

Final exam
Test
Testing 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.

Промежуточная аттестация

2026/2027 4th module
0.5 * Test + 0.5 * Final exam

Программа дисциплины