7. (Анализ) Комбинаторика. Перестановка

По | 14 июня, 2022
перестановка

Перестановка — это один из ключевых терминов комбинаторики. Она представляет собой комбинацию из нескольких элементов, которые отличаются друг от друга только порядком следования.

Как и размещение, перестановку можно разделить на два вида:

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

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

По сути, данный вид перестановки есть частный случай размещения без повторений, когда объём выборки равен количеству всех объектов исходного множества. Количество перестановок без повторений из 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

То есть можно составить более полумиллиона слов.

Что дальше?

Теперь нам осталось познакомиться с термином «Сочетание«. Об этом в следующей статье.