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

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

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

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

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

Основы теории графов. Графы и орграфы. Основные определения. Матрицы смежности и инцидентности. Маршруты, пути и циклы. Связность, компоненты связности.

Основы теории графов. Связность орграфов: различные виды связности, компоненты сильной связности, граф компонент. Диаметр и радиус графа. Дополнительный граф. Изоморфизм графов. Деревья и их свойства.

Пути, циклы и раскраски графов. Двудольные графы, критерий двудольности. Эйлеровы и Гамильтоновы пути и циклы. Простейшие свойства раскрасок графов. Теорема Брукса (б/д). Теорема Визинга (б/д).

Паросочетания и покрытия. Независимые и доминирующие множества и связь между ними. Паросочетания в двудольном графе: теоремы Холла и Кенига. Максимальные покрытия. Теорема Галлаи. Чередующиеся цепи.

Связность графов. Двусвязные графы. Дерево блоков и точек сочленения. Вершинная и реберная связность. Теорема Менгера. Структура минимальных k-связных графов: теорема Мадера о цикле и оценка количества вершин степени k. Редуцирование трехсвязных графов (теорема Татта о колесе).