12. Перестановки с повторяющимися элементами
Если среди букв слова есть одинаковые, то разных слов получается меньше, чем (где — число букв в слове): каждое слово мы посчитали столько раз, сколькими способами можно переставить одинаковые буквы между собой. Поэтому делим: .
Что пригодится из прошлого: перестановки и факториал — число расстановок различных элементов; выборки — кратность элемента. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Самый маленький пример: слово «ААБ»
В слове «ААБ» две одинаковые буквы «А» и одна «Б». Сколько разных слов получается, если переставлять эти буквы всеми способами? Если бы все три буквы были разными, их можно было бы расставить способами. Но одинаковые «А» неразличимы, и после их перестановки слово не меняется.
Чтобы разобраться, пометим одинаковые буквы номерами: . Теперь все три буквы различны, и расстановок . Сотрём номера и посмотрим, какие слова получились:
А₁А₂Б, А₂А₁Б → ААБ
А₁БА₂, А₂БА₁ → АБА
БА₁А₂, БА₂А₁ → БАА
Каждое слово появилось дважды ( — число способов пометить две «А»), поэтому слов .
Теперь побольше: слово «МАМА»
В слове «МАМА» две буквы «М» и две буквы «А». Пометим одинаковые буквы: . Теперь все четыре буквы различны, и расстановок . Сотрём номера и посмотрим, какие слова получились:
- ААММ — А₁А₂М₁М₂, А₁А₂М₂М₁, А₂А₁М₁М₂, А₂А₁М₂М₁
- АМАМ — А₁М₁А₂М₂, А₁М₂А₂М₁, А₂М₁А₁М₂, А₂М₂А₁М₁
- АММА — А₁М₁М₂А₂, А₁М₂М₁А₂, А₂М₁М₂А₁, А₂М₂М₁А₁
- МААМ — М₁А₁А₂М₂, М₁А₂А₁М₂, М₂А₁А₂М₁, М₂А₂А₁М₁
- МАМА — М₁А₁М₂А₂, М₁А₂М₂А₁, М₂А₁М₁А₂, М₂А₂М₁А₁
- ММАА — М₁М₂А₁А₂, М₁М₂А₂А₁, М₂М₁А₁А₂, М₂М₁А₂А₁
Каждый пункт — одно настоящее слово. Помеченных расстановок, которые в него превращаются, ровно четыре. Пунктов шесть: слов.
Откуда берётся число четыре. Возьмём любое слово, например «МАМА». Две буквы «М» можно пометить номерами двумя способами ( слева и справа или наоборот): . Две буквы «А» — тоже двумя способами: . Расставляем метки независимо, поэтому по правилу произведения (числа способов независимых шагов перемножаются) получаем помеченных варианта. Так у каждого слова: например, «ААММ» тоже превращается из четырёх помеченных расстановок.
Общий случай
Пусть алфавит , а нужны слова длины , в которых буква встречается ровно раз (), причём
Число таких слов обозначим .
Теорема.
Доказательство. Рассмотрим слово, в котором все буквы стоят группами:
Все нужные слова получаются перестановками букв слова : у всех них один и тот же набор букв — ровно букв . Если считать все буквы различными (пометить одинаковые), перестановок . Теперь возьмём любое нужное слово. Метки для одинаковых букв можно расставить способами, для букв — способами и так далее, независимо друг от друга. Каждая такая расстановка меток — одна из помеченных расстановок, и стирание меток возвращает именно это слово. Поэтому каждое слово «получено» ровно раз среди помеченных расстановок (правило произведения). Разные слова получаются из разных помеченных расстановок: после стирания меток каждая расстановка даёт ровно одно слово. Поэтому все помеченных расстановок разбиты на группы по штук, по одной группе на каждое слово. Значит,
откуда и следует формула.
Что здесь делит и почему. Мы сначала посчитали с запасом ( помеченных вариантов), а потом разделили на то, сколько раз при этом посчиталось каждое слово. Это похоже на формулу из главы про число элементов объединения: там общие элементы посчитались дважды, и лишнее вычитали; здесь каждое слово посчиталось несколько раз, и лишнее убирают делением.
Проверка частных случаев.
- Все (, все буквы разные): формула даёт — обычные перестановки.
- Если буква не встречается (), множитель ничего не меняет.
- «МАМА»: , , : — как в списке.
Примеры
1. «КОЛОКОЛ». Буквы: К — , О — , Л — ; всего . Число слов
2. «МАТЕМАТИКА». М — , А — , Т — , Е, И, К — по одной; всего букв.
3. Нули и единицы. Сколько существует двоичных слов длины , в которых ровно три единицы? Нулей :
Эту же формулу мы ещё раз получим в главе про сочетания: слово из трёх единиц и пяти нулей однозначно задаётся выбором трёх мест из восьми, на которых стоят единицы.
Частые ошибки
- Забыть поделить. считает помеченные буквы; одинаковые буквы нужно «склеить».
- Делить на вместо произведения . Делят на произведение факториалов кратностей по отдельности.
- Не проверить, что . Иначе в числителе не то число.
- Считать одинаковые буквы различными. В слове «ОКНО» две «О»; слов , а не .
Проверь себя
1. Сколько различных слов можно получить перестановкой букв слова «ОКНО»?
Решение
Буквы: О — , К — , Н — , всего . .
2. Сколько различных слов можно получить из букв слова «ПОПОЛАМ»?
Решение
П — , О — , Л, А, М — по одной; всего букв. .
3. Сколько существует слов из букв слова «БАНАН»?
Решение
Б — , А — , Н — ; всего . .
4. Сколькими способами можно разложить в ряд три красных одинаковых шарика и пять синих одинаковых?
Решение
Слово из трёх букв «к» и пяти букв «с»: .
Итог
- Если буквы повторяются, слов меньше, чем : каждое слово посчитано раз.
- Формула: , где .
- Приём: пометить одинаковые буквы, посчитать расстановки, разделить на число способов пометки.
- Частный случай из двух букв (нули и единицы) приведёт нас к сочетаниям.
