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

Пусть задано конечное множество /, состоящее из п элементов, т. е. / = {/'| 1 < / < п}.

Определение 3.1. Перестановкой элементов Рп множества I

называется расположение их в некотором порядке.

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

В связи с тем, что элементы конечного множества / могут быть пронумерованы числами натурального ряда, любая перестановка Рп множества / эквивалентна перестановке номеров этих элементов, т. е. перестановке чисел натурального ряда. Пусть, например, индексное множество I состоит из трех элементов / = {/',, /2, /3}. Тогда /',, /2, /3 — первая перестановка, которой соответствует перестановка чисел 1,2, 3; /,, /3, /2 — вторая перестановка элементов и соответствующая ей перестановка чисел 1, 3, 2 и т. д. На этом основании изучение перестановок элементов любого множества может быть сведено к изучению перестановок чисел натурального ряда.

Первый вопрос, который обычно возникает при рассмотрении перестановок, сколько различных перестановок можно составить для «-элементного множества /? В реальной жизни он может звучать, например, так: сколько различных очередей можно составить из пяти человек? Прежде чем, мы получим ответ на поставленный вопрос, введем известное обозначение для произведения п натуральных чисел 1-2-3-... « = «!, которое читается «эн факториал».

Теорема 3.1. Число перестановок Рп конечного множества /,

состоящего из п элементов, равно произведению чисел натурального ряда 1 *2 3-... лг, т. е. Рп = п .

Истинность этого определения проще всего подтвердить, применяя правило произведения. Пусть имеется п мест, на которых можно располагать элементы множества /. Тогда на первое место можно поставить любой из п элементов /. После того, как занято первое место, на второе место можно поставить любой из п -1 оставшихся элементов. В результате по правилу произведения получаем п(п - 1) вариантов размещения элементов на первых двух местах. Продолжая процесс дальше до последнего места и последнего элемента, получим, что все п мест можно заполнить п(п - 1)(« — 2)*___-2-1 = п способами.

Приведем некоторые примеры вычисления числа перестановок. Сколькими различными способами можно расположить на полке 4 книги? Ответ: Рп = 4! = 1-2-3-4 = 24. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга? Очевидное расположение ладей, не бьющих друг друга, такое: на каждой горизонтали и вертикали шахматной доски стоит одна ладья. Применяя шахматную нотацию, это можно записать так: ах, Ь2, с3, , е5, /6, g1,8. Отсюда

следует, что для решения задачи необходимо найти все перестановки первых восьми натуральных чисел. Таким образом, число возможных расположений ладей = 8! = 40 320.

Пусть Рп+з =(/7 + 3)!, а Рп - п. Требуется определить частное

(л + 3)!. Ответ: !(" + 1)("+2)(/7 + 3) = (п + щп + 2)(я + 3).

п

п

Число перестановок Рп = п свойственно всем тем случаям, когда переставляемые объекты все попарно различны. Если же некоторые объекты одинаковы, то число различных перестановок окажется меньшим, так как некоторые из них будут одинаковы. Возьмем, например, первые три числа натурального ряда 1, 2, 3 и составим из них все перестановки, а рядом выпишем перестановки чисел 1, 1,3. Легко можно видеть, что во втором случае мы получим три различные перестановки 113, 131, 311, которые отмечены галочками:

123

113

132

131

л/

213

311

л/

231

312

313.

Определение 3.2. Перестановки, в которых содержатся повторения последовательностей объектов, называются перестановками с повторениями.

Возникает вопрос, как определить число перестановок с повторениями? Отвечая на него, сразу же скажем, что это число зависит от количества повторяющихся элементов.

Пусть имеется п объектов, которые разбиты на к групп с /7, одинаковыми элементами в первой группе, п2 одинаковыми элементами во второй группе и пк одинаковыми элементами в последней, к-й группе. В нашем примере с тремя числами натурального ряда первая группа /7, состоит из двух чисел 1,1, вторая п2из одного числа 3.

Объекты любой группы можно переставлять местами пк различными способами. И это не будет изменять выбранную перестановку. Например, в перестановке 113 можно поставить единицу двумя способами, что не приведет к изменению последовательности 311. Однако последовательности сразу же изменяются, если мы начнем комбинировать элементы различных групп между собой. По правилу произведения число таких комбинаций равно пхп2-...пк.

В рассматриваемом нами примере, комбинируя элементы 1, 1 с элементом 3, получим еще две перестановки 131, 311. Таким образом, множество всех п перестановок распадается на части, состоящие из п]-п2-...-пкодинаковых перестановок каждая.

Теорема 3.2. Число различных перестановок из п элементов с повторениями определяется по формуле Р(пх, п2, ..., пК) = я!

пхп2-...пк

3' 6

Для нашего примера Р(пх, п2)~-=-= 3, в чем легко

2.1. 1 2 1

убедиться, подсчитывая перестановки, отмеченные галочками.

Решим еще одну задачу. Сколько перестановок можно составить из букв слова «Миссисипи»? Для этого используем формулу, по которой определяется число перестановок с повторениями.

В слове «Миссисипи» одна буква «М», четыре буквы «И», три буквы «С» и одна буква «П». Всего девять букв. Значит

Р{п,, п^, и.) =-—-= 2520.

При решении практических задач, в частности, экстремальных задач комбинаторного типа, в которых функционалы определены на множествах перестановок, возникает необходимость последовательно составлять перестановки некоторого я-элементно-го множества объектов. Существует ряд методов построения последовательностей всех п! перестановок такого множества. Их принято называть методами генерации перестановок. Для получения очередной перестановки эти методы используют различные приемы: транспозицию элементов предшествующей перестановки (обмен местами двух элементов этой перестановки), сдвиг элементов перестановки и др. Рассмотрим простейший из них. В этом методе используется транспозиция двух соседних элементов перестановки.

Предположим, необходимо составить все перестановки трехэлементного множества N = {1, 2, 3}. Для этого сначала в перестановку 2, 3 вставим элемент 1 всеми возможными способами. В результате получим три перестановки 123, 213, 231. Затем всеми возможными способами вставим элемент 1 в перестановку 3, 2. В результате получаем также три перестановки 321, 312, 132. При этом заметим, что при построении первой последовательности перестановок транспозиция единицы осуществляется со следующим элементом предшествующей перестановки, а при построении второй последовательности транспозиция единицы осуществляется с предшествующим элементом перестановки. Наглядно это показано ниже, где единица отмечена жирным шрифтом.

  • 213
  • 321
  • 132.

Таким образом, в общем виде для формирования всех перестановок элементов 1, 2, ..., п необходимо последовательно вставлять элемент 1 всеми возможными способами в каждую перестановку элементов 2, 3, ..., п. В результате этот элемент будет перемещаться между первой и последней перестановкой попеременно вперед и назад (/7-1)! раз.

 
< Пред   СОДЕРЖАНИЕ     След >