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

Пример.

Имеются три различные цифры: 1, 2 и 3.

Переставляя их, можно получить различные трёхзначные числа.

Если на первое место поставить цифру 1, то получим два числа: 123 и 132. Если на первое место поставить 2, то получим числа: 213 и 231. Ну, а если на первом месте окажется цифра 3, то получим числа: 312 и 321.

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

Определение:

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

Вернемся к примеру, и найдем число перестановок из трёх элементов:

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

Для выбора первого элемента существует три варианта. Для каждого из них есть два варианта выбора второго элемента. И третий элемент мы выбираем единственным способом.

Получим формулу числа перестановок из n элементов.

Пусть у нас есть n элементов. Тогда на первое место можно поставить один из них, то есть n вариантов. На второе место можно поставить любой из оставшихся n-1 элементов. На третье место можно поставить любой из оставшихся n -2 элементов. И так далее.

В результате получим такую формулу числа перестановок из n элементов:

Расположим множители в порядке возрастания:

Для записи произведения первых n натуральных чисел, есть специальное обозначение:

Например:

Пример.

Найти число перестановок из 5 элементов:

Пример.

Найти число перестановок из 7 элементов:

Пример.

Найти число перестановок из 10 элементов:

Пример.

Определить, делится ли число 18! на 30, на 54 и на 625.

Запишем и проверим, получится ли в результате целое число:

Получили, что числитель и знаменатель дроби можно сократить на 5 и на 6. Очевидно, в результате получим целое число.

Получили, что числитель и знаменатель можно сократить на 6 и на 9. Полученное произведение равно целому числу.

Получили, что в результате сокращения в знаменателе остаётся 5. Значит число 18! не делится на 625 нацело.

Пример.

Вычислить значения выражений, содержащих факториал:

1.                Вычислить:

Представим числитель и знаменатель в виде произведения:

Теперь легко увидеть, что дробь можно сократить, вычислим:

2.                Вычислить:

Представим числитель и знаменатель в виде произведения, сократим дробь:

3.                Вычислим:

Представим каждый факториал в виде произведения, вычислим:

Нашли значения выражений, содержащих знак факториала.

Пример.

Сколько 6 - ых чисел можно составить, используя цифры 1, 3, 5, 7, 8 и 9, не повторяя их?

Решение задачи сводиться к нахождению числа перестановок из 6 элементов.

Применим формулу:

Сколько 6 - ых чисел можно составить, используя цифры 0, 3, 5, 7, 8 и 9, не повторяя их?

Переставляя 6 данных цифр, мы получим 720 различных вариантов. Но ведь число не может начинаться с 0. Тогда мы должны вычесть все случаи, когда 0 записан на первом месте. На первом месте у нас 0, а остальные 5 цифр могут располагаться в любом порядке и количество таких вариантов, равно числу перестановок из 5 элементов.

Найдём количество таких случаев:

Получим:

Пример.

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

Будем рассматривать все простые карандаши как 1. Тогда нам нужно разложить 6 объектов. Найдём сколькими способами это можно сделать. Найдем число перестановок из 6 элементов:

В каждом из полученных способов четыре простых карандаша тоже можно разложить по-разному, получим:

Для нахождения общего числа способов: