Перестановки

Рассмотрим различные упорядочения n элементного множества Х (век-тора длины n, составленные из n элементного множества). В отличие от декартова произведения, полученные при этом векторы, отличаются лишь порядком следования элементов и называются перестановками без повто-рений из n элементов. Число перестановок без повторений из n элементов обозначается Pn. К перестановкам без повторений можно прийти, полагая, что осуществляется размещение без повторений из n элементов по n:

Считается, что 0!=1.
Пример. Сколько существует возможных последовательностей выпол-нения проверок финансовой деятельности трех подразделений?
Требуется получить число перестановок без повторений из трех эле-ментов, т.е. Р3=3!=6.
Получим все эти последовательности:
(1,2,3), (1,3,2), (2,3,1), (2,1,3), (3,1,2), (3,2,1).
Пример. Сколько можно составить пятизначных шифров-чисел, не кратных 5, из цифр 1,2,3,4,5 без повторений цифр?
Всего из пяти цифр можно составить Р5=5!=120 пятизначных шифров-чисел, но они будут включать и кратные 5. Сколько будет шифров кратных 5? Из данного набора чисел кратными 5 могут быть числа, содержащие 5 в младшем разряде. Если цифру 5 записать в младшем разряде, то остальные цифры 1,2,3,4 можно распределить по разрядам Р4=4!=24 способами. Та-ким образом, число пятизначных шифров из чисел 1,2,3,4,5 без повторения чисел и не кратных 5 будет 120-24=96.
Перестановки без повторений можно интерпретировать как различные варианты векторов, состоящих из неповторяющихся компонентов, полу-чаемые перестановкой компонентов.
По аналогии при наличии одинаковых компонент в некотором векторе получаем задачу оценки так называемых перестановок с повторениями данного состава [23].
Рассмотрим вначале пример: сколько различных последовательностей – кодов можно получить, переставляя цифры в числе 010, т.е. векторов дли-ны k=3 из 2-х элементного множества В={0,1}, содержащих два нуля.
Имеется всего три разряда, которые обозначим р1, р2, р3. Их можно пе-реставить р3=3!=6 способами. Запишем различные получаемые сочетания разрядов и соответствующие коды:

Видно, что коды повторяются тогда, когда несущественен порядок сле-дования разрядов с одинаковой цифрой 0 (р1,р3). Все это соответствует то-му факту, что имеется два способа (2!) перестановки этих разрядов (р1,р3), (р3,р1) без изменения кода, т.е. неповторяющихся кодов будет меньше во столько раз, сколько имеется способов перестановки повторяющихся раз-рядов.
Рассмотрим более сложный случай.
Сколько различных «слов», не обязательно имеющих смысл, можно по-лучить, переставляя буквы в слове «кишмиш»?
Здесь шесть букв слова можно переставить друг с другом р6=6!=720 способами, но в данном слове буквы «и» и «ш» повторяются дважды и при их перестановке слова могут повторяться. Сколько же существует вариан-тов перестановок этих букв без изменения слова? Первый вариант – исход-ный, второй – поменять местами буквы «и», третий – поменять местами буквы «ш», четвертый – поменять местами как буквы «и», так и буквы «ш». Всего четыре варианта. С учетом того, что эти четыре варианта участ-вуют в порождении 720 способов, получим 720/4=180 различных «слов». Можно показать, что число раз, во сколько уменьшается количество слов по сравнению с числом перестановок без повторений, представляет собой произведение факториалов количества повторяющихся букв.
Таким образом, если из n элементов множества Х={x1,x2,...,xn} состав-лен вектор V длины k, причем каждому i-му компоненту можно поставить в соответствие число ki, указывающее его число повторений в V, то задан вектор S=(k1,k2,...,kn), который называется составом данного вектора.
Так, для Х={0,1,2,3} и V=(010223), состав: S=(2,1,2,1).
Векторы одного и того же состава, отличающиеся лишь порядком ком-понент, называются перестановками с повторениями данного состава.
Общая формула числа перестановок с повторениями данного состава имеет вид
Р(k1,k2,...,kn)= .
Пример. Сколько различных кодовых последовательностей можно по-лучить перестановками кода 102202030?
Такому вектору, составленному из элементов множеств {0,1,2,3} соот-ветствует вектор состава (1,4,3,1), поэтому число различных кодовых ком-бинаций определяется как число перестановок с повторениями этого соста-ва
Р(1,4,3,1)= .