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

2022/2023

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

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

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

Когда читается: 3, 4 модуль

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

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

Преподаватели: Ненашева Марина Сергеевна, Тиморин Владлен Анатольевич, Ферник Тома Клеман

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

Кредиты: 5

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

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

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

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

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

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

Дополнительное домашнее задание
отчетность за онлайн-курс
Контрольная работа
Экзамен

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

2022/2023 учебный год 4 модуль
Минимум из 10 и суммы баллов по формам контроля

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