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

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

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

• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 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.

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

• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 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.
• Greene D.H., Knuth D.E. Mathematics for the Analysis of Algorithms. Birkhauser, 1990.

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

• Ландо С.К.Лекции о производящих функциях. М., МЦНМО, 2004.
• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.
• Greene D.H., Knuth D.E. Mathematics for the Analysis of Algorithms. Birkhauser, 1990.

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

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

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

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

Дискретная вероятность. Классическое определение вероятности. Условные вероятности. Независимость событий. Формулы полной вероятности и Байеса. Схема Бернулли. Полиномиальная схема. Случайные графы и множества. Приложения к комбинаторике: нижняя оценка чисел Рамсея, теоремы Эрдеша–Мозера и Эрдеша–Хайнала.

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

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

• Ширяев А. Н. Вероятность. М. Наука, 1989.
• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.

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

• Ширяев А. Н. Вероятность. М. Наука, 1989.
• Алон Н., Спенсер Дж. Вероятностный метод. М. Бином, 2009. (приложения к комбинаторике)

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

• Ширяев А. Н. Вероятность. М. Наука, 1989.
• Алон Н., Спенсер Дж. Вероятностный метод. М. Бином, 2009. (приложения к комбинаторике)

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

• Ширяев А. Н. Вероятность. М. Наука, 1989.
• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.