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

Акимов О.Е.

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

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

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

а = .

Первый индекс i1 можно выбрать n различными способами. После этого выбор i2 можно осуществить только (n – 1) способами; индекса i3 — (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).

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

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

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

1 · k1 + 2 · k2 + ... + n · kn = n.

Например, для классов C2 и C4 имеем:

1 · k1 + 3 · k3 = 1 · 1 + 3 · 1 = 4,

1 · k1 + 2 · k2 = 1 · 2 + 2 · 1 = 4.

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

.

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

C0(4, 0, 0, 0) = 1,     C1(0, 2, 0, 0) = 3,     C2(1, 0, 1, 0) = 8,

C3(0, 0, 0, 1) = 6,     C4(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). Сравнивая данную подстановку с предыдущей, убеждаемся в их тождественности.


 
  


Hosted by uCoz