1) Перестановки без повторений.
Определение 3: Пусть - конечное множество из элементов. Перестановками из элементов множества называются все размещения из элементов множества . Обозначается: .
Согласно определению:
.
Таким образом: .
2) Перестановки с повторениями.
Перестановки с повторениями используются в тех задачах, в которых речь идёт не о единичных объектах, а о видах, классах, сортах элементов. Понятно, что внутри каждого вида элементы повторяются.
Пусть имеются предметы различных типов:
.
Сколькими способами можно переставить местами элемент первого вида, элементов второго вида, ..., элементов последнего вида?
Число элементов в каждой перестановке равно: .
Перестановки элементов внутри вида не меняет перестановку. Она изменится только в случае межвидовых перестановок. Если бы все элементы были бы различными, то число всех перестановок равнялось бы . Но в силу того, что есть повторяющиеся объекты, получится меньшее число перестановок.
Теорема 3: Число различных перестановок с повторениями находится по формуле:
, где .
Замечание: В комбинаторике если не нужно засчитывать какое-то число способов, то на это число делят.
Поэтому в знаменателе дроби стоят числа (число перестановок элементов первого вида, которые не нужно засчитывать), (число перестановок элементов второго вида) и т. д. Перестановки элементов первого типа, второго типа и т.д. можно делать независимо друг от друга, поэтому по правилу умножения элементы данной перестановки можно переставлять способами. Значит, число различных перестановок с повторениями будет равно указанному числу.
Например, перестановки букв в словах мама, математика, анаграммы – есть перестановки с повторениями.