Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

2.1. Группа и связанные с ней понятия

Комбинаторные свойства подстановок

Ясно, что подстановки тесно связаны с комбинаторикой. Первый вопрос, который здесь возникает, звучит так: сколько подстановок можно составить из n индексов? Оказывается, это число равно n!, т.е. равно числу перестановок из n индексов. Отсюда получаются числа: 3! = 6, 4! = 24, 5! = 120. Почему это так, понять несложно. Представим перестановку n индексов следующей подстановкой:

а = .

Первый индекс i₁ можно выбрать n различными способами. После этого выбор i₂ можно осуществить только (n – 1) способами; индекса i₃ — (n – 2) способами и т.д. Так как выбор каждого индекса i осуществляется независимо, общее число способов размещения n чисел по n позициям равно произведению:

n · (n – 1) · (n – 2) · ... · 3 · 2 · 1 = n!.

Второй вопрос: сколько классов подстановок различной циклической структуры можно составить из n индексов? Ответ на этот вопрос таков: количество классов определяется числом возможных разложений n на слагаемые, причем таким образом, чтобы каждое последующее слагаемое было не больше предыдущего. В частности: при n = 3 имеем три способа разложения: 3, 21 и 111, так как

3 = 3,     3 = 2 + 1,    3 = 1 + 1 + 1.

Следовательно, может существовать три класса подстановок: (abc), (ab)(c), (a)(b)(c). При n = 5 будет уже семь классов: 5, 41, 32, 311, 221, 2111, 11111, с подстановками вида:

(01234), (0123), (012)(34), (034), (12)(34), (14), (0).

Наконец, возникает еще один вопрос комбинаторного характера: сколько подстановок содержится в классе C_i? Для представления циклической структуры подстановок, образующих класс C_i, будем пользоваться следующей спецификацией: C_i (k₁, k₂, ... , k_n), здесь k₁ — число 1-циклов, входящих в подстановку из класса C_i; k₂ — число 2-циклов, ... , k_n — число n-циклов.

Рассмотрим случай n = 4. Тогда тождественная подстановка e = (0)(1)(2)(3), образующая класс C₀, будет иметь спецификацию C₀(4, 0, 0, 0); подстановка (01)(23) из класса C₁ имеет спецификацию C₁(0, 2, 0, 0); подстановка (0)(123) из класса C₂ — спецификацию C₂(1, 0, 1, 0); подстановка (0123) из класса C₃ — спецификацию C₃(0, 0, 0, 1); подстановка (0)(1)(23) из класса C₄ — спецификацию C₄(2, 1, 0, 0). Таким образом, мы перечислили все пять возможных классов для подстановок, состоящих из четырех индексов.

Так как r-циклов содержит r индексов, а всего индексов n, то для любого класса C_i справедливо равенство:

1 · k₁ + 2 · k₂ + ... + n · k_n = n.

Например, для классов C₂ и C₄ имеем:

1 · k₁ + 3 · k₃ = 1 · 1 + 3 · 1 = 4,

1 · k₁ + 2 · k₂ = 1 · 2 + 2 · 1 = 4.

Цикл, длина которого r, можно записать r! способами, причем элементы в каждом из этих циклов можно выбрать способами. Так как все эти выборы можно сделать независимо, необходимо брать произведение . Если помнить, что общее число подстановок равно n!, то формула для нахождения количества элементов в классе C_i (k₁, k₂, ..., k_n) выглядит следующим образом:

.

В нашем конкретном случае число элементов по классам распределится следующим образом:

C₀(4, 0, 0, 0) = 1,     C₁(0, 2, 0, 0) = 3,     C₂(1, 0, 1, 0) = 8,

C₃(0, 0, 0, 1) = 6,     C₄(2, 1, 0, 0) = 6.

Число элементов во всех пяти классах должно быть равно n!:

4! = 1 + 3 + 8 + 6 + 6 = 24.

Завершим этот раздел демонстрацией одного несложного, но полезного приема. Касается он быстрого отыскания сопряженной подстановки b, если известна исходная a и трансформационная t. Демонстрацию проведем на конкретном примере.

Пусть даны следующие подстановки —

a = (052)(134)(67),     t = (0235)(1467).

Чтобы найти сопряженную относительно a подстановкуb необходимо осуществить преобразование подобия, сделав при этом умножение трех подстановок:

b = t^–1at =

= (0532)(1764) · (052)(134)(67) · (0235)(1467) =

= (032)(17)(456).

Однако подстановку b можно найти без этого утомительного перемножения. Для этого нужно на место индексов подстановки a поставить индексы, указанные подстановкой t. Так, первый индекс 0 подстановки a заменяется на индекс 2, поскольку в подстановке t индекс 0 переходит в 2. Второй индекс 5 подстановки a необходимо заменить на 0, так как в подстановке t осуществляется переход 5 → 0 и т.д. В результате получим: b = (203)(456)(71). Сравнивая данную подстановку с предыдущей, убеждаемся в их тождественности.