Перестановка — это один из ключевых терминов комбинаторики. Она представляет собой комбинацию из нескольких элементов, которые отличаются друг от друга только порядком следования.
Как и размещение, перестановку можно разделить на два вида:
Перестановка без повторений.
По сути, данный вид перестановки есть частный случай размещения без повторений, когда объём выборки равен количеству всех объектов исходного множества. Количество перестановок без повторений из n элементов определяется следующей формулой:
Pnn = n * (n − 1) * … * (n − n + 1) = n! / (n − n)! = n! / 0! = n! / 1 = n!
Перестановка с повторениями.
Так как перестановка это тоже размещение, то логично предположить, что рассматриваемый вариант перестановки относится к размещению с повторениями. В целом это так. В перестановках с повторениями, также участвует сразу все объекты, но есть одно отличие.
Когда мы работаем с «Размещением с повторениями», то извлекаем объект из множества и возвращаем его обратно. Поэтому в следующий раз мы можем извлечь тот же объект, что извлекался ранее. Это и есть повторение. Но в случае с перестановкой ситуация несколько иная. Дело в том, что некое множество может состоять из объектов, часть из которых имеет одинаковые характеристики.
Например слово:
К, О, Л, О, К, О, Л, Ь, Ч, И, К
является множеством и состоит из нескольких букв, где:
К – повторяется 3 раза;
О – повторяется 3 раза;
Л – повторяется 2 раза;
Ь – повторяется 1 раз;
Ч – повторяется 1 раз;
И – повторяется 1 раз.
Именно об этих повторениях и идёт речь, при работе с перестановками.
Поэтому общая формула будет такой:
Pn1,n2,…,nk = n! / (n1! * n2! * … * nk!) ,
где n — количество всех объектов во множестве, nk — количество повторений одного элемента
Например: Сколько различных слов (не обязательно осмысленных) можно получить при перестановке букв: в слове: К, О, Л, О, К, О, Л, Ь, Ч, И, К?
Так как среди букв есть одинаковые,то здесь имеет место перестановка с повторениями, и осталось выполнить бесхитростные подсчёты – всего у нас 11 карточек, среди которых буква:
К – повторяется 3 раза;
О – повторяется 3 раза;
Л – повторяется 2 раза;
Ь – повторяется 1 раз;
Ч – повторяется 1 раз;
И – повторяется 1 раз.
Всего букв: 3 + 3 + 2 + 1 + 1 + 1 = 11, что и требовалось проверить.
По формуле количества перестановок с повторениями:
Р11 = 11! / (3! * 3! * 2! * 1! * 1! * 1!) = 39916800 / (6 * 6 * 2 * 1 * 1 * 1) = 554400
То есть можно составить более полумиллиона слов.
Что дальше?
Теперь нам осталось познакомиться с термином «Сочетание«. Об этом в следующей статье.