https://scs.math.msu.ru/node/4...

Комбинаторные задачи естественным образом возникают в различных областях математики, например, когда необходимо подсчитать количество каких-либо объектов. Однако комбинаторике не всегда уделяется достаточно внимания. Даже задачи типа «В магазине продаётся 4 типа шоколадок. Сколько различных наборов из 8 шоколадок можно купить?» могут вызывать у студентов трудности. В спецкурсе рассказывается о методах решения различных комбинаторных задач. Основные темы: бином Ньютона и полиномиальная формула, треугольник Паскаля, рекуррентные уравнения, числа Фибоначчи и числа Каталана, основы теории графов. В заключительной части спецкурса планируется рассказать об оценках сложности вычисления биномиальных коэффициентов, которые являются одним из основных объектов комбинаторики.На данный момент комбинаторика является чрезвычайно содержательной и быстроразвивающейся областью математики. Стоит отметить, что в этой области есть много интересных открытых задач - например, гипотеза Сингмастера, гипотеза Адамара, задачи о количестве графов разных типов, задачи о числах Рамсея.

Список всех тем лекций

Лекция 1. Бином Ньютона и треугольник Паскаля.
Место комбинаторики в математике Понятие биномиального коэффициента Треугольник Паскаля Бином Ньютона Формулы с биномиальными коэффициентами Задачи на треугольник Паскаля с множителями Задача на сумму попарных произведений биномиальных коэффициентов

Лекция 2. Полиномиальные коэффициенты.
Повторение Правила сложения и умножения Полиномиальная формула и полиномиальный коэффициент Повторяющиеся биномиальные коэффициенты Гипотеза и теорема Сингмастера

Лекция 3. Шары и перегородки.
Некоторые свойства биномиальных коэффициентов Задача про деление шоколадок между студентами Задача про разбиение числа k на n слагаемых Рекуррентные уравнения

Лекция 4. Рекуррентные уравнения.
Обсуждение задач с прошлого занятия Гипотеза Сингмастера Алгоритм решения однородного рекуррентного уравнения Алгоритм решения неоднородного рекуррентного уравнения Связь рекуррентных и дифференциальных уравнений Строки треугольника Паскаля, где все числа нечётные

Лекция 5. Задачи, решаемые с помощью рекуррентных уравнений.
Числа Фибоначчи и 1 Задачи про лягушку до 9 Задача про рост деревьев Нечётные строки в треугольнике Паскаля

Лекция 6. Числа Каталана.
Связь между задачами про лягушек Правильные скобочные последовательности Задача про пути Двоичные деревья

Лекция 7. Задачи, в которых возникают числа Каталана.
Система рекуррентных уравнений Нечётные числа Каталана Задача про хорды Таблицы Юнга Триангуляции Задача на дом

Лекция 8. Решение различных комбинаторных задач.
Задача про разбиение числа на части Числа Фибоначчи и числа Каталана в треугольнике Паскаля Формула включений-исключений Основные понятия теории графов

Лекция 9. Деревья. Эйлеровость графов.
Повторение Деревья Характеристическое свойство деревьев Остовное дерево Эйлеровость и полуэйлеровость графов

Лекция 10. Способы задания графов. Изоморфизм графов. Код Прюфера.
Матрица инцидентности Изоморфизм графов Полный граф и его остовные деревья Код Прюфера

Лекция 11. Теорема Кэли. Сложность вычислений.
Доказательство теоремы Кэли Сложность арифметических вычислений Свойства суммирования биномиальных коэффициентов Свойства делимости биномиальных коэффициентов

Лекция 12. Вычисление биномиальных коэффициентов.
Информация про экзамен Свойства делимости биномиальных коэффициентов Теорема о существовании общего делителя N и C_N^k Оценки логарифма факториалов и биномиальных коэффициентов

Лекция 13. Оценки сложности вычисления биномиальных коэффициентов.
Повторение Оценка сумм k*ln(k) и k*ln^2(k) Сумма логарифмов биномиальных коэффициентов Сложность вычисления верхней части треугольника Паскаля Сложность вычисления строки треугольника Паскаля