Урок 3: Комбинаторика — перестановки, размещения, сочетания

Считать перестановки, размещения и сочетания и выбирать формулу по признаку «важен ли порядок».

Формулы комбинаторики

Перестановки, размещения и сочетания: когда что применять

Ключевой вопрос: важен ли порядок? Ответ определяет, какую из трёх формул использовать.

Таблица трёх формул комбинаторики. Перестановки — n! — все элементы, порядок важен; Размещения — n!/(n-k)! — k из n, порядок важен; Сочетания — n!/((n-k)!k!) — k из n, порядок не важен. Примеры для каждой — Сочетания — наиболее частый инструмент в задачах «выбора без учёта порядка»

Lesson notes

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

Комбинаторика отвечает на вопрос: сколько способов существует выбрать или расставить объекты? Главный вопрос при выборе формулы: важен ли порядок? Правило умножения: если на первом шаге n₁ вариантов, на втором n₂ и т.д., то всего n₁ · n₂ · ... вариантов. Перестановки — количество способов расставить все n объектов в ряд: n! = n · (n−1) · ... · 1. Например, 5! = 5·4·3·2·1 = 120. Размещения P(n,k) — выбираем k объектов из n, и порядок важен: P(n,k) = n! / (n−k)!. Пример: P(5,2) = 5!/(5−2)! = 120/6 = 20. Это ответ на вопрос «сколькими способами можно выбрать и расставить 2 из 5 человек на первое и второе место». Сочетания C(n,k) — выбираем k объектов из n, порядок НЕ важен: C(n,k) = n! / (k! · (n−k)!). Пример: C(5,2) = 120 / (2 · 6) = 120/12 = 10. Это ответ на «сколькими способами выбрать команду из 2 человек из 5 — без учёта порядка». Заметьте: C(5,2) = 10 = P(5,2)/2! = 20/2. Сочетаний всегда меньше или равно размещениям.