Комбинаторика: перестановки, размещения и сочетания
Комбинаторика отвечает на вопрос "Сколько способов?". Основные формулы комбинаторики должен знать каждый олимпиадник. Факториал n! — количество перестановок n элементов.
Сочетания (биномиальные коэффициенты C из n по k) используются, когда порядок выбора не важен. Размещения (A из n по k) — когда порядок важен. Правила суммы и произведения позволяют разбивать сложные задачи на простые подзадачи.
Более сложные темы включают формулу включений-исключений (для подсчета пересекающихся множеств), шары и перегородки (разбиение числа на слагаемые) и числа Каталана. Треугольник Паскаля обладает множеством удивительных свойств, связанных с биномиальными коэффициентами.
Пример задачи: сколькими способами можно выбрать команду из 3 человек из класса в 25 человек? Решение: C(25, 3). А если нужно выбрать капитана и двух помощников? Решение: A(25, 3) или 25 * C(24, 2).
