Чем отличаются перестановки, размещения и сочетания?
В комбинаторике три похожих слова: перестановки, размещения, сочетания. Я их всё время путаю. В чём разница и когда что применять?
2 ответа
Разница в двух вопросах: «берём все или часть?» и «важен ли порядок?».
Перестановки (P). Берём ВСЕ n элементов и расставляем по порядку. Порядок важен.
P(n) = n!
Пример: сколькими способами рассадить 5 человек в ряд → 5! = 120.
Размещения (A). Берём k из n, порядок ВАЖЕН.
A(n,k) = n! / (n−k)!
Пример: из 10 спортсменов выбрать золото-серебро-бронзу (порядок мест важен) → A(10,3) = 10·9·8 = 720.
Сочетания (C). Берём k из n, порядок НЕ важен.
C(n,k) = n! / (k!·(n−k)!)
Пример: из 10 человек выбрать команду из 3 (кто за кем — неважно) → C(10,3) = 120.
Ключ: если переставление выбранных даёт новый вариант — это размещение/перестановка. Если переставление даёт тот же набор — это сочетание. Сочетаний всегда меньше, потому что мы «склеиваем» одинаковые по составу варианты.
Запоминалка через пример: сейф — код 1-2-3 и 3-2-1 разные → порядок важен → размещения. Салат — порядок овощей неважен → сочетания. Очередь из всех — расставляем всех → перестановки. Связь: A(n,k) = C(n,k) · k! (сочетания, домноженные на все перестановки внутри выбранных).