bulgakov

12. Перестановки с повторяющимися элементами

Если среди букв слова есть одинаковые, то разных слов получается меньше, чем r!r! (где rr — число букв в слове): каждое слово мы посчитали столько раз, сколькими способами можно переставить одинаковые буквы между собой. Поэтому делим: P(d1,…,dn)=r!d1! d2!⋯dn!P(d_1,\dots,d_n)=\dfrac{r!}{d_1!\,d_2!\cdots d_n!}.

Что пригодится из прошлого: перестановки и факториал — число расстановок различных элементов; выборки — кратность элемента. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Самый маленький пример: слово «ААБ»

В слове «ААБ» две одинаковые буквы «А» и одна «Б». Сколько разных слов получается, если переставлять эти буквы всеми способами? Если бы все три буквы были разными, их можно было бы расставить 3!=63!=6 способами. Но одинаковые «А» неразличимы, и после их перестановки слово не меняется.

Чтобы разобраться, пометим одинаковые буквы номерами: А1,А2,БА_1,А_2,Б. Теперь все три буквы различны, и расстановок 3!=63!=6. Сотрём номера и посмотрим, какие слова получились:

Схема
А₁А₂Б, А₂А₁Б    →  ААБ
А₁БА₂, А₂БА₁    →  АБА
БА₁А₂, БА₂А₁    →  БАА

Каждое слово появилось дважды (2!2! — число способов пометить две «А»), поэтому слов 6:2=36:2=3.

Теперь побольше: слово «МАМА»

В слове «МАМА» две буквы «М» и две буквы «А». Пометим одинаковые буквы: М1,М2,А1,А2М_1,М_2,А_1,А_2. Теперь все четыре буквы различны, и расстановок 4!=244!=24. Сотрём номера и посмотрим, какие слова получились:

  • ААММ — А₁А₂М₁М₂, А₁А₂М₂М₁, А₂А₁М₁М₂, А₂А₁М₂М₁
  • АМАМ — А₁М₁А₂М₂, А₁М₂А₂М₁, А₂М₁А₁М₂, А₂М₂А₁М₁
  • АММА — А₁М₁М₂А₂, А₁М₂М₁А₂, А₂М₁М₂А₁, А₂М₂М₁А₁
  • МААМ — М₁А₁А₂М₂, М₁А₂А₁М₂, М₂А₁А₂М₁, М₂А₂А₁М₁
  • МАМА — М₁А₁М₂А₂, М₁А₂М₂А₁, М₂А₁М₁А₂, М₂А₂М₁А₁
  • ММАА — М₁М₂А₁А₂, М₁М₂А₂А₁, М₂М₁А₁А₂, М₂М₁А₂А₁

Каждый пункт — одно настоящее слово. Помеченных расстановок, которые в него превращаются, ровно четыре. Пунктов шесть: 24:4=624:4=6 слов.

Откуда берётся число четыре. Возьмём любое слово, например «МАМА». Две буквы «М» можно пометить номерами двумя способами (М1М_1 слева и М2М_2 справа или наоборот): 2!2!. Две буквы «А» — тоже двумя способами: 2!2!. Расставляем метки независимо, поэтому по правилу произведения (числа способов независимых шагов перемножаются) получаем 2!⋅2!=42!\cdot2!=4 помеченных варианта. Так у каждого слова: например, «ААММ» тоже превращается из четырёх помеченных расстановок.

Общий случай

Пусть алфавит A={a1,a2,…,an}A=\{a_1,a_2,\dots,a_n\}, а нужны слова длины rr, в которых буква aia_i встречается ровно did_i раз (1≤i≤n1\le i\le n), причём

d1+d2+⋯+dn=r.d_1+d_2+\cdots+d_n=r.

Число таких слов обозначим P(d1,d2,…,dn)P(d_1,d_2,\dots,d_n).

Теорема.

P(d1,d2,…,dn)=r!d1! d2!⋯dn!.\boxed{P(d_1,d_2,\dots,d_n)=\frac{r!}{d_1!\,d_2!\cdots d_n!}}.

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

W=a1a1…a1⏟d1  a2a2…a2⏟d2  …  anan…an⏟dn.W=\underbrace{a_1a_1\ldots a_1}_{d_1}\;\underbrace{a_2a_2\ldots a_2}_{d_2}\;\ldots\;\underbrace{a_na_n\ldots a_n}_{d_n}.

Все нужные слова получаются перестановками букв слова WW: у всех них один и тот же набор букв — ровно did_i букв aia_i. Если считать все буквы различными (пометить одинаковые), перестановок r!r!. Теперь возьмём любое нужное слово. Метки для d1d_1 одинаковых букв a1a_1 можно расставить d1!d_1! способами, для d2d_2 букв a2a_2 — d2!d_2! способами и так далее, независимо друг от друга. Каждая такая расстановка меток — одна из r!r! помеченных расстановок, и стирание меток возвращает именно это слово. Поэтому каждое слово «получено» ровно d1! d2!⋯dn!d_1!\,d_2!\cdots d_n! раз среди r!r! помеченных расстановок (правило произведения). Разные слова получаются из разных помеченных расстановок: после стирания меток каждая расстановка даёт ровно одно слово. Поэтому все r!r! помеченных расстановок разбиты на группы по d1! d2!⋯dn!d_1!\,d_2!\cdots d_n! штук, по одной группе на каждое слово. Значит,

P(d1,…,dn)⋅d1! d2!⋯dn!=r!,P(d_1,\dots,d_n)\cdot d_1!\,d_2!\cdots d_n!=r!,

откуда и следует формула. □\square

Что здесь делит и почему. Мы сначала посчитали с запасом (r!r! помеченных вариантов), а потом разделили на то, сколько раз при этом посчиталось каждое слово. Это похоже на формулу ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A\cup B|=|A|+|B|-|A\cap B| из главы про число элементов объединения: там общие элементы посчитались дважды, и лишнее вычитали; здесь каждое слово посчиталось несколько раз, и лишнее убирают делением.

Проверка частных случаев.

  • Все di=1d_i=1 (r=nr=n, все буквы разные): формула даёт n!1⋅1⋯1=n!\dfrac{n!}{1\cdot1\cdots1}=n! — обычные перестановки.
  • Если буква не встречается (di=0d_i=0), множитель 0!=10!=1 ничего не меняет.
  • «МАМА»: r=4r=4, dМ=2d_{\text{М}}=2, dА=2d_{\text{А}}=2: 4!2! 2!=244=6\dfrac{4!}{2!\,2!}=\dfrac{24}{4}=6 — как в списке.

Примеры

1. «КОЛОКОЛ». Буквы: К — 22, О — 33, Л — 22; всего 77. Число слов

7!2! 3! 2!=504024=210.\frac{7!}{2!\,3!\,2!}=\frac{5040}{24}=210.

2. «МАТЕМАТИКА». М — 22, А — 33, Т — 22, Е, И, К — по одной; всего 1010 букв.

10!2! 3! 2!=3 628 80024=151 200.\frac{10!}{2!\,3!\,2!}=\frac{3\,628\,800}{24}=151\,200.

3. Нули и единицы. Сколько существует двоичных слов длины 88, в которых ровно три единицы? Нулей 55:

P(3,5)=8!3! 5!=56.P(3,5)=\frac{8!}{3!\,5!}=56.

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

Частые ошибки

  • Забыть поделить. r!r! считает помеченные буквы; одинаковые буквы нужно «склеить».
  • Делить на (d1+⋯+dn)!(d_1+\dots+d_n)! вместо произведения d1!⋯dn!d_1!\cdots d_n!. Делят на произведение факториалов кратностей по отдельности.
  • Не проверить, что d1+⋯+dn=rd_1+\dots+d_n=r. Иначе в числителе не то число.
  • Считать одинаковые буквы различными. В слове «ОКНО» две «О»; слов 4!2!=12\dfrac{4!}{2!}=12, а не 4!4!.

Проверь себя

1. Сколько различных слов можно получить перестановкой букв слова «ОКНО»?

Решение

Буквы: О — 22, К — 11, Н — 11, всего 44. 4!2! 1! 1!=12\dfrac{4!}{2!\,1!\,1!}=12.

2. Сколько различных слов можно получить из букв слова «ПОПОЛАМ»?

Решение

П — 22, О — 22, Л, А, М — по одной; всего 77 букв. 7!2! 2!=50404=1260\dfrac{7!}{2!\,2!}=\dfrac{5040}{4}=1260.

3. Сколько существует слов из букв слова «БАНАН»?

Решение

Б — 11, А — 22, Н — 22; всего 55. 5!1! 2! 2!=1204=30\dfrac{5!}{1!\,2!\,2!}=\dfrac{120}{4}=30.

4. Сколькими способами можно разложить в ряд три красных одинаковых шарика и пять синих одинаковых?

Решение

Слово из трёх букв «к» и пяти букв «с»: 8!3! 5!=56\dfrac{8!}{3!\,5!}=56.

Итог

  • Если буквы повторяются, слов меньше, чем r!r!: каждое слово посчитано d1! d2!⋯dn!d_1!\,d_2!\cdots d_n! раз.
  • Формула: P(d1,…,dn)=r!d1! d2!⋯dn!P(d_1,\dots,d_n)=\dfrac{r!}{d_1!\,d_2!\cdots d_n!}, где d1+⋯+dn=rd_1+\dots+d_n=r.
  • Приём: пометить одинаковые буквы, посчитать расстановки, разделить на число способов пометки.
  • Частный случай из двух букв (нули и единицы) приведёт нас к сочетаниям.
ПрактикаЗагружаем тест…