Канунников Андрей Леонидович
«Производящие функции, теория Пойа, диаграммы Юнга»
Описание курса:
Это вводный курс по перечислительной комбинаторике. Имеет небольшие пересечения с обязательными курсами алгебры и теории чисел, расширяя и углубляя их. Не пересекается по содержанию с другими, более специальными комбинаторными курсами, читавшимися на факультете. Спецкурс рассчитан на студентов, владеющих алгеброй и теорией чисел в объёме первых трёх семестров мехмата (большинство тем доступно первокурсникам).
В курсе мы познакомим слушателей с основными алгебраическими методами решения задач перечислительной комбинаторики. Современная алгебраическая комбинаторика имеет множество ответвлений со своими методами и приложениями в математике и естествознании. Задачи о подсчёте числа элементов возникают в теории вероятностей, графов, булевых функций, лингвистике, химии, биологии и др.
Значительная часть времени отводится на разбор примеров и задач. Первая часть курса посвящена классическим комбинаторным числам и тождествам, их комбинаторным интерпретациям. Такие интерпретации ("биективные" доказательства) известных формул открывают их новое видение, дают толчок для интересных обобщений и регулярно публикуются. Особенно подробно мы рассматриваем числа разбиений (диаграмм Юнга). Они обладают замечательными свойствами и широкой сферой применения. В обязательном курсе с помощью разбиений классифицируются конечные примарные абелевы группы, нильпотентные жордановы формы и классы сопряжённости симметрической группы (этим объясняется их важность в теории представлений симметрической группы). Во второй части изучается один из основных инструментов перечислительной комбинаторики - производящие функции. Числа, которые требуется вычислить в комбинаторной задаче, в переводе на алгебраический язык становятся коэффициентами рядов, что позволяет также применять и аналитические методы. Зачастую, особенно когда нет удовлетворительной формулы для самой последовательности, её удаётся исследовать с помощью производящей функции, устроенной несложно (основной пример - числа разбиений). В третьей части мы излагаем перечислительную теорию Пойа, предмет которой - подсчёт элементов с точностью до некоторого отношения эквивалентности. В частном случае действия группы на множестве получается более простая лемма Бернсайда о числе орбит, кратко затрагиваемая в основном курсе алгебры. Последняя часть курса посвящена задачам о покрытии доски (прямоугольной, треугольной, гексогональной) фигурками заданного типа. Один тип задач - доказать, что покрытие невозможно. В кружковой математике для этого часто применяются те или иные трюки, например, удачно подобранная раскраска или расстановка чисел. Алгебра даёт два более стандартных метода с помощью перевода задачи на язык многочленов (принадлежность многочлена идеалу, базисы Грёбнера) или теории групп (вывод одних групповых соотношений из других, диаграммы Ван Кампена). Мы не ставим задачу подробно рассказать о базисах Грёбнера или диаграммах Ван Кампена, а хотим познакомить и заинтересовать слушателей на примерах их применения. Другой тип задач (формально более общий) - найти число покрытий. На примере покрытий прямоугольника доминошками мы проиллюстрируем технику определителей и перманентов.
План курса:
