Дискретная математика 1 курс 2013-2014 учебный год

лектор: доц. Е.Б.Фейгин

---

Объявления
Срок сдачи листка № 7 продлён до 4 июня включительно.

Листок № 8 выдаваться не будет (в связи с государственными праздниками 12 и 13 июня).

В пятницу, 23 мая, на третьей паре состоится контрольная по дискретной математике

Список студентов, получивших автомат за третий модуль: Автомат 3 модуль

Выложен листок 4.

В среду 5 марта на второй паре (начало в 10.30) состоится контрольная работа по пройденному с начала третьего модуля материалу.

В листке 3 исправлена опечатка в задаче 9: нужно рассматривать не все последовательности, а только перестановки
(т.е. последовательности без повторений). 

Выложена обновлённая версия листка 5.

---

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

1.Биномиальные и мультиномиальные коэффициенты.
2. Перестановки, статистики и многочлены Гаусса.
3. Двенадцатеричный путь.
4. Формальные степенные ряды и производящие функции.
5. Рациональные производящие функции, рекуррентные соотношения.
6. Числа Каталана, пути Дика и пути Моцкина.
7. Производящие функции нескольких переменных. Числа Бернулли-Эйлера.
8. Принцип включения-исключения. Производящие функции Дирихле.
9. Производящие функции, пути и непрерывные дроби.
10. Разбиения, диаграммы Юнга и пентагональная теорема.
11. Перечисление графов и деревьев.
12. Частично упорядоченные множества и формула обращения Мебиуса.
13. Дискретная вероятность.
14. Производящие функции случайных величин

---

Литература:

Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики".
С. К. Ландо "Введение в дискретную математику".
С. К. Ландо "Лекции о производящих функциях".
Р. Стенли "Перечислительная комбинаторика".
Е. Ю.Смирнов "Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы". 

---

Лекции:

Лекция 1, 17.01. Множества и мультимножества. Биномиальные коэффициенты и разложения.
Литература: Р. Стенли, Перечислительная комбинаторика, том 1, гл. 1.

Лекция 2, 24.01. Мультиномиальные коэффициенты, перестановки мультимножеств.
Статистики на группе перестановок, циклическая структура, числа Стирлинга первого рода.
Литература: Р. Стенли, Перечислительная комбинаторика, том 1, гл. 1.

Лекция 3, 31.01.  Инверсии перестановок множеств и мультимножеств, q-биномиальные и q-мультиномиальные коэффициенты,  статистические суммы инверсий. Пространство формальных степенных рядов.
Литература: Р. Стенли, Перечислительная комбинаторика, том 1, гл. 1.
С.К.Ландо, Введение в дискретную математику, гл. 1

Лекция 4, 05.02. Формальные степенные ряды, основные операции: сложение, умножение, композиция.
Теорема существования и единственности обратного ряда. Числа Фибоначчи, экспонента.
Литература. С.К.Ландо, Введение в дискретную математику, гл. 1

Лекция 5, 07.02. Дифференциальное и интегральное исчисления формальных степенных рядов. Разложение
в ряд Тейлора, формула для производной композиции двух рядов. Экспонента и логарифм. Бином Ньютона
для произвольной комплексной степени.
Литература. С.К.Ландо, Введение в дискретную математику, гл. 1. А.Л.Городенцев, Лекции по алгебре,
http://vyshka.math.ru/pspdf/1011/algebra-2/lec_04.pdf

Лекция 6, 19.02. Рекуррентные соотношения и рациональные производящие функции. Векторные производящие функции.
Произведение Адамара рациональных производящих функций. Квазимногочлены и разложение на элементарные дроби.
Литература. С.К.Ландо, Введение в дискретную математику, гл. 2

Лекция 7, 28.02. Рекуррентные соотношения, рациональные производящие функции, квазимногочлены и разложение на элементарные дроби. Числа Каталана: комбинаторные интерпретации, явная формула и производящая функция.
Литература. С.К.Ландо, Введение в дискретную математику, гл. 2, гл. 3.

Лекция 8, 07.03. Комбинаторика чисел Каталана. Числа разбиений, диаграммы Юнга. Производящие функции чисел разбиений. Разбиения на нечётные и различные части. Теорема Эйлера.
Литература. С.К.Ландо, Введение в дискретную математику, гл 6. Е.Ю.Смирнов "Диаграммы Юнга, плоские разбиения и знакочередующиеся
матрицы", лекция 1.

Лекция 9, 19.03. Пятиугольные числа и теорема Эйлера. Рекуррентная формула для чисел разбиений. Тождество Якоби для тройного произведения.
Литература. С.К.Ландо, Введение в дискретную математику, гл 6.
Е.Ю.Смирнов "Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы", лекции 1 и 2.

Лекция 10, 04.04. Перечисление путей в графах, производящие функции двух переменных, графы Паскаля, Дика и Моцкина, треугольник
Бернулли-Эйлера.
Литература. С.К.Ландо, Введение в дискретную математику, гл 3,4.

Лекция 11, 11.04. Треугольник Бернулли-Эйлера, пилообразные перестановки, рекуррентные соотношения,
дифференциальные уравнения, тангенциальные числа.
Литература. С.К.Ландо, Введение в дискретную математику, гл 4.

Лекция 12, 18.04. Числа Эйлера, треугольники Дика с кратностями. Принцип включения-исключения и линейная алгебра.
Конечные множества и свойства элементов.
Литература. С.К.Ландо, Введение в дискретную математику, гл 4.
Р. Стенли, Перечислительная комбинаторика, гл. 2.

Лекция 13, 25.04. Принцип включения-исключения и числа беспорядков.
Производящие функции Дирихле, мультипликативные последовательности,
формула обращения Мёбиуса.
Дзета функция, функция Мёбиуса, эйлерова фи-функция.
Литература.
С.К.Ландо, Введение в дискретную математику, гл 7.
Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики",  гл. 4.9, 7.

Лекция 14, 16.05. Графы и деревья. Помеченные и корневые деревья. Коды Прюфера и теорема Кэли.
Литература.
С.К.Ландо, Введение в дискретную математику, гл 8.
Р.Стенли, Перечислительная комбинаторика: деревья, том 2, гл. 5

Лекция 15, 30.05.
Теорема Кэли и теорема Лагранжа. Дискретная вероятность, случайные величины, математическое ожидание, дисперсия.
Литература.
С.К.Ландо, Введение в дискретную математику, гл 8.
Р.Стенли, Перечислительная комбинаторика: деревья, том 2, гл. 5.
Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики", гл. 8

Лекция 16, 06.06.
Ковариация и коэффициент корреляции случайных величин. Неравенство Чебышёва. Производящие функции случайных величин.
Литература. Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики", гл. 8

---

Задачи для семинаров:   Семинар 1   Семинар 2  Семинар 3   Семинар 4  Семинар 5  Семинар 6  Семинар 7   
Семинар 8 (числа Каталана): Р.Стенли, Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции, стр. 283-295. 
Семинар 9   Семинар 10  Семинар 11  Семинар 12   Семинар 13  Семинар 13  Семинар 14
Семинар 15   Семинар 16  Семинар 17   Семинар 18

---

Листки:   Листок 1   срок сдачи: до 07.02.2014
Листок 2  срок сдачи: до 21.02.2014 
Листок 3  срок сдачи: 06.03.2014 
Листок 4  срок сдачи 20.03.2014 
Листок 5  срок сдачи 24.04.14
Листок 6  срок сдачи 15.05.14
Листок 7  срок сдачи 29.05.14