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

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

Пример. Перестановки из 3 различных элементов а, b и с: аbс, bса, саb, сbа, bас, асb.

Число всех перестановок из п различных элементов (обозначается Р_п) есть Р_п= =1×2×3×... × n = п! (п! читается "эн-факториал").

Действительно, выберем какой-то один элемент из п различных. Его можно разместить среди последовательности п- 1оставшегося элемента n способами. Получим п различных последовательностей из n- 1 элемента. Выберем в каждой такой последовательности из n- 1 элемента какой-то один элемент. Его можно разместить среди оставшихся n -2 элементов n -1 способом. Среди остальных п-2 элементов выберем какой-то один элемент. Его можно разместить среди оставшихся n —3 элементов n —2 способами и т.д. В конце-концов придем к 2 оставшимся элементам. Один из них можно разместить по отношению к другому элементу 2 способами. Оставшийся один последний элемент можно разместить относительно самого себя только одним способом. В итоге, с учетом правила произведения, получим Р_п = п× (п-1)×(п-2) ×...×2×1= п!

Для числа перестановок примера с перестановками 3 различных элементов а, b и с имеем Р₃= 3! = =6.

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

Таблица. Значения факториалов первых натуральных чисел и нуля.

Решением задачи 1 является Р₆ = 6!= 720 различных вариантов расстановки на полке 6 различных книг.