Конспект

Литература по курсу «Комбинаторика»

Ключевые тезисы

• Основной задачник — «Комбинаторика» Виленкина (задачник с пояснениями и решениями).
• «Зелёная книжка» (методическое пособие под авторством лектора) — важный указатель по материалу курса.
• Дополнительные источники: задачник О.Н. Васильева и А.А. Егорова (более продвинутый), а также «Теория графов» Ф. Харари (для раздела о графах).

Основные понятия и правила

Комбинаторика — наука о том, как комбинировать объекты. Она решает две основные задачи:

1. Подсчёт количества возможных комбинаций.
2. Поиск комбинаций с оптимальными (экстремальными) свойствами.

Множество — совокупность объектов. Обозначается как A = {a₁, a₂, ..., aₙ}.

• Мощность множества (|A|) — количество элементов в нём.

Три основополагающих правила

Правило сложения

Если нужно выбрать один объект ИЛИ из множества A (мощности n), ИЛИ из множества B (мощности m), и множества не пересекаются, то число способов выбора равно n + m.

Правило умножения

Если нужно выбрать пару объектов: сначала один из множества A (мощности n), а затем один из множества B (мощности m), то число способов осуществить этот последовательный выбор равно n * m.

• Правило обобщается на любое количество последовательных выборов (перемножение мощностей всех множеств).

Принцип Дирихле («кролики и ящики»)

Если n + 1 кролика рассадить в n ящиков, то обязательно найдётся ящик, в котором не менее двух кроликов.

• Применение принципа часто требует творческого подхода: нужно определить, что является «кроликами», а что — «ящиками».

Пример применения принципа Дирихле

В квадрате со стороной 2 произвольно выбраны 5 точек. Доказать, что найдутся две точки, расстояние между которыми не больше √2.

• Доказательство: Разобьём квадрат на 4 равных клетки со стороной 1 («ящики»). 5 точек — это «кролики». По принципу Дирихле, в одной клетке окажется не менее двух точек. Максимальное расстояние между двумя точками внутри такой клетки равно длине диагонали — √2.

Сочетания, размещения, перестановки

Рассматривается множество A из n объектов. Способы выбрать k объектов:

1. Последовательно и без возвращения (объекты не повторяются) → k-размещения без повторений.
2. Последовательно, но с возвращением (объекты могут повторяться) → k-размещения с повторениями.
3. Без порядка и без возвращения (просто «пригоршня» разных объектов) → k-сочетания без повторений.
4. Без порядка, но с возможными повторениями (например, набор фруктов в корзине) → k-сочетания с повторениями.

Ключевое отличие: В размещениях важен порядок выбора (распределение по «должностям»), а в сочетаниях — только состав группы.

Обозначения и формулы

• Факториал: n! = 1 * 2 * ... * n. По определению 0! = 1.
• k-размещения с повторениями: Ᾱnk = nk.
• k-размещения без повторений: Ank = n * (n-1) * ... * (n-k+1) = n! / (n-k)!.
• Перестановки — это частный случай размещений, когда k = n. Число перестановок n различных объектов: Pn = Ann = n!.
• k-сочетания без повторений: Cnk = Ank / k! = n! / (k! * (n-k)!).

Вывод формулы для сочетаний
Каждому k-сочетанию (неупорядоченной «кучке») соответствует k! различных k-размещений (все возможные перестановки объектов внутри этой кучки). Поэтому общее число размещений (Ank) равно числу сочетаний (Cnk), умноженному на k!. Отсюда и получается формула.