Перестановки.

Тридцать три буквы русского алфавита принято располагать от А до Я. Можно расположить в обратном порядке: от Я до А. Каждое расположение тридцати трех букв в определенном порядке называется их перестановкой. Количество всех таких перестановок выражается тридцатисемизначным числом.

Перестановки можно образовывать из элементов любого конечного множества.

Множество из одного элемента можно упорядочить одним-единственным образом. Множество из двух элементов А и Б – двумя способами: АБ и БА.

Множество из трех элементов: А, Б, В – шестью способами: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА.

Установленный в конечном множестве порядок элементов называют перестановкой.

Число перестановок из n элементов обозначают через . Мы нашли, что

Вычислять удобно последовательно, пользуясь рекуррентной формулой:

. (1)

Докажем ее. Пусть требуется упорядочить множество из n элементов. Какой-то из этих элементов придется поставить на последнее, n-е место. Этот элемент можно выбрать n различными способами. Если он уже выбран, то останется n-1 элемент. Ими придется занять первые n-1 мест. Это можно сделать способами ( по смыслу ). Всего получается способов упорядочить множество из n элементов, т.е. .

По формуле (1) последовательно получаем:

Например, 7 гостей можно рассадить по 7 местам за столом 5040 способами.

Из формулы (1) вытекает, что (число перестановок из n элементов) равно произведению первых n натуральных чисел:

. (2)

Для произведения первых n натуральных чисел принято специальное обозначение: n! (читается «n-факториал»). Пользуясь этим обозначением, формулу (2) можно записать в виде

n! (3)

Для дальнейшего удобно считать, что пустое множество можно упорядочить только одним способом, т.е. . Тогда формулой (1) можно пользоваться и при n=1:

.

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

=362880.

Формула (3) применима для подсчета числа перестановок элементов множеств, т.е. когда элементы совокупности различные. Если же некоторые объекты в перестановках повторяются, то применяется формула для числа перестановок с повторениями.

Число перестановок элементов из такой совокупности будет меньше, чем из множества, где число элементов то же.

Пример: все перестановки для набора чисел (5,1,5): 515, 551, 155; все перестановки для набора чисел (5,1,2): 512, 521, 125, 152, 215, 251. В первом и втором наборах по три элемента, но там, где элементы повторяются, число перестановок меньше. Следовательно, число перестановок зависит от количества повторяющихся элементов.

В общем виде задача формулируется так: имеется n элементов, которые разбиты на k различных групп с одинаковыми элементами в первой группе, одинаковыми элементами во второй группе и одинаковыми элементами в последней, k-й группе. Сколько различных перестановок из n элементов, разбитых на k групп можно составить?

Теорема. Число различных перестановок с повторениями определяется по формуле:

. (4)

Пример: разобьем набор чисел предыдущего примера (5,1,5) на группы: =2 – количество 5-ок и =1 – количество 1-ниц. Тогда по формуле (4): =3.

Задачи.

1. Сколько различных трехцветных флагов с тремя горизонтальными полосами можно получить, если использовать красный, белый, синий цвета?

2. Сколькими способами можно составить список из 9 студентов?

3. В пассажирском поезде 14 вагонов. Сколькими способами можно распределить по вагонам 14 проводников, если за каждым вагоном закрепляется один проводник?

4. Найти значение выражения:

а) 8! +9!; б) ; в) .

5.Сократить дробь:

а) ; б) ; в) .

6. Из цифр 0,1,2,3 составлены всевозможные четырехзначные числа так, что в каждом числе нет одинаковых цифр. Сколько получилось чисел?

7. Из цифр 1,2,3,4,5 составлены всевозможные пятизначные числа без повторения цифр. Выясните, сколько среди этих пятизначных чисел таких, которые:

а) начинаются цифрой 3;

б) не начинаются с цифры 5;

в) начинаются с 54;

г) не начинаются с 543.

8. Определить, сколько различных слов можно составить из слова «литература».