Permutations

Permutations

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

'’Перестановками из $n$ элементов’’ называют размещения без повторений из $n$ элементов, в которые входят все элементы.

Обозначаются $P_n = A_n^n = n \cdot (n - 1) \cdot … \cdot 2 \cdot 1 = n| $ | |### Задачи Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не били друг друга?

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

• $a_1$ - номер поля на первой горизонтали
• $a_2$ - номер поля на второй горизонтали
• …

• $a_8$ - номер поля на восьмой горизонтали

• $(a_1, …, a_8)$ - некоторая перестановка $(1, …, 8)$
• $P_8 = 8| = 40320$ | |

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

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

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

Число элементов в каждой перестановке равно $n = n_1 + n_2 + … + n_k$ Если бы все элементы были разными, то у нас было бы $n| $ перестановок. | |Но из-за того, что элементы совпадают, получается меньшее количество перестановок.

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

$\underbrace{aa \ .. \ a}{n_1} \ \underbrace{bb \ .. \ b}{n_2} \ … \ \underbrace{xx \ .. \ x}_{n_k}$

• Элементы первого типа можно переставить друг с другом $n_1

  $ способами, но т.к. эти элементы одинаковы, то это не изменит перестановку.

  - Permutations первого, второго, $k$-того типов можно делать независимо друг от друга. Поэтому по правилу произведения элементы этой перестановки можно переставить друг с другом $n_1

  \cdot n_2! \cdot … \cdot n_k!$ способами так, что она останется неизменной.

  - Следовательно, $P(n_1, n_2, …, n_k) = \frac{n

  }{n_1! n_2! … n_k!}$

  ### Задача

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

$P(4, 3, 1, 1) = \frac{9| }{4! \cdot 3! \cdot 1! \cdot 1!} = 2520$ | |## Sources

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