Спивак

Свободный Университет

Курс Александра Спивака
Комбинаторика-2

Аннотация к курсу

Вторая часть курса комбинаторики чуть сложнее начальной его части, но всё ещё полезна всем интересующимся математикой и её применениями. Небольшая часть курса потребует знания того, что такое производная и интеграл, но основная часть по прежнему доступно всем начиная с 9 класса средней школы.

Как проходит обучение?
Занятия будут в Google-классе с февраля по сентябрь 2022 года.
Первая часть курса читалась осенью 2021 года. Ознакомиться с программой
Знание прочитанного осенью 2021 курса облегчит работу, однако не обязательно, поскольку можно будет нагнать по ходу дела: все материалы Google-класса сохранились и могут быть использованы учащимися.

О преподавателе

Александр Спивак

педагог дополнительного образования Дворца пионеров (Москва), преподаватель Малого мехмата МГУ.
При помощи Спивака Николая Александровича (студент 1 курса мехмата МГУ).

Подайте заявку на курс уже сегодня!

Ждём вас в Свободном Университете
Прием заявок до 25.01.2022

Подать заявку

Программа курса

Продолжение курса осени 2021

Задача о ханойской башне.
Многомерный куб и двоичная система счисления.

Игра Конвея с единицами и числа Стирлинга для перестановок.

Дерево Калкина-Вилфа-Шрёдера-Броко и алгоритм Евклида.

Формула Пика. Количество целых точек в многограннике. Теорема о количестве внутренних точек.

Производящие функции для чисел Фибоначчи и чисел Каталана.

Разбиения на слагаемые. Количество разбиений на нечётные слагаемые равно количеству разбиений на попарно различные слагаемые.

Произведения и степенные ряды. Теорема Эйлера о разности между количествами разбиений на чётное и нечётное число слагаемых.

Тройное произведение Гаусса-Якоби. Его комбинаторные доказательства и вывод из коммутативного бинома Гаусса.

Количество деревьев с данным числом вершин. Автостоянки, перестановки и деревья

Цепные дроби. Теорема Маркова о пересечениях графика прямой пропорциональности с вертикалями и горизонталями. Подходящие дроби.

Равномерные слова. Геометрические слова. Слова Штурма. Теорема Хелли о выпуклых фигурах и геометричность равномерных слов.

Эйлеровы графы.

Гамильтоновы графы.

Деревенские свадьбы. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе. Теорема Менгера об отделимости.

Литература

Кнут, Грэхем и Паташник "Конкретная математика".
Ю. Бурман и А. Спивак "Автостоянки, перестановки и деревья" ("Квант", номер 4 за 2004 год).
Энциклопедия издательства "Росмэн" http://www.kvant.info/panov/enciklop.pdf

Напоминание:

программа курса осени 2021 года

Правило произведения. Факториал. Числа сочетаний и треугольник Паскаля.
Перестановки. Разложения на циклы. Числа Стирлинга для подмножеств и для перестановок.
Чётность перестановки. Разложение на транспозиции. Количество беспорядков.
Индикаторы. Формула включений-исключений. Заплаты на кафтане.
Числа Фибоначчи. Биекции. Производящая функция.
Функция Мёбиуса. Формула обращения Мёбиуса. Формула включений-исключений как частный случай формулы обращения Мёбиуса.
Перестановки без неподвижных точек. Количества ожерелий.
Числа Каталана. Треугольник и дерево Каталана.
Числа Шрёдера, Моцкина, Перрина.
Гауссовы биномиальные коэффициенты. Коммутативный и некоммутативный биномы Гаусса.
Треугольник Паскаля, степени и знакопеременные суммы.
Суммы степеней и числа Стирлинга для перестановок.
Игра цзяньшицзы. Теорема лорда Рэлея. Слова Фибоначчи, фибоначчиева система счисления.

Литература

Кнут, Грэхем и Паташник "Конкретная математика".
Айгнер и Циглер "Доказательства из КНИГИ".
Виленкин "Комбинаторика". https://math.ru/lib/363
Видеокурс "Комбинаторика и вероятности для начинающих" https://www.youtube.com/playlist?list=PL1JJ1jVZ9z5AsIntmdXttrdzfn58HTF2X

Программа курса