Дискретная математика, весна 2020
Здесь будут появляться материалы по дискретной математике для первого курса матфака, группы образовательных программ «Математика» и «Совместный бакалавриат ВШЭ-ЦПМ».
Лекции
Курс «Introduction to Enumerative Combinatorics» на Курсере:
https://www.coursera.org/learn/enumerative-combinatorics
Первая неделя, 6-12 апреля:
Lecture 1. Permutations and Binomial Coefficients
Lecture 2. Binomial coefficients, continued. Inclusion and exclusion formula.
Литература: [В3], гл.I-II; [Л] 1.1-1.2, 7.1 [ГКП] 5.1-5.3
Вторая неделя, 13-19 апреля:
Lecture 3. Linear recurrences. The Fibonacci sequence
Lecture 5. Generating functions: a unified approach to combinatorial problems. Solving linear recurrences
Литература: [В3] 55, 94, VII: 105-109,115-118; [Л] 1.4, 2.1-2.3 [ГКП] 6.6, 7.2, 7.3
Третья и четвертая недели, 20-30 апреля:
Lecture 4. A nonlinear recurrence: many faces of Catalan numbers
Lecture 6. Generating functions, continued. Generating function of the Catalan sequence
Литература: [В3] 81-84, 110-114; [Л] 3.3; [ГКП] 7.5
Пятая и шестая недели, 6-15 мая:
Lecture 7. Partitions. Euler’s generating function for partitions and pentagonal formula
Литература: [В3] 118, [Л] 6.1, 6.2.
Седьмая неделя, 18-22 мая:
Lecture 8. Gaussian binomial coefficients. “Quantum” versions of combinatorial identities
Литература: [См] лекция 2.
Восьмая неделя, 25-29 мая:
Лекция 9. Перечисление деревьев и теорема Кэли. [видео|записки]
Литература: [Л] 8.1.
Дополнительная литература: К.П.Кохась, Как Бусенька разбирала новогоднюю ёлку. «Квантик» №12, 2018.
Девятая неделя, 1-9 июня:
Лекция 10. Суммы степеней и числа Бернулли. [видео|записки]
Литература: [М]
Дополнительная литература: [Л] 4.3, 4.4, [ГКП] 6.5
Семинары
Листок 1 (6-12 апреля). Перестановки и биномиальные коэффициенты.
Листок 2 (13-19 апреля). Линейные рекурренты.
Листок 3 (20-30 апреля). Числа Каталана.
Листок 4 (6-15 мая). Разбиения.
Листок 5 (18-22 мая). q-бином.
Листок 5а (21 мая, дополнительный). Еще одно доказательство пентагональной теоремы.
Листок 6 (25-29 мая). Перечисление деревьев.
Листок 7 (1-9 июня). Суммы степеней и числа Бернулли.
Домашние задания
Домашнее задание 1 (к 19 мая)
Домашнее задание 2 (к 8 июня)
Расписание семинаров (возможны изменения!)
A1: среда 12:00, четверг 13:30
Евгений Юрьевич Смирнов, esmirnov@hse.ru
B1: понедельник 10:30, среда 10:30
Василий Геннадьевич Горбунов, vgorbunov@hse.ru
C1: среда 10:30, четверг 12:00
Михаил Борисович Скопенков, mikhail.skopenkov@gmail.com
D1: понедельник 13:30, пятница 10:30
Александр Юрьевич Буряк, aburyak@hse.ru
E1: понедельник 13:30, среда 13:30
Алексей Геннадьевич Горинов, agorinov@hse.ru
G1: Александр Савельевич Штерн, ashtern@hse.ru
Ссылку (discord) можно получить у преподавателя или старосты
HIJ1: вторник 12:00, четверг 12:00
Григорий Александрович Мерзон, grigory.merzon@gmail.com
Ссылку (discord) можно получить у преподавателя или старосты группы
Формула оценки
Оценка за курс складывается из следующих составляющих:
10% — оценка за курс на Coursera;
20% — оценка за еженедельные письменные домашние задания;
25% — контрольная работа (ориентировочно после майских праздников прошла 29 мая);
45% — письменный экзамен.
Итог округляется до ближайшего целого (95% — это 10, а 94% — это 9).
Литература
Книг по дискретной математике огромное количество. Здесь приведены лишь несколько книг, материал из которых можно читать в дополнение к просмотру лекций. Список будет обновляться.
По просьбам слушателей я указываю только книги и статьи на русском языке.
Основная литература
[B] Виленкин Н.Я. Комбинаторика. изд. «Наука», 1969. https://math.ru/lib/363
Классическая книга, на которой выросло не одно поколение матшкольников.
[В3] Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. МЦНМО, 2006.
Существенно расширенное издание предыдущей книги.
[Л] Ландо С.К. Введение в дискретную математику. МЦНМО, 2012.
http://vyshka.math.ru/pspdf/1112/discr/LandoBook.pdf
Матфаковский учебник по этому курсу. Всё, что нам нужно, там есть.
Дополнительная литература
[ГКП] Р.Грэхем, Д.Кнут, О.Паташик, Конкретная математика. Основание информатики. Мир: Бином, 2009
[М] Г.А.Мерзон, Алгебра, геометрия и анализ сумм степеней последовательных чисел (Матем. просв., сер. 3, вып. 21, с. 104–118)
[См] Е.Ю.Смирнов, Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы. М.: МЦНМО, 2014. https://www.mccme.ru/free-books/dubna/smirnov-asm.pdf
[C] Стенли, Р. Перечислительная комбинаторика. Мир, 1990.
Более сложный учебник; читать его подряд может быть тяжело, можно использовать его скорее как справочник.