Перестановки без повторений
Перестановки в ряд
Перестановкой из элементов (или -перестановкой) называется -элементное упорядоченное множество, составленное из элементов -элементного множества.
Иначе: Перестановкой из элементов (или -перестановкой) называется размещение из элементов по без повторений.
Число перестановок из элементов без повторений обозначается от французского словаperturbation.
Теорема: число способов расположить в ряд различных объектов есть
Замечание: Рекуррентная формула: .
Перестановки симметричных объектов
различных предметов можно расположить по кругу способами, а если их можно еще и переворачивать, то различными способами.
Размещения без повторений
Подсчитаем количество способов расположить различных элементов по различным позициям (). Такие расположения называются размещениями, а их количество, от французского слова arrangement обозначается . В случае, если количество предметов совпадает с количеством имеющихся мест, и это уже изученная задача о числе перестановок.
Если из объектов выбирают штук, то число выборов последнего объекта есть невыбранных объектов, что означает наличие возможности выбора последнего выбранного объекта. То же, другими словами: после выбора первых элемента остается выбрать элемент.
Теорема: число размещений различных элементов по различным позициям есть
,
или, в терминах факториалов,
.
Примечание: заметим, что в случае, когда число мест, по которым размещают предметы, совпадает с количеством самих предметов, т. е. когда , рассматриваемая задача становится задачей о числе перестановок. В нашем случае при этом мы получаем в знаменателе дроби ноль факториал, и для того, что бы разные формулы, соответствующие одной и той же задаче, приводили к одинаковым результатам, полагают, что .
Сочетания
Подсчитаем количество способов, которыми можно выбрать из различных предметов. Такие выборки называются сочетаниями, а их количество обозначается .
При , выбрать k предметов из n можно способами, переставляя их способами:
.
Рекуррентная формула: .
Свойства сочетаний: ;.