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

Комбинаторные задачи естественным образом возникают в различных областях математики, например, когда необходимо подсчитать количество каких-либо объектов. Однако комбинаторике не всегда уделяется достаточно внимания. Даже задачи типа «В магазине продаётся 4 типа шоколадок. Сколько различных наборов из 8 шоколадок можно купить?» могут вызывать у студентов трудности. В спецкурсе рассказывается о методах решения различных комбинаторных задач. Основные темы: бином Ньютона и полиномиальная формула, треугольник Паскаля, рекуррентные уравнения, числа Фибоначчи и числа Каталана, основы теории графов. В заключительной части спецкурса планируется рассказать об оценках сложности вычисления биномиальных коэффициентов, которые являются одним из основных объектов комбинаторики.
На данный момент комбинаторика является чрезвычайно содержательной и быстроразвивающейся областью математики. Стоит отметить, что в этой области есть много интересных открытых задач - например, гипотеза Сингмастера, гипотеза Адамара, задачи о количестве графов разных типов, задачи о числах Рамсея.