2024/2025
Введение в перечислительную комбинаторику
Статус:
Майнор
Кто читает:
Факультет математики
Онлайн-часы:
40
Охват аудитории:
для всех кампусов НИУ ВШЭ
Язык:
русский
Кредиты:
5
Программа дисциплины
Аннотация
Перечислительная комбинаторика имеет дело с конечными множествами и их мощностями. Другими словами, типичная проблема перечислительной комбинаторики состоит в том, чтобы найти сколькими способами можно составить ту или иную структуру определенного образца. В первой части нашего курса мы будем иметь дело с элементарными комбинаторными объектами и понятиями: перестановками, сочетаниями, разложениями, числами Фибоначчи и Каталана и т.д. Во второй части курса мы введем понятие производящих функций и используем его для изучения рекуррентных соотношений и числа разбиений.
Цель освоения дисциплины
- Целями освоения дисциплины «Перечислительная комбинаторика» являются: знакомство с основными концепциями, используемыми в современных комбинаторике и дискретной математике (перестановки, сочетания, разложения), знакомство с техникой производящих функций.
Планируемые результаты обучения
- Владеть техникой работы с производящими функциями.
- Знать основные типы перечислительных задач и базовые инструменты для их решения.
- Понимать основные идеи работы с перестановками, сочетаниями, разбиениями, производящими функциями
- Уметь формализовать возникающие на практике перечислительные задачи.
Содержание учебной дисциплины
- Перестановки и биномиальные коэффициенты. Треугольник Паскаля.
- Формула включения-исключения. Целочисленные разложения.
- Линейные рекуррентные соотношения, последовательность Фибоначчи.
- Примеры нелинейных рекуррент: многогранные числа Каталана.
- Производящие функции. Решение линейных рекуррентных соотношений при помощи производящих функций.
- Производящая функция для чисел Каталана.
- Разбиения. Производящая функция Эйлера для числа разбиений, теорема Эйлера о пятиугольных числах.
- Гауссовы биномиальные коэффициенты, «квантовые» аналоги комбинаторных соотношений.
Список литературы
Рекомендуемая основная литература
- Клековкин Г.А. - Введение в перечислительную комбинаторику: учебное пособие - Издательство "Лань" - 2019 - ISBN: 978-5-8114-4386-4 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/119290
Рекомендуемая дополнительная литература
- Львовский, С. М. Работа в системе LaTeX : учебное пособие / С. М. Львовский. — 2-е изд. — Москва : ИНТУИТ, 2016. — 534 с. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100443 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.