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

Четыре горе – музыканта из баcни Крылова долго пересаживались с места на место. В ходе этого творческого поиска осёл внёс предложение: «Мы, верно, уж поладим, коль рядом сядем». Попробовали – не помогло. Но в ряд можно сесть разными способами. Определим число всевозможных вариантов расположения четырёх музыкантов в ряд. Обозначим музыкантов следующим образом: А – Мартышка, В – Осёл, С – Козёл, Д – Мишка. Тогда варианты расположения будут такими:

АВСД, АВДС, АДВС, АДСВ, АСДВ, АСВД,

САВД, САДВ, СДАВ, СДВА, СВДА, СВАД,

ВСАД, ВСДА, ВДСА, ВДАС, ВАСД, ВАДС,

ДВАС, ДВСА, ДАВС, ДАСВ, ДСАВ, ДСВА.

Итого 24 варианта. Если говорить математическим языком, то мы составляем кортежи длины 4 из различных элементов четырёхэлементного множества.[14]

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

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

Теорема 6. Число различных перестановок из n элементов равно произведению последовательных натуральных чисел от 1 до n включительно, то есть Р =1 ∙2 ∙ 3 ∙ … ∙ n=n!

 При упорядочении n – элементного множества, какой-то элемент получит номер 1, какой-то номер 2 и так далее, какой-то из элементов получит номер n. Номер 1 может получить любой из элементов множества. Значит, выбор первого элемента можно осуществить n способами. Вторым может быть любой из оставшихся элементов, а значит, его можно выбрать (n – 1) способами. Третий элемент можно выбрать (n – 2) способами и т.д. Наконец, предпоследний можно выбрать двумя способами, а последний элемент только одним способом. По правилу произведения получаем, что общее число всевозможных перестановок из n элементов определяется по формуле: Р =n ∙ (n – 1) ∙ (n – 2) ∙ … ∙ 2 ∙ 1=n!

Теорема 6 доказана.

Задача 1. Сколько слов (не обязательно имеющих смысл) можно получить из букв слова «апельсин»?

Решение. Речь идет об упорядочении множества содержащего восемь элементов. Эта операция приводит к определению числа всех возможных перестановок из 8 элементов, то есть о вычислении Р₈.

Р₈=8!=1 • 2 • 3 • 4 • 5 • 6 • 7 • 8=40320 (перестановок).

Из этих комбинаций только одна – «спаниель» – является осмысленным словом русского языка, все остальные представляют собой бессмысленный набор букв[15].

Ответ: 40320 перестановок.

Задача 2. Сколько различных пятизначных чисел можно записать с помощью цифр 1, 2, 3, 4, 5, если ни одна цифра в записи числа не повторяется?

Решение. Так как, для записи пятизначного числа необходимо использовать 5 цифр, то речь идет об упорядочении множества содержащего пять элементов. Найдём число всевозможных перестановок из пяти цифр:

Р =5!=1 = 120(чисел).

Ответ: 120 чисел.

Задача 3. Сколько различных пятизначных чисел можно записать с помощью цифр 0, 1, 2, 3, 4, если ни одна цифра в записи числа не повторяется?

Решение. Как и предыдущей задаче, найдём число всевозможных перестановок из 5 цифр: Р =5!.

Однако, если цифра 0 займет первое место, число станет четырехзначным, таких чисел Р =4!. Следовательно, искомое число Р –Р =5! – 4!=120 – 24=96 (чисел).

Ответ: 96 чисел.