Основы дискретной математики
Санкт-Петербург, осень 2016
Описание
Целью курса является знакомство слушателей с основными понятиями и методами дискретной математики.
Преподаватели
Список лекций
Основные комбинаторные величины и простейшие комбинаторные формулы. Числа размещения и сочетания (с повторениями и без повторений). Бином Ньютона и биномиальные коэффициенты. Простейшие соотношения на биномиальные коэффициенты. Треугольник Паскаля. Обобщение бинома Ньютона и мультиномиальные коэффициенты. Семейства подмножеств конечного множества.
Формула включений-исключений. Субфакториалы (задача о беспорядках). Формула обращения Мебиуса.
Четность перестановки, разложение в произведение транспозиций, разбиение на циклы, четность цикла, классы сопряженных и циклический тип перестановки.
Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Диаграммы Юнга. Рекуррентные соотношения для функций разбиения. Теоремы Харди- Рамануджана (б/д).