Карточки
Тесты
Зави
Перестановки с повторениями: слова и числа
Перестановки с повторениями: слова и числа
В уроке «Размещения. Как выбрать формулу» мы считали наборы различных предметов, а в уроке «Перестановки, факториал, сочетания» — перестановки: $n$ различных предметов можно расставить в ряд $P_n=n!$ способами. Теперь разберем, что меняется, когда среди предметов есть одинаковые: буквы в слове, цифры в числе, шашки одного цвета. Начнем с вопроса, ответ на который получим в третьем разделе: сколько различных слов можно получить, переставляя буквы слова «ПАРАБОЛА»?
Когда все буквы разные, слов столько же, сколько перестановок
Словом в этом уроке назовем любую последовательность букв, даже бессмысленную. Возьмем слово «КОТ» и построим дерево выборов: на первом ярусе выбираем первую букву — $3$ ветви, на втором — $2$, на третьем — $1$. Путь от корня до листа — одно слово. Листьев $3 \cdot 2 \cdot 1=3!=6$: КОТ, КТО, ОКТ, ОТК, ТКО, ТОК.
Разные листья здесь дают разные слова, потому что каждая буква встречается один раз. Заменим «К» второй буквой «Т» — получим слово «ТОТ». Карточек по-прежнему три, мест три, и путей в дереве снова $6$. Но если выписать слова на листьях, получится ТОТ, ТТО, ОТТ, ОТТ, ТТО, ТОТ. Различных слов только три, каждое встретилось дважды.
Обратите внимание
Формула $P_n=n!$ считает расстановки различных предметов. Если среди букв есть одинаковые, $n!$ — это число путей дерева, но не число различных слов.
Одинаковые буквы склеивают листья дерева
Чтобы дерево можно было построить, пометим одинаковые буквы номерами, как будто это разные карточки: Т1, О, Т2. Все буквы стали различны, путей $3!=6$. Теперь сотрем номера. Листья Т1ОТ2 и Т2ОТ1 превращаются в одно и то же слово «ТОТ» — эти два листа склеиваются в одну группу.
Почему в каждой группе ровно два листа? Возьмем любое слово, например «ТТО». Буквы «Т» стоят на первом и втором местах. Помеченные карточки Т1 и Т2 можно положить на эти два места $2!=2$ способами — получим два листа с одним словом. Так для каждого слова: все группы одного размера, поэтому слов $6:2=3$.
То же рассуждение работает для любого числа одинаковых букв. В слове «КАРАВАН» $7$ букв: «А» — $3$ раза, остальные разные. Пометим А1, А2, А3 — путей $7!=5040$. В каждом слове три «А» занимают три места, и разложить по ним помеченные карточки можно $3!=6$ способами. Каждое слово стоит на $6$ листьях, а различных слов $\dfrac{7!}{3!}=\dfrac{5040}{6}=840$.
Определение
Перестановка с повторениями — расстановка в ряд $n$ предметов, среди которых есть одинаковые. Две такие расстановки различны, если хотя бы на одном месте в них стоят предметы разных видов.
Правило
Если среди $n$ предметов один повторяется $k$ раз, а остальные различны, то различных расстановок
Делим на $k!$, потому что столько перестановок одинаковых предметов между собой дают одно и то же слово.
$$\dfrac{n!}{k!}$$
Повторов несколько: делим на каждую группу одинаковых
Теперь в слове повторяются две буквы. Решавр считает, сколько слов можно получить из букв слова «МАМА».
Ошибка
Решавр рассуждает: «В слове $4$ буквы, значит, слов $4!=24$».
Проверим перечислением. Слово задается тем, на каких двух местах стоят буквы «М»: ММАА, МАМА, МААМ, АММА, АМАМ, ААММ. Различных слов $6$, а не $24$. Ответ $12$ (разделить на $2!$ один раз) тоже неверен: он учитывает повтор только одной буквы.
Где сломалось рассуждение: $4!$ — число путей дерева, в которых М1 и М2, А1 и А2 различаются. Решавр не склеил одинаковые листья, а повторяются обе буквы.
Почему группы по $4$? В слове «МАМА» две «М» на своих местах можно переставить $2!$ способами, и независимо от этого две «А» — тоже $2!$ способами. По правилу умножения одно слово дают $2! \cdot 2!=4$ пути, поэтому слов $\dfrac{4!}{2! \cdot 2!}=\dfrac{24}{4}=6$.
Формула перестановок с повторениями
Пусть $n$ предметов разбиты на $m$ видов: $n_1$ одинаковых предметов первого вида, $n_2$ — второго, …, $n_m$ — последнего, $n_1+n_2+\ldots+n_m=n$. Число различных расстановок в ряд
$$P(n_1,n_2,\ldots,n_m)=\dfrac{n!}{n_1!\,n_2!\ldots n_m!}$$
Почему это верно
Шаг 1. Пометим одинаковые предметы номерами — все $n$ станут различны, путей дерева $n!$.
Шаг 2. Возьмем любое слово. Предметы первого вида стоят в нем на $n_1$ местах, и помеченные карточки раскладываются по ним $n_1!$ способами; второго вида — $n_2!$ способами, и так далее. Выборы независимы, поэтому каждое слово дают ровно $n_1!\,n_2!\ldots n_m!$ путей.
Шаг 3. Все группы склеенных листьев одного размера. Значит, число слов равно $n!$, деленному на этот размер. Предмет, который встречается один раз, дает множитель $1!=1$ — его можно не писать.
Алгоритм
- Найдите число всех предметов $n$.
- Выпишите, сколько раз повторяется каждый предмет, и проверьте, что сумма повторов равна $n$.
- Разделите $n!$ на произведение факториалов повторов.
Пример 1
Задача. Сколько различных слов можно получить перестановкой букв слова: а) «ПАРАБОЛА»; б) «МАТЕМАТИКА»?
Решение. а) 1) $n=8$. 2) «А» — $3$ раза; «П», «Р», «Б», «О», «Л» — по одному разу; $3+5=8$. 3) $\dfrac{8!}{3!}=\dfrac{40320}{6}=6720$.
б) 1) $n=10$. 2) «М» — $2$ раза, «А» — $3$ раза, «Т» — $2$ раза, «Е», «И», «К» — по одному; $2+3+2+3=10$. 3) $\dfrac{10!}{2! \cdot 3! \cdot 2!}=\dfrac{3628800}{24}=151200$.
Проверка смысла: в а) ответ в $3!=6$ раз меньше $8!$ — каждое слово склеено из $6$ листьев.
Ответ: а) $6720$; б) $151200$.
Обратная задача
Скрыть
В слове одна буква повторяется дважды, остальные различны, и из него получили $60$ различных слов. Сколько в слове букв?
Число слов $\dfrac{n!}{2!}=60$, значит, $n!=120$. Подбираем: $5!=120$, поэтому букв $5$. Проверка: $\dfrac{120}{2}=60$.
Два вида предметов — это знакомые сочетания
Пусть предметы только двух видов, например шаги робота «вправо» и «вверх». Тогда слово задается тем, на какие места поставлены буквы первого вида. Выбрать места — значит выбрать группу без порядка, а это сочетания.
Пример 2
Задача. Робот идет по линиям клетчатой сетки из левого нижнего угла в правый верхний, делая только шаги вправо и вверх: $3$ шага вправо и $3$ шага вверх. Сколько существует различных путей?
Решение. 1) Запишем путь словом: П — шаг вправо, В — шаг вверх. Путь на рисунке — ППВПВВ. Различные пути — различные слова из трех букв П и трех букв В. 2) По формуле $P(3,3)=\dfrac{6!}{3! \cdot 3!}=\dfrac{720}{36}=20$. 3) Иначе: выберем $3$ места из $6$ для букв П, остальные займут В: $C_6^3=20$.
Ответ: $20$.
Сочетания как перестановки с повторениями
Выбрать $k$ предметов из $n$ — то же, что расставить в ряд $k$ отметок «взят» и $n-k$ отметок «не взят»:
$$C_n^k=P(k,n-k)=\dfrac{n!}{k!\,(n-k)!}$$
Ноль впереди и одинаковые буквы рядом
Цифры ведут себя как буквы, но у записи числа есть запрет: она не начинается с нуля. Удобно сначала посчитать все расстановки, а потом вычесть запрещенные.
Пример 3
Задача. Сколько различных четырехзначных чисел можно записать цифрами $0$, $1$, $1$, $2$, используя каждую ровно один раз?
Решение. 1) Все расстановки: «1» повторяется дважды, $\dfrac{4!}{2!}=12$. 2) Запрещенные — с нулем впереди. Ноль поставлен, остальные цифры $1$, $1$, $2$ расставляем $\dfrac{3!}{2!}=3$ способами. 3) $12-3=9$.
Проверка перебором первой цифры: если первая $1$, остаются $0$, $1$, $2$ — $3!=6$ чисел; если первая $2$, остаются $0$, $1$, $1$ — $\dfrac{3!}{2!}=3$ числа; $6+3=9$.
Ответ: $9$.
Ошибка
Решавр составляет пятизначные числа из цифр $0$, $0$, $1$, $1$, $2$ и считает: «$\dfrac{5!}{2! \cdot 2!}=30$ чисел».
Проверим. Среди $30$ расстановок есть записи $01102$, $00112$, $01120$ — они начинаются с нуля, а это не пятизначные числа. Таких расстановок: ноль поставлен первым, остальные цифры $0$, $1$, $1$, $2$ расставляются $\dfrac{4!}{2!}=12$ способами. Верно: $30-12=18$. Ошибка Решавра: он посчитал все расстановки и не вычел запрещенные.
Две одинаковые буквы рядом
Если две одинаковые буквы должны стоять рядом, а других таких букв нет, склейте их в один блок и считайте блок одним предметом. Множителя $2!$ внутри блока нет: буквы одинаковые.
Пример 4
Задача. Сколько различных слов можно получить перестановкой букв слова «ЗАКАЗ» так, чтобы две буквы «А» стояли рядом?
Решение. 1) Склеим две «А» в один блок, как в ВиС 9 склеивали в фишку двух друзей. Предметов стало $4$: блок «АА», «З», «З», «К». 2) Буква «З» повторяется дважды: $\dfrac{4!}{2!}=12$. 3) Внутри блока «АА» переставлять нечего: буквы одинаковые.
Проверка смысла: всего слов $\dfrac{5!}{2! \cdot 2!}=30$, и с «А» рядом — только часть из них.
Ответ: $12$.
Вероятность слова и правило «хотя бы один»
Склейка листьев помогает и в вероятности. Буквы слова «АННА» написали на четырех карточках, перемешали и выложили в ряд; каждый порядок четырех карточек равновероятен. Какова вероятность снова прочитать «АННА»?
Пример 5
Решение. 1) Карточки перемешивают так, что каждая из $4!=24$ раскладок физически разных карточек равновероятна: карточки различимы, поэтому раскладок ровно $24$, а равновероятность задана условием. 2) Различных слов $\dfrac{4!}{2! \cdot 2!}=6$, и каждое склеено ровно из $2! \cdot 2!=4$ раскладок. 3) Слову «АННА» благоприятны $4$ раскладки из $24$: $P=\dfrac{4}{24}=\dfrac16$.
Ответ: $\dfrac16$.
Группы склеенных листьев одного размера, поэтому при равновероятном перемешивании карточек различные слова тоже равновозможны: можно сразу считать $P=\dfrac{1}{6}$, где $6$ — число слов. Если бы группы были разными, так делать было бы нельзя.
Другой частый вопрос — «хотя бы один». Независимо бросают три правильные игральные кости; сколько исходов, в которых выпала хотя бы одна шестерка? Прямой подсчет требует разбирать случаи: одна шестерка, две, три. Проще перейти к противоположному событию $\overline{A}$ — «шестерок нет». На каждой кости тогда $5$ значений: $5^3=125$ исходов. Всего исходов $6^3=216$, значит, с хотя бы одной шестеркой $216-125=91$ исход и $P(A)=\dfrac{91}{216}$. Проверка по случаям: $75+15+1=91$.
Правило
Число исходов, где есть хотя бы один нужный элемент, равно числу всех исходов минус число исходов, где его нет:
Если все исходы равновозможны, вероятность события получают делением на $N$:
$$N(A)=N-N(\overline{A})$$$$P(A)=1-P(\overline{A})$$
Перед заданиями про коды договоримся: код длины $k$ — это $k$ цифр от $0$ до $9$, первая цифра тоже может быть нулем. Код $05$ допустим, а числом двузначным он не считается.
Вывод
Перестановки с повторениями встречаются везде, где есть одинаковые предметы: буквы в словах, цифры в кодах и числах, шаги на сетке, шары одного цвета. Чтобы вспомнить формулу, представьте дерево: пометьте одинаковые предметы — путей станет $n!$; сотрите номера — листья склеятся в равные группы по $n_1!\,n_2!\ldots n_m!$.
Часто задаваемые вопросы
Повтор не убирает отдельные листья, а склеивает их в группы одного размера: каждое слово встречается среди $n!$ путей одинаковое число раз. Когда все группы равны, число групп находят делением. Вычитание подходит для запретов вроде нуля впереди, где лишние расстановки нужно отбросить.
Можно не писать: $1!=1$, и деление на единицу ничего не меняет. Но при проверке полезно убедиться, что сумма всех повторов, включая единицы, равна $n$ — так легче не потерять букву.
В размещениях все $n$ предметов различны, а в ряд ставят только $k$ из них; дерево обрывается на $k$-м ярусе. В перестановках с повторениями в ряд ставят все предметы, но среди них есть одинаковые; дерево доходит до последнего яруса, а листья склеиваются.
Да, если предметов мало: перечислить все слова, как для «МАМА», или разобрать случаи по первой букве. Формула нужна, когда слов сотни и тысячи, а перечисление на малых числах — хороший способ ее проверить.
5
5
1
5