С.В.Дужин

Комбинаторика

Спецкурс предназначен для студентов 2-3 курса.

До недавних пор считалось, что комбинаторика представляет собой нестройное
собрание красивых разрозненных трюков. Первую серьезную попытку заложить
основы комбинаторики как науки недавно предприняли Бержерон, Лабелл и Леру в
книге "Комбинаторные виды и древообразные структуры". Книга посвящена
последовательному построению комбинаторики на основе понятия вида, который
ввел Андре Жуайяль (A.Joyal). На первый взгляд, понятие комбинаторного вида
кажется бессодержательным; однако, листая страница за страницей
книгу трех авторов, просто диву даешься, как из ничего, буквально из пустоты
возникают содержательные и красивые комбинаторные конструкции и факты,
например разнообразные комбинаторные тождества, формула обращения Лагранжа,
теория перечисления Пойа и т.п. Я предполагаю ознакомить слушателей с
началами теории видов и рассмотреть с этой точки зрения некоторое множество
разрозненных фактов классической комбинаторики.

Примерная программа курса

  1. Последовательности и производящие функции
        o решение линейных рекуррентных соотношений
        o числа Фибоначчи, Каталана, Эйлера, Бернулли
        o алгебра формальных степенных рядов
        o асимптотика коэффициентов
  2. Введение в теорию видов
        o определение, примеры
        o ряды, связанные с видом: производящий, 
          экспоненциальный, цикловой
        o операции над видами
        o молекулярные и атомарные виды
        o формула обращения Лагранжа
  3. Теория перечисления
        o лемма Бернсайда
        o формула Пойа
        o перечисление деревьев
        o плетизмы и функции Шура
  4. Теория разбиений
        o диаграммы Юнга
        o пентагональная теорема Эйлера
        o соответствия Глэшера и Сильвестра
        o асимптотика Харди-Рамануджана
        o соответствие Робинсона-Шенстеда-Кнута
  5. Частично упорядоченные множества
        o алгебра Мебиуса
        o функция Мебиуса
        o формула обращения Мебиуса

Литература

   F.Bergeron, G.Labelle, P.Leroux "Th\'{e}orie des esp\`{e}ces et
combinatoire des structures arborescentes", Montr\'{e}al, 1994 
(англ. перевод: "Combinatorial Species and Tree-like Structures", 
Cambridge University Press, 1998).

   P.Cameron. Combinatorics. Cambridge, 1994.

   Р.Стенли. Перечислительная комбинаторика. Изд. Мир.

   С.К.Ландо. Комбинаторика. Изд. МЦНМУ, 1994
(http://www.mccme.ru/ium/ancient/combs93.html).