Современная комбинаторика (Modern combinatorics)

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

Современная комбинаторика, таким образом, это своего рода основа основ: это и красивейшая теория с массой нетривиальных задач и методов, но это и прекрасная база для приложений в computer science, в анализе сложных сетей, в теории кодирования и криптографии, в биоинформатике и др. В курсе мы познакомим слушателей с наиболее важными областями и инструментами современной комбинаторики, причем многие темы курса по сути уникальны: здесь не только классические комбинаторные величины и тождества, но также и общая теория обращения Мебиуса, и диаграммы Юнга, и рекурсия, и производящие функции. Это позволит нам в дальнейших курсах выйти на реальные приложения в анализе таких сложных сетей, как Интернет, социальные, биологические сети, сети межбанковских взаимодействий и др.

Для участия в курсе слушателю необходимо иметь базовые представления о теории множеств и началах анализа. Все остальные понятия будут введены в ходе курса.

Курс состоит из 7 недель лекций и 1 недели экзамена. Каждую неделю слушатель выполняет задания, составляющие 10% от всего курса (5% тест и 5% задачи с ответом). Экзамен также состоит из теста и задач с ответом, каждая часть оценивается в 15% от общей суммы. Для успешного прохождения курса необходимо в каждом задании набрать не менее 50% от общего числа баллов.

Данный курс рекомендуется к прохождению перед курсом Теория вероятностей.

• Основные принципы комбинаторики
• Основные принципы комбинаторики. Правило сложения. Правило умножения. Принцип Дирихле. Пример применения принципа Дирихле. Теорема о раскраске множества в два цвета. Мощности множества попарно неортогональных {-1,0,1}-векторов : верхняя и нижняя оценки. Числа сочетаний, размещений и перестановок.
• Комбинаторные тождества
• Бином Ньютона. Полиномиальная формула. Формула включений и исключений. Простейшие тождества. Треугольник Паскаля. Сумма биномиальных и полиномиальных коэффициентов. Сумма квадратов биномиальных коффициентов. Формулы для суммы степеней натуральных чисел. Знакопеременное тождество.
• Формула обращения Мёбиуса
• Формула для количества ‘слов’. Определение циклической последовательности. Формулировка проблемы. Простое число. Бесконечность простых. Основная теорема арифметики. Функция Мебиуса. Суммы по делителям. Формула обращения Мебиуса.
• Циклические последовательности
• Вывод формулы для количества циклических последовательностей. Частично упорядоченное множество. Обобщенная функция Мебиуса. Связь с обычной функцией Мебиуса. Теорема об формуле обращения Мебиуса на ч.у.м. Передоказательство формулы включений и исключений (часть 1) (*).
  
• Разбиения
• Разбиения чисел на слагемые. Упорядоченные и неупорядоченные разбиения. Формула для числа упорядоченных разбиений. Рекуррентное соотношение для числа неупорядоченных разбиений. Формула Харди-Рамануджана. Диаграмма Юнга. Теоремы Эйлера о равенстве количеств неупорядоченных разбиений. Передоказательство формулы включений и исключений (часть 2) (*).
• Линейные рекуррентные соотношения. Формальные степенные ряды.
• Линейные рекуррентные соотношения. Числа Фибоначчи. Теорема о решении линейного рекуррентного соотношения второго порядка. Формальные степенные ряды. Операции над рядами. Пример “деления в столбик”.
• Производящие функции
• Производящие функции. Теорема о сходимости степенных рядов (б/д). Примеры, иллюстрирующие теоремы. Сходимость на границе интервала. Числа Фибоначчи и их производящая функция. Суммы чисел Фибоначчи, чисел сочетания и пр. Числа Каталана. Извлечение корней из степенных рядов. Формула для числа Каталана: д-во через производящие функции.
• Экзамен
• Экзамен.