Перестановки и сочетания: почему порядок меняет ответ

Пять человек вызвались участвовать в проекте. Нужно выбрать капитана и заместителя. Капитана можно выбрать пятью способами, затем заместителя четырьмя. Получается двадцать назначений.

Теперь изменим одно предложение: нужен комитет из двух человек без отдельных ролей. Те же пять человек дают десять комитетов. Люди не изменились. Изменилось определение одного результата.

Перестановки и сочетания позволяют считать результаты, не перечисляя все варианты. Формулы становятся понятными, когда вы решаете, какую информацию сохраняет результат. Сначала разберём это решение, затем выведем обозначения.

Начинайте с позиций, а не с формулы

Представьте два пустых места с подписями «капитан» и «заместитель». Для первого есть пять кандидатов. После его заполнения для второго остаются четыре. У каждого первого выбора есть четыре продолжения:

$$5 \times 4 = 20$$

Это правило произведения. Если за каждым вариантом на одном этапе следует одинаковое число вариантов, перемножьте числа по этапам. Можно представить дерево с пятью ветвями, каждая из которых делится ещё на четыре.

Подписи важны. Алекс как капитан и Беа как заместитель отличаются от Беа как капитана и Алекса как заместителя. Люди те же, позиции разные. Это упорядоченный выбор, то есть перестановка.

В комитете нет подписанных позиций. «Алекс, Беа» и «Беа, Алекс» описывают одну группу. Используя двадцать назначений для комитетов, вы посчитаете каждую группу дважды.

Тест обмена показывает, важен ли порядок

Спросите: если поменять местами два выбранных элемента, получится другой результат?

Для пьедестала гонки да: золото и серебро являются разными результатами. Для набора начинок пиццы обычно нет: грибы с оливками и оливки с грибами являются одним выбором.

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

До вычислений запишите пример результата. «Капитан Алекс, заместитель Беа» содержит роли. «Группа из Алекса и Беа» не содержит. Этот шаг предотвращает больше ошибок, чем заучивание длинного списка формул.

Ситуация	Что фиксирует результат	Модель
Присудить золото, серебро и бронзу	Человека на каждом месте	Порядок есть, без повторений
Выбрать трёх членов комитета	Только состав	Порядка нет, без повторений
Составить четырёхзначный код	Цифру на каждой позиции	Порядок есть, повторения могут быть разрешены
Выбрать несколько шариков мороженого	Количество каждого вкуса	Порядка нет, повторения могут быть разрешены

В последних двух строках нужно также выяснить, разрешены ли повторения. Одного вопроса о порядке недостаточно.

Факториалы считают полные расположения

Расставим в ряд четыре разные книги. Для первого места есть четыре выбора, для второго три, для третьего два, для последнего один:

$$4! = 4 \times 3 \times 2 \times 1 = 24$$

Восклицательный знак обозначает факториал, то есть сокращает убывающее произведение. Для неотрицательного целого $n$ факториал считает расположения всех $n$ различных элементов.

Почему $0! = 1$? Есть одно пустое расположение: ничего не делать. Это значение также сохраняет равенство $1! = 1 \times 0!$.

Факториал не является повторным сложением или степенью. Факториал четырёх равен двадцати четырём, а четыре в четвёртой степени равно двумстам пятидесяти шести. В факториале число вариантов уменьшается, потому что элемент нельзя повторить; в степени оно постоянно.

Перестановки останавливают произведение раньше

Пусть в забеге семь участников, а нас интересуют первые три места без ничьих. Для первого места есть семь вариантов, для второго шесть, для третьего пять:

$$P(7,3) = 7 \times 6 \times 5 = 210$$

Порядок остальных четырёх не важен. Умножение до единицы отвечало бы на другой вопрос.

Для $r$ упорядоченных позиций, заполняемых из $n$ различных элементов без повторений:

$$P(n,r) = \frac{n!}{(n-r)!}$$

Знаменатель сокращает неиспользованный хвост факториала. В примере с бегунами семь факториал, делённое на четыре факториал, оставляет семь умножить на шесть и на пять.

Формула предполагает $0 \le r \le n$ и различные доступные элементы. Если условия изменились, вернитесь к позициям, а не подгоняйте числа под выражение.

Сочетания убирают повторяющиеся расположения

Выберем трёх из семи в комитет. Упорядоченный подсчёт даёт 210, но считает разные порядки одной тройки разными ответами.

Одну тройку, Алекс, Беа и Чен, можно записать шестью способами: ABC, ACB, BAC, BCA, CAB и CBA. Каждая тройка встречается шесть раз, потому что $3! = 6$.

Делим на число повторяющихся расположений:

$$\binom{7}{3} = \frac{210}{6} = 35$$

В общем виде:

$$\binom{n}{r} = \frac{n!}{r!(n-r)!}$$

Это читается как «число сочетаний из n по r». Первое деление убирает неиспользованные элементы, второе убирает порядки, которые мы больше не различаем.

Есть полезная симметрия: $\binom{7}{3} = \binom{7}{4}$. Выбор трёх участников одновременно определяет четырёх неучастников. Оба описания относятся к одному набору решений.

Повторения снова меняют вопрос

В четырёхзначном коде на каждой позиции, включая первую, можно использовать цифры от нуля до девяти, а повторения разрешены. У каждой позиции десять вариантов:

$$10^4 = 10000$$

Если цифры повторять нельзя:

$$10 \times 9 \times 8 \times 7 = 5040$$

Если сказано «четырёхзначное число», а не «код», ведущий ноль обычно запрещён. При разрешённых повторениях:

$$9 \times 10 \times 10 \times 10 = 9000$$

Три похожих условия дают три ответа. Формула не стала ненадёжной, изменились ограничения.

Неупорядоченный выбор с повторениями, например шариков с одинаковым вкусом, требует другого метода. Обычные сочетания предполагают, что каждый элемент выбирают не более одного раза. Понять, что знакомая формула неприменима, уже правильный первый шаг.

Разбирайте решение в таком порядке

До вычислений запишите один полный результат. Затем выясните, различают ли результаты порядок или роли, можно ли повторять элементы и есть ли особое ограничение для какой-либо позиции.

Попробуйте решить три задачи, не заглядывая сразу в ответы:

1. Из шести человек выбрать председателя и секретаря, причём один человек не может занимать обе должности.
2. Из тех же шести выбрать двух равноправных представителей.
3. Составить трёхсимвольный код из четырёх символов с повторениями.

В первой задаче $6 \times 5 = 30$ назначений. Во второй делим это на $2!$ и получаем пятнадцать пар. В третьей $4^3 = 64$ кода, потому что для каждой позиции доступны все четыре символа.

Объяснение важнее числа. Если вы можете сказать, почему один ответ делят на два, а другой нет, различие вам понятно.

Подсчёт лежит в основе вероятности

Правильно сосчитав равновероятные исходы, можно вычислять вероятности, сравнивая благоприятные исходы со всеми возможными. Следующий шаг описан в нашем интуитивном руководстве по вероятности. Парадокс дней рождения показывает, как удачный подсчёт упрощает неожиданный результат.

Пока ограничьтесь малым: определите исход, нарисуйте позиции, если они есть, и объясните каждый множитель. Для практики используйте задачи Math Zen по вероятности, а когда обозначения скрывают смысл, возвращайтесь к маленькому примеру.

Перестановка сохраняет расположение. Сочетание сохраняет состав. Деление на факториал просто забывает расположение, не считая ту же группу снова.