Упорядоченные комбинации. 
Математика: логика, теория множеств и комбинаторика

Рассмотрим комбинации, в которых важен порядок следования элементов. В комбинаторике такие наборы называются перестановками и размещениями.

Определения и примеры

Пусть дано //-элементное множество S. Записав все его элементы в некотором порядке, получим набор, называемый перестановкой из п элементов (или перестановкой п-й степени).

Пример 10.1.1. S= (к, о, л} - трехэлементное множество. Тогда можно получить следующие перестановки из грех элементов:

кол, кло, окл, олк, лко, лок. •.

Нетрудно видеть, что перестановка из п элементов множества S представляет собой упорядоченную л-ку, составленную из различных элементов множества S. Составляя перестановку /7-й степени, мы линейно упорядочиваем множество S.

Отметим, что термин «перестановка» в общечеловеческом смысле понимается как процесс изменения порядка каких-либо объектов.

В математике подобный процесс обычно называют подстановкой. Более точно подстановка — это отображение (преобразование) я-элементного множества на себя. Это соответствие удобно задавать таблицей, в которой в первой строке стоят числа 1,2, …, я, а во второй — их образы, так что нижний элемент любого столбца есть образ верхнего элемента. В этом случае вторая строка такой таблицы является перестановкой множества {1,2,. Приведем примеры подстановок из четырех элементов:

Последняя подстановка является тождественным преобразованием. Рассмотрим упорядоченный набор, в котором каждый элемент некоторого множества записан определенное число раз. Занумеруем элементы исходного множества: д_ь а₂, …, д*. Пусть элемент д, встречается я, раз. Число и, — называется кратностью элемента д,. Такой набор называется перестановкой с заданной кратностью элементов. Набор кратностей (п, п₂, …, я*) называется составом (или типом) перестановки.

Например, слово МАТЕМАТИКА является перестановкой букв М, А, Т, Е, И, К состава (2,3,2,1,1,1).

Нетрудно видеть, что длина перестановки равна сумме всех кратностей И1+Л2+—•‘Н^;

Пример 10.1.2. Составим всевозможные перестановки элементов д, b состава (2,3).

Организуем перебор: aahbb baabb bbaab bbbaa ababb babab bbaba abbba babha Имеем 10 перестановок. •.

Теперь рассмотрим случай, когда из //-элементного множества требуется выбрать лишь часть элементов и расположить их в некотором порядке.

Упорядоченная комбинация, содержащая т элементов, выбранных из //-элементного множества, называется размещением из п элементов по т элементов (или, сокращенно, размещением из п по т).

В общем случае, некоторые из выбранных т элементов могут совпадать. Иногда бывает нужно рассмотреть размещения, в которых все элементы попарно различны. Поэтому, если в наборе могут встретиться повторяющиеся элементы, принято говорить, что рассматривается набор с повторениями (правильнее было бы говорить о наборе с возможным повторением элементов). Если при составлении набора берутся попарно различные элементы, то говорят, что рассматривается комбинация без повторений.

Пример 2.1.3. Дано множество S={2,3,4,5}. Составим всевозможные размещения е повторениями из 4 по 3:

В первых четырех столбцах приведены размещения, первая цифра которых равна 2, затем идут четыре столбца чисел, первая цифра которых равна 3 и т. д.

Всего получаем 64 размещения с повторениями. Размещений без повторений из 4 по 2 всего 24 (они подчеркнуты).

Каждое из приведенных размещений взаимно однозначно определяет трехзначное число, составленное из цифр 2, 3, 4, 5. Однако если в размещении на первом месте стоит 0, то, например, различные размещения по 3 и по 4 элемента 023 и 0023 определяют одно и то же двузначное число. •.

В заключение пункта сформулируем определения рассмотренных видов упорядоченных комбинаций на языке теории множеств.

Перестановкой из п элементов называется упорядоченная и-ка, составленная из п различных элементов.

Перестановкой из п элементов состава (п, /ъ, …, и*), где П+П2+…+Пк=п, называется упорядоченная //-ка, в которой имеется п элемент первого типа, п₂ элемента второго типа,…, п_к элементов к-то типа.

Размещением с повторениями из п по т называется любая упорядоченная m-ка, составленная из //-элементного множества.

Размещением без повторений из п по т (или, как часто говорят, просто «размещением из п по т») называется любая упорядоченная т-ка, составленная из попарно различных элементов //-элементного множества.

В частности, размещение без повторений из п по п есть перестановка из п элементов.

Напомним, что упорядоченная п-ка с попарно различными элементами представляет собой //-элементное множество с заданным на нем линейным порядком.