Permutations

Если брать размещения, в которые входят все [math]n[/math] предметов, то они могут различаться только порядком.

Перестановками из [math]n[/math] элементов называют размещения без повторений из [math]n[/math] элементов, в которые входят все элементы.

Обозначаются [math]P_n = A_n^n = n \cdot (n - 1) \cdot ... \cdot 2 \cdot 1 = n![/math]

Задачи

Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не били друг друга?

При таком расположении на каждой горизонтали и вертикали стоит по одной ладье

  • [math]a_1[/math] - номер поля на первой горизонтали
  • [math]a_2[/math] - номер поля на второй горизонтали
  • ...
  • [math]a_8[/math] - номер поля на восьмой горизонтали
  • [math](a_1, ..., a_8)[/math] - некоторая перестановка [math](1, ..., 8)[/math]
  • [math]P_8 = 8! = 40320[/math]


Permutations с повторениями

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

Пусть имеется [math]n[/math] предметов [math]k[/math] различных типов. Сколько перестановок можно сделать из [math]n_1[/math] элементов первого типа, [math]n_2[/math] элементов второго типа, ..., [math]n_k[/math] элементов [math]k[/math]-того типа?

Число элементов в каждой перестановке равно [math]n = n_1 + n_2 + ... + n_k[/math] Если бы все элементы были разными, то у нас было бы [math]n![/math] перестановок.

Но из-за того, что элементы совпадают, получается меньшее количество перестановок.


Рассмотрим перестановку

[math]\underbrace{aa \ .. \ a}_{n_1} \ \underbrace{bb \ .. \ b}_{n_2} \ ... \ \underbrace{xx \ .. \ x}_{n_k}[/math]

  • Элементы первого типа можно переставить друг с другом [math]n_1![/math] способами, но т.к. эти элементы одинаковы, то это не изменит перестановку.
  • Permutations первого, второго, [math]k[/math]-того типов можно делать независимо друг от друга. Поэтому по правилу произведения элементы этой перестановки можно переставить друг с другом [math]n_1! \cdot n_2! \cdot ... \cdot n_k![/math] способами так, что она останется неизменной.
  • Следовательно, [math]P(n_1, n_2, ..., n_k) = \frac{n!}{n_1! n_2! ... n_k!}[/math]

Задача

Сколько перестановок можно сделать из букв слова "Миссисипи"?

[math]P(4, 3, 1, 1) = \frac{9!}{4! \cdot 3! \cdot 1! \cdot 1!} = 2520[/math]

Sources

  • Виленкин Н.Я. Комбинаторика. М., Наука, 1969.