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

Пример 11

 

Проказница-Мартышка,

Осел, Козел да косолапый Мишка

Затеяли сыграть Квартет.

(Иван Крылов, «Квартет»)

Вы прекрасно помните, чем эта затея закончилась. В каком порядке ни садились наши горе-исполнители, музыки у них не получилось. Как заметил Соловей, «А вы, друзья, как ни садитесь, всё в музыканты не годитесь».

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

Решение.

Пусть для наших четырех исполнителей есть четыре места: обозначим их по сторонам света

С, В, Ю, З.

Сколькими способами может выбрать себе место косолапый Мишка?

Если он уже занял свое место, то сколькими способами может найти себе место Мартышка?

Сколько теперь осталось вариантов для Козла?

А Осел может только занять единственное оставшееся место.

Я думаю, вы догадались, что Мишка может выбирать из четырех вариантов, Мартышка – из трех, Козел – из двух, а Осел садится на единственное оставленное ему место. Все эти числа надо перемножить (наверное, вы не забыли правило произведения):

4∙3∙2∙1 = 24.

Пример 12

Часовой сонного царства.

Группа туристов из 8 человек решила ночью охранять свой лагерь. Группа спит с 23.00 до 7.00, и каждый из туристов дежурит по часу.

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

А сколько теперь кандидатов на дежурство во вторую смену? Третью? И т.д.?

Решение.

Дежурного на первый час можно назначить 8 способами, на второй – 7 способами, на третий – шестью и т.д. А всего способов распределить дежурных будет

8∙7∙6∙5∙4∙3∙2∙1 = 40320.

Вы не забыли, как записывать такие произведения кратко?

4∙3∙2∙1 =4! = 24.8∙7∙6∙5∙4∙3∙2∙1 =8!=40320 .

Обобщение. Вывод рабочей формулы.

Сформулируем общую задачу. Пусть у вас есть множество из n элементов. Сколькими различными способами можно расположить их по порядку?

Первый элемент можно выбрать n способами, второй – (n-1) способом, третий -

(n-2) способами и т.д. Тогда последний, n-й элемент можно выбрать только 1 способом. Тогда, чтобы найти число способов, которым можно выбрать все k элементов, нужно перемножить все эти числа:

(3).

Это число называется числом перестановок из n элементов.

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

(4).

– Что за бред? – скажете вы. Факториал нуля? Произведение всех чисел от единицы до … нуля?

Дело в том, что принято считать 0! = 1. Почему именно так? Вспомним, что такое факториал:

А теперь уберем мысленно последний множитель. Что останется? (n-1)! Значит:

(5).

Запишем это равенство для n = 1:

1! = 0!∙1

Так как 1! = 1, то и получается 0! = 1.

Вернемся к нашей формуле для размещений из n по n и подставим туда 0! = 1:

Что и требовалось доказать.