Комбинаторика и смежные вопросы сложности вычислений

Биномиальные коэффициенты. Бином Ньютона. Формулы с биномиальными коэффициентами.
Треугольник Паскаля и его свойства.
Полиномиальные коэффициенты. Полиномиальная формула.
Различные типы комбинаторных задач и методы их решения.
Однородные рекуррентные уравнения.
Неоднородные рекуррентные уравнения.
Примеры задач, решаемых с помощью рекуррентных уравнений. Числа Фибоначчи.
Числа Каталана. Примеры задач, в которых они возникают.
Основные понятия теории графов. Маршруты, цепи, циклы. Связность. Ориентированные и неориентированные графы.
Способы задания графов: матрица смежности, матрица инцидентности, список смежности, список рёбер.
Деревья. Характеристические свойства деревьев. Остовные деревья. Код Прюфера. Теорема Кэли.
Сложность арифметических вычислений. Свойства делимости биномиальных коэффициентов.
Формула Лежандра. Теорема Куммера. Верхняя оценка суммы логарифмов биномиальных коэффициентов.
Оценки сложности вычисления биномиальных коэффициентов.