Карточки
Тесты
Зави
Размещения. Как выбрать формулу комбинаторики
Размещения. Как выбрать формулу комбинаторики
В уроке «События и комбинаторика: повторение» мы вспомнили дерево выборов, перестановки $P_n=n!$ и сочетания $C_n^k$. В этом уроке разберем третий случай — упорядоченный выбор части предметов. Это размещения: выведем их формулу по дереву, сравним с сочетаниями и научимся выбирать нужную формулу по двум вопросам.
Когда порядок важен, но берут не всех
У кодового замка девять кнопок с цифрами от 1 до 9. Код — четыре разные кнопки, нажатые в определенном порядке. Сколько существует таких кодов? Перебирать их долго, поэтому сначала разберем задачу поменьше, а к замку вернемся в следующем разделе.
В финале четыре участника: А, Б, В и Г. Нужно определить, кто займет первое место, а кто второе. Построим дерево выборов. Первый ярус — победитель: четыре ветви. Второй ярус — второе место: победитель уже занят, поэтому из каждой ветви выходят три. Третьего яруса нет: мест всего два, и дерево обрывается.
Листьев $4 \cdot 3=12$. Лист «АБ» и лист «БА» — разные: в первом случае победил А, во втором — Б. Порядок важен. При этом в каждом листе только двое из четырех: берем не всех.
Определение
Размещение из $n$ по $k$ — это упорядоченный набор $k$ из $n$ различных предметов. Число размещений обозначают $A_n^k$ (читается «а из эн по ка»). Здесь $n$ и $k$ — целые числа, $0\le k\le n$.
В дереве размещение — путь от корня до листа длиной $k$ ярусов. Значит, $A_4^2=12$.
Ветви убывают на единицу, пока не кончатся места
Пусть предметов $n$, а мест $k$. На первом ярусе $n$ ветвей. После каждого выбора из каждой полученной вершины выходит на одну ветвь меньше: выбранный предмет второй раз не берут. На шаге $j$ у каждого частичного выбора есть $n-j+1$ продолжений, на последнем шаге $k$ — $n-k+1$. По правилу умножения число листьев — произведение чисел ветвей на всех ярусах.
Правило
Число размещений из $n$ по $k$ равно произведению $k$ убывающих на единицу множителей, начиная с $n$:
$$A_n^k=n(n-1)(n-2)\ldots(n-k+1)=\frac{n!}{(n-k)!}$$
Почему верна вторая запись. Если бы дерево шло до конца, листьев было бы $n!=n(n-1)\ldots(n-k+1)\cdot(n-k)(n-k-1)\ldots 1$. Хвост после $k$-го множителя — это $(n-k)!$. Дерево его не строит, поэтому хвост убираем делением. При $k=n$ хвост пустой, $0!=1$, и $A_n^n=n!=P_n$: перестановки — размещения всех предметов.
Пример 1
Задача. Вычислите $A_7^3$ двумя способами.
Решение. По произведению: три множителя, начиная с 7: $A_7^3=7 \cdot 6 \cdot 5=210$.
Через факториалы: $A_7^3=\dfrac{7!}{4!}=\dfrac{5040}{24}=210$.
Ответ: $210$.
Теперь вернемся к замку. Кнопок $n=9$, в коде $k=4$ разные кнопки, порядок нажатия важен. Это размещения: $A_9^4=9 \cdot 8 \cdot 7 \cdot 6=3024$ кода. А теперь проверьте, как дерево работает на другом замке: в опыте ниже кнопок $6$, а в коде $4$ разные кнопки.
Чем размещения отличаются от сочетаний
Возьмем трех учеников: А, Б, В — и выберем двоих. Если двоих ставят на разные роли (староста и заместитель), листья дерева такие: АБ, АВ, БА, БВ, ВА, ВБ — шесть размещений, $A_3^2=6$. Если выбирают просто двух дежурных, листья АБ и БА означают одну и ту же пару. Их склеиваем: остается три пары — АБ, АВ, БВ, то есть $C_3^2=3$.
В общем случае каждая группа из $k$ предметов встречается среди листьев столько раз, сколькими способами ее можно упорядочить, — $k!$ раз. Склеивая листья группами по $k!$, получаем сочетания.
Правило
Размещений в $k!$ раз больше, чем сочетаний: каждая группа дает $k!$ упорядоченных наборов.
$$A_n^k=C_n^k\cdot k!,\qquad C_n^k=\frac{A_n^k}{k!}$$
Пример 2
Задача. В кружке 7 человек. Сколькими способами можно а) выбрать троих в команду на олимпиаду; б) выбрать капитана, секретаря и редактора газеты?
Решение. Сначала б), затем а). б) Роли разные — порядок важен: $A_7^3=7 \cdot 6 \cdot 5=210$.
Теперь а). В команде роли одинаковы — склеиваем листья по $3!=6$: $C_7^3=210:6=35$.
Ответ: а) $35$; б) $210$.
Ошибка
Решавр распределяет золотую и серебряную медали между тремя участниками: «Выбираю двоих, а группу из двоих можно упорядочить $2!$ способами, поэтому $\dfrac{3 \cdot 2}{2!}=3$».
Проверим перебором. Способов шесть: АБ, АВ, БА, БВ, ВА, ВБ. Случаи «золото у А, серебро у Б» и «золото у Б, серебро у А» различаются — для А это разные медали. Значит, ответ $3$ неверен.
Где сломалось рассуждение: деление на $k!$ склеивает листья, которые отличаются только порядком. Склеивать можно, лишь когда порядок не важен. Обратная ошибка — не делить на $k!$, когда порядок не важен: тогда каждая группа посчитана $k!$ раз.
Два вопроса, которые выбирают формулу
Перестановки, размещения и сочетания — одно и то же дерево выборов. Различаются они ответами на два вопроса. Первый: важен ли порядок, то есть склеивать ли листья? Второй: берут ли все предметы, то есть идет ли дерево до последнего яруса?
| Порядок важен? | Берут всех? | Что с деревом | Формула |
|---|---|---|---|
| Да | Да | Идет до конца, листья не склеиваем | $P_n=n!$ |
| Да | Нет, $k$ из $n$ | Обрывается на $k$-м ярусе | $A_n^k=\dfrac{n!}{(n-k)!}$ |
| Нет | Любое $k$ от $0$ до $n$ | Обрывается и склеивается по $k!$ | $C_n^k=\dfrac{n!}{k!\,(n-k)!}$ |
Все три формулы годятся, только если предметы различны и не повторяются. Если предмет можно взять снова (цифры кода могут совпадать) и порядок важен, ветви на ярусах не убывают, и по правилу умножения получается $n^k$.
Пример 3
Задача. Выберите формулу и найдите ответ: а) сколькими способами можно расставить 5 разных книг на полке; б) сколькими способами из 10 человек выбрать председателя и секретаря; в) сколькими способами из 10 человек выбрать 3 дежурных.
Решение. а) Порядок важен, берут все пять: $P_5=5!=120$.
б) Порядок важен (роли разные), берут двоих: $A_{10}^2=10 \cdot 9=90$.
в) Порядок не важен, берут троих: $C_{10}^3=\dfrac{10 \cdot 9 \cdot 8}{3!}=120$.
Ответ: а) $120$; б) $90$; в) $120$.
Вернемся к замку. Бывают замки, у которых важно только, какие кнопки нажаты, а не в каком порядке. Тогда листья склеиваются по $4!=24$, и кодов в 24 раза меньше: $C_9^4=3024:24=126$.
Ошибка
Формулу выбирают по слову в условии: «выбрать» — значит сочетания. Но в задаче б) из примера 3 тоже «выбирают», а ответ $C_{10}^2=45$ вдвое меньше верного $90$: пары «А — председатель, Б — секретарь» и наоборот склеены по ошибке. Решает не глагол, а вопрос: изменится ли способ, если поменять выбранных местами?
Ограничение ломает дерево: начинаем с самого строгого шага
Формулы работают, когда на каждом ярусе число ветвей определяется однозначно. Условие вроде «число не начинается с нуля» эту однозначность ломает. Тогда считаем дерево сами: начинаем с самого ограниченного шага (в примере 4 — с первой цифры, которая не ноль) и проверяем, одинаково ли число продолжений у всех ветвей; если нет — делим варианты на случаи и складываем. Прием для условия «двое рядом» (объединить пару в блок) покажет пример 5.
Пример 4
Задача. Сколько трехзначных чисел с различными цифрами можно составить из цифр 0, 1, 2, 3, 4?
Решение. Самый строгий шаг — первая цифра: ноль на первом месте не ставят, остается 4 способа. Вторая цифра — любая из оставшихся четырех, теперь и ноль: 4 способа. Третья — 3 способа.
$4 \cdot 4 \cdot 3=48$.
Ответ: $48$.
Ошибка
Решавр начинает с последней цифры: «Последняя — 5 способов, средняя — 4, первая — 3, итого $60$». Проверим перебором: чисел $48$.
Где сломалось рассуждение: число способов для первой цифры зависит от того, где уже стоит ноль. При порядке «последняя — средняя — первая» это видно так. Если последняя цифра 0, то среднюю выбираем 4 способами, а первую — 3 способами (ненулевые из оставшихся): $4 \cdot 3=12$ чисел. Если последняя цифра ненулевая (4 способа), то при нуле посередине первую выбираем 3 способами, а при ненулевой средней (3 способа) для первой остаются 2 способа (ноль нельзя): $4\cdot(1\cdot3+3\cdot2)=36$ чисел. Всего $12+36=48$. Единого множителя для первой цифры нет, поэтому запретный шаг удобнее поставить первым.
Пример 5
Задача. На полку ставят 4 тома: 1, 2, 3, 4. Тома 1 и 2 должны стоять рядом. Сколько существует расстановок?
Решение. Самый строгий шаг — пара: склеим тома 1 и 2 в один блок. Внутри блока 2 порядка: «12» и «21». Теперь расставляем 3 объекта — блок, том 3, том 4: $3!=6$ способов.
$2 \cdot 3!=12$. Перебор всех $4!=24$ расстановок дает тоже $12$.
Ответ: $12$.
Вывод
Размещения считают упорядоченный выбор части предметов: дерево выборов, у которого число продолжений каждого выбора убывает на единицу и которое обрывается на $k$-м ярусе. Отсюда $A_n^k=n(n-1)\ldots(n-k+1)=\dfrac{n!}{(n-k)!}$. Если порядок не важен, листья склеивают по $k!$ и получают сочетания. Для исходного замка порядок важен, повторов нет и дополнительных запретов нет, поэтому кодов $3024$; если бы важен был только набор кнопок, их было бы $126$. Если же в условии есть запрет, сначала проверьте, одинаково ли число продолжений на каждом шаге. Эти формулы понадобятся, чтобы считать исходы в задачах на вероятность и в следующем уроке о словах с повторяющимися буквами.
| Случай | Как вспомнить через дерево |
|---|---|
| Все $n$ предметов по порядку | Дерево до конца: $P_n=n!$ |
| $k$ из $n$, порядок важен | Дерево обрывается на $k$-м ярусе: $A_n^k$ |
| $k$ из $n$, порядок не важен | Обрываем и склеиваем по $k!$: $C_n^k=A_n^k:k!$ |
| Есть запрет | Начните со строгого шага, проверьте число продолжений; если оно разное — разбейте на случаи |
Часто задаваемые вопросы
Произведение $n(n-1)\ldots(n-k+1)$ удобно для счета: в нем всего $k$ множителей. Запись $\dfrac{n!}{(n-k)!}$ удобна для преобразований и показывает связь с перестановками. Значения у них одинаковые.
$A_n^1=n$: один ярус из $n$ ветвей. $A_n^0=\dfrac{n!}{n!}=1$: дерево без ярусов, единственный способ — ничего не выбирать.
Мысленно поменяйте местами двух выбранных. Если получился другой способ (другая роль, другая цифра в коде, другое место), порядок важен. Если та же группа — не важен.
Если порядок важен, то ветви на ярусах не убывают: на каждом из $k$ шагов по $n$ вариантов, всего $n^k$. Например, кодов из трех цифр, которые могут совпадать, $10^3=1000$. Для выбора без порядка с повторениями формулы другие, и $n^k$ в нем не работает.
Если код состоит из $k$ разных символов из $n$ и догадку выбирают наугад, то есть любой допустимый код с одинаковой вероятностью, то вероятность угадать заданный код равна $\dfrac{1}{A_n^k}$: благоприятный исход один. То, что исходы — размещения, само по себе не делает их равновозможными: при неравновероятном выборе или повторах эту формулу без проверки применять нельзя.
5
5
1
5