Перестановки без повторений

Перестановками из n элементов называются различные упорядочения множества  X .
Из этого определения следует, что две перестановки отличаются только порядком элементов и их можно рассматривать как частный случай размещений.
Формула: Число различных перестановок без повторений вычисляется по формуле

$$P_n=n!=n \cdot (n-1) \cdot (n-2) \cdot ...\cdot 2 \cdot 1$$

Заметим, что в любую перестановку входят все элементы множества Х, причём ровно по одному разу. То есть перестановки одна от другой отличаются только порядком следования элементов и могут получиться одна из другой перестановкой элементов (отсюда и название).

 Пример. Сколькими способами можно разместить на полке 5 книг?

Решение. Способов размещения книг на полке существует столько, сколько существует различных перестановок из пяти элементов: $P_5=5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ способов.

Замечание. Формулу перестановок всегда можно заменить более универсальным правилом произведения

Задачи:

1. Сколькими способами могут встать в очередь в билетную кассу: 1) 3 человека; 2) 5 человек?

Решение.

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

Три человека могут встать в очередь  $Р_3 = 3! = 6$  различными способами.

Ответ: 1) 6 способов; 2) 120 способов.

2. Сколькими способами 4 человека могут разместиться на четырехместной скамейке?

Решение.

Количество человек равно количеству мест на скамейке, поэтому количество способов размещения равно числу перестановок из 4 элементов:  $Р_4 = 4! = 24$.

Можно рассуждать по правилу произведения: для первого человека можно выбрать любое из 4 мест, для второго - любое из 3 оставшихся, для третьего - любое из 2 оставшихся, последний займет 1 оставшееся место; всего есть  $4*3*2*1= 24$  разных способов Размещения 4 человек на четырехместной скамейке.

Ответ: 24 способами.

3. У Вовы на обед - первое, второе, третье блюда и пирожное. Он обязательно начнет с пирожного, а все остальное съест в произвольном порядке. Найдите число возможных вариантов обеда.

 Решение.

После пирожного Вова может выбрать любое из трех блюд, затем - из двух, и закончить оставшимся. Общее число возможных вариантов обеда:  $P_3=3!=6$.

Ответ: 6.

 4. Сколькими способами можно с помощью букв К, L, М, Н обозначить вершины четырехугольника?

Решение.

Будем считать, что вершины четырехугольника пронумерованы, за каждой закреплен постоянный номер. Тогда задача сводится к подсчету числа разных способов расположения 4 букв на 4 местах (вершинах), т. е. к подсчету числа различных перестановок: $Р_4 = 4! =24$ способа.

Ответ: 24 способа.

5.  Четыре друга купили билеты в кино: на 1-е и 2-е места в первом ряду и на 1-е и 2-е места во втором ряду. Сколькими способами друзья могут занять эти 4 места в кинотеатре?

Решение.

Четыре друга могут занять 4 разных места  $Р_4 = 4! = 24$  различными способами.

Ответ: 24 способа.

6.  Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов может он выбрать?

Решение.

Под маршрутом следует понимать порядок посещения курьером учреждений. Пронумеруем учреждения номерами от 1 до 7, тогда маршрут будет представляться последовательностью из 7 Цифр, порядок которых может меняться. Количество маршрутов равно числу перестановок из 7 элементов:  $Р_7= 7! = 5 040$.

Ответ: 5 040 маршрутов.

7.  Сколько существует выражений, тождественно равных произведению abcde, которые получаются из него перестановкой множителей?

Решение.

Дано произведение пяти различных сомножителей abcde, порядок которых может меняться (при перестановке множителей произведение не меняется).

Всего существует  $Р_5 = 5! = 120$  различных способов расположения пяти множителей; один из них (abcde) считаем исходным, остальные 119 выражений тождественно равны данному.

Ответ: 119 выражений.

8.  Ольга помнит, что телефон подруги оканчивается цифрами 5, 7, 8, но забыла, в каком порядке эти цифры следуют. Укажите наибольшее число вариантов, которые ей придется перебрать, чтобы дозвониться подруге.

Решение.

Три последних цифры телефонного номера могут быть расположены в одном из  $Р_3 =3! =6$  возможных порядков, из которых только один верный. Ольга может сразу набрать верный вариант, может набрать его третьим, и т. д. Наибольшее число вариантов ей придется набрать, если правильный вариант окажется последним, т. е. шестым.

Ответ: 6 вариантов.

Перестановки с повторением
Пусть дано множество $X = {x_1, x_2, …, x_r}$. Составим кортеж длиной $n$, в который элемент $x_1$ входит $n_1$ раз, $x_2 - n_2$ раза,$x_r - n_r$ раз. Назовем составом этого кортежа новый кортеж $(n_1, n_2, n_r)$. Кортежи данного состава называют перестановками с повторением из $n_1$ элементов $х_1$, $n_2$ элементов $х_2,n_r$ элементов $x_r$. Их число выражается формулой

$$P_n(n_1,n_2,...,n_r)=\frac{n!}{n_1! \cdot n_2! \cdot ...\cdot n_r! }$$

где  $n_1+n_2+...+n_r=n$