Evgeny Smirnov's classes

Дискретная математика, весна 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.
Более сложный учебник; читать его подряд может быть тяжело, можно использовать его скорее как справочник.