Свободный Университет
Свободный Университет
Курс Александра Спивака
Комбинаторика-2
Курс Александра Спивака
Комбинаторика-2
Аннотация к курсу
Вторая часть курса комбинаторики чуть сложнее начальной его части, но всё ещё полезна всем интересующимся математикой и её применениями. Небольшая часть курса потребует знания того, что такое производная и интеграл, но основная часть по прежнему доступно всем начиная с 9 класса средней школы.
Как проходит обучение?
Занятия будут в Google-классе с февраля по сентябрь 2022 года.
Первая часть курса читалась осенью 2021 года. Ознакомиться с программой
Знание прочитанного осенью 2021 курса облегчит работу, однако не обязательно, поскольку можно будет нагнать по ходу дела: все материалы Google-класса сохранились и могут быть использованы учащимися.
О преподавателе
Александр Спивак
педагог дополнительного образования Дворца пионеров (Москва), преподаватель Малого мехмата МГУ.
При помощи Спивака Николая Александровича (студент 1 курса мехмата МГУ).
Подайте заявку на курс уже сегодня!
Ждём вас в Свободном Университете
Прием заявок до 25.01.2022
Программа курса
Продолжение курса осени 2021
14
Задача о ханойской башне.
Многомерный куб и двоичная система счисления.
15
Игра Конвея с единицами и числа Стирлинга для перестановок.
16
Дерево Калкина-Вилфа-Шрёдера-Броко и алгоритм Евклида.
17
Формула Пика. Количество целых точек в многограннике. Теорема о количестве внутренних точек.
18
Производящие функции для чисел Фибоначчи и чисел Каталана.
19
Разбиения на слагаемые. Количество разбиений на нечётные слагаемые равно количеству разбиений на попарно различные слагаемые.
20
Произведения и степенные ряды. Теорема Эйлера о разности между количествами разбиений на чётное и нечётное число слагаемых.
21
Тройное произведение Гаусса-Якоби. Его комбинаторные доказательства и вывод из коммутативного бинома Гаусса.
22
Количество деревьев с данным числом вершин. Автостоянки, перестановки и деревья
23
Цепные дроби. Теорема Маркова о пересечениях графика прямой пропорциональности с вертикалями и горизонталями. Подходящие дроби.
24
Равномерные слова. Геометрические слова. Слова Штурма. Теорема Хелли о выпуклых фигурах и геометричность равномерных слов.
25
Эйлеровы графы.
26
Гамильтоновы графы.
27
Деревенские свадьбы. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе. Теорема Менгера об отделимости.
Литература
  1. Кнут, Грэхем и Паташник "Конкретная математика".


  2. Ю. Бурман и А. Спивак "Автостоянки, перестановки и деревья" ("Квант", номер 4 за 2004 год).


  3. Энциклопедия издательства "Росмэн" http://www.kvant.info/panov/enciklop.pdf
Напоминание:
программа курса осени 2021 года
  1. Правило произведения. Факториал. Числа сочетаний и треугольник Паскаля.

  2. Перестановки. Разложения на циклы. Числа Стирлинга для подмножеств и для перестановок.

  3. Чётность перестановки. Разложение на транспозиции. Количество беспорядков.

  4. Индикаторы. Формула включений-исключений. Заплаты на кафтане.

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

  6. Функция Мёбиуса. Формула обращения Мёбиуса. Формула включений-исключений как частный случай формулы обращения Мёбиуса.

  7. Перестановки без неподвижных точек. Количества ожерелий.

  8. Числа Каталана. Треугольник и дерево Каталана.

  9. Числа Шрёдера, Моцкина, Перрина.

  10. Гауссовы биномиальные коэффициенты. Коммутативный и некоммутативный биномы Гаусса.

  11. Треугольник Паскаля, степени и знакопеременные суммы.

  12. Суммы степеней и числа Стирлинга для перестановок.

  13. Игра цзяньшицзы. Теорема лорда Рэлея. Слова Фибоначчи, фибоначчиева система счисления.
Литература
  1. Кнут, Грэхем и Паташник "Конкретная математика".

  2. Айгнер и Циглер "Доказательства из КНИГИ".

  3. Виленкин "Комбинаторика". https://math.ru/lib/363

  4. Видеокурс "Комбинаторика и вероятности для начинающих" https://www.youtube.com/playlist?list=PL1JJ1jVZ9z5AsIntmdXttrdzfn58HTF2X