Основы дискретной математики

Санкт-Петербург, осень 2014

Описание

Целью курса является знакомство слушателей с основными понятиями и методами дискретной математики.

Запись курса в 2014 году не ведётся, по ссылке можно найти лекции прочтения 2012 года.

Преподаватели

Список лекций

Элементарная комбинаторика

Основные комбинаторные величины и простейшие комбинаторные формулы. Числа размещения и сочетания (с повторениями и без повторений). Бином Ньютона и биномиальные коэффициенты. Простейшие соотношения на биномиальные коэффициенты. Треугольник Паскаля. Обобщение бинома Ньютона и мультиномиальные коэффициенты. Семейства подмножеств конечного множества.

Принцип включений-исключений

Формула включений-исключений. Субфакториалы (задача о беспорядках). Формула обращения Мебиуса.

Частично упорядоченные множества

Понятие частично упорядоченного множества. Функция Мебиуса для частично упорядоченного множества. Цепи и антицепи. Теорема Дилуорса (б/д). Теорема Мирского.

Группа перестановок

Четность перестановки, разложение в произведение транспозиций, разбиение на циклы, четность цикла, классы сопряженных и циклический тип перестановки.

Разбиения числа в сумму слагаемых

Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Диаграммы Юнга. Рекуррентные соотношения для функций разбиения. Теоремы Харди- Рамануджана (б/д).

Рекуррентные соотношения. Числа Каталана и числа Белла

Рекуррентные соотношения. Числа Каталана и числа Белла. Различные интерпретации чисел Каталана.