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

Простейшими комбинациями, которые можно составить из элементов конечного множества, являются перестановки.

Рассмотрим пример. Пусть имеются три карандаша: синий, красный, желтый.  Обозначим их С, К, Ж. Эти карандаши можно разложить по-разному.

Если первым положить синий карандаш, то возможны такие варианты расположения карандашей: синий-желтый-красный и синий-красный-желтый.

Если положить красный карандаш первым, то возможными являются такие расположения: красный-синий-желтый и красный-желтый-синий.

И, наконец, если первым положить желтый карандаш, то можно получить такие расположения: желтый-синий-красный и желтый-красный-синий.

Каждое из этих расположений называют перестановкой из трех элементов.

Перестановкой из трех элементов называется каждое расположение этих элементов в определенном порядке.

Число перестановок из эн элементов обозначают Пэ из эн.

В рассмотренном примере мы установили, что количество перестановок из трех элементов равно шести. Чтобы найти количество перестановок из трех элементов, можно не выписывать их, а воспользоваться комбинаторным правилом умножения. Будем рассуждать так. На первое место можно поставить любой из трех элементов. Для каждого выбора первого элемента существует две возможности выбора второго элемента из оставшихся двух элементов. И, наконец, для каждого выбора первых двух элементов остается единственная возможность выбора третьего элемента. Значит, число перестановок из трех элементов равно три умноженное на два и на один, то есть шесть.

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

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

Расположив множители в порядке возрастания, получим следующую формулу…

Для произведения первых эн натуральных чисел используют специальное обозначение: эн факториал.

Например, три факториал равно произведению один, два и три равно шесть; шесть факториал равно произведению один, два, три, четыре, пять, шесть и равно семьсот двадцать. По определению считают, что один факториал равно один.

Таким образом, число всевозможных перестановок из эн элементов равно эн факториал.

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

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

Второй пример. Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр ноль, один, два, три?

Из цифр ноль, один, два, три можно получить пэ из четырех перестановок. Из них надо исключить те перестановки, которые начинаются с нуля, так как натуральное число не может начинаться с цифры ноль. Число таких перестановок равно Пэ из трех. Значит, искомое количество четырехзначных чисел равно разности Пэ из четырех.. и Пэ из трех….. Получаем восемнадцать.

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

Сначала будем рассматривать красные тарелки, как одну тарелку. Тогда нужно расставить не девять, а шесть тарелок. Это можно сделать Пэ из шести способами. В каждой из полученных комбинаций можно выполнить Пэ из четырех перестановок тарелок. Значит, искомое количество способов расположения тарелок на полке равно произведению Пэ из шести и Пэ из четырех.

Получаем семнадцать тысяч двести восемьдесят способов.