Основные понятия теории множеств. Бинарные отношения и функции. Рефлексивность, симметричность, транзитивность. Взаимно-однозначные соответствия. Счетные множества.

• Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М., Физматлит, 2004.
• Верещагин Н. К., Шень А. Х. Начала теории множеств. М., МЦНМО, 2002.

Асимптотики сумм и рекуррентных последовательностей. Теорема Штольца. Оценки и асимптотики для комбинаторных величин. Элементарные оценки факториалов, биномиальных коэффициентов и пр. Формула Стирлинга (без доказательства).

• Грин Д., Кнут Д. Математические методы анализа алгоритмов. М., Мир, 1989.
• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
• Odlyzko A. M. Asymptotic Enumeration Methods. Глава из книги Handbook of Combinatorics, vol. 2, R. L. Graham, M. Groetschel and L. Lovasz, eds., Elsevier, 1995, pp. 1063–1229.

Понятие об энтропии. Асимптотики для биномиальных коэффициентов и прочее. Оценки сумм биномиальных коэффициентов. Замена сумм интегралами в асимптотических оценках. Преобразование Абеля. Примеры: гармонические числа, постоянная Эйлера, суммирование по простым числам и т.д.

Рекуррентные соотношения и производящие функции. Числа Фибоначчи. Формула Бинэ и матричное представление чисел Фибоначчи. Линейные рекуррентные соотношения с постоянными коэффициентами. Применение производящих функций для решения рекуррентных соотношений.

• Ландо С.К. Лекции о производящих функциях. М., МЦНМО, 2004.
• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
• Грин Д., Кнут Д. Математические методы анализа алгоритмов. М., Мир, 1989.

Применение степенных рядов и производящих функций для доказательства комбинаторных тождеств. Производящие функции для биномиальных коэффициентов. Произведение Адамара. Взаимно рекуррентные последовательности.

Экспоненциальные производящие фунцкии. Формальная связь с обычными производящими функциями. Факториальные степени. Числа Стирлинга и их применение. Числа Белла.

• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
• Риордан Д. Введение в комбинаторный анализ. М., ИЛ, 1963.

Числа и многочлены Бернулли. Формула суммирования Эйлера–Маклорена. Ее частные случаи и приложения.

• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
• Риордан Д. Введение в комбинаторный анализ. М., ИЛ, 1963.

Дискретная вероятность. Классическое определение вероятности. Условные вероятности. Независимость событий. Формулы полной вероятности и Байеса. Схема Бернулли. Полиномиальная схема. Случайные графы и множества. Приложения к комбинаторике.

• Ширяев А. Н. Вероятность. М. Наука, 1989.
• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
• Алон Н., Спенсер Дж. Вероятностный метод. М. Бином, 2009. (приложения к комбинаторике)

Случайные величины. Функции распределения. Независимые случайные величины. Математическое ожидание и дисперсия. Неравенства Маркова, Чебышёва и Чернова.

Ковариация и коэффициент корреляции. Независимость и некоррелированность случайных величин. Приложения случайных величин к комбинаторике и теории чисел. Закон больших чисел для схемы Бернулли. Локальная и интегральная предельные теоремы Муавра–Лапласа для схемы Бернулли. Теорема Пуассона.

Геометрическая вероятность. Парадокс Бертрана. Метод Монте-Карло. Абсолютно непрерывные распределения. Основные виды распределений. Числовые характеристики распределений: математическое ожидание, дисперсия, моменты, факториальные моменты. Совместные распределения. Ковариация и корреляция.

Производящие функции и характеристические функции случайных величин. Центральная предельная теорема (различные формулировки).