в качестве нетривиального примера применения теоремы В найдем число строк букв а, Ь, с, содержащих ровно

А вхождений буквы а;

В вхождений буквы 6;

С вхождений буквы с;

к вхождений пары стоящих рядом букв са;

I вхождений пары стоящих рядом букв сЬ;

т вхождений пары стоящих рядом букв Ьа. (18)

Из теоремы следует, что это то же самое, что найти число двухстрочных массивов

вида

а Ъ ... 6 с

U U • • • U U

А-к-mas т as

В-1 bs

к as

(19)

I bs

Буквы а можно расположить во второй строке А \ fB\ (С \к

, . , , , способами; ,А - к - т I \7П/

после этого буквы 6 можно разместить в оставшихся позициях

fB + k\ fC-k

способами.

Остальные свободные места нужно заполнить буквами с; следовательно, искомое число равно

А-к-т

В\ т)

fC-k\ I

(20)

Вернемся к вопросу о нахождении всех разложений данной перестановки. Существует ли такой объект, как "простая" перестановка, которая не разлагается на множители, отличные от нее самой и е? Обсуждение, предшествующее теореме А, немедленно приводит к выводу о том, что перестановка будет простой тогда и только тогда, когда она является циклом без повторяющихся элементов. В случае, если перестановка является таким циклом, наше рассуждение доказывает, что не существует левых множителей, кроме е и самого цикла. Если же перестановка содержит повторяющийся элемент у, то всегда можно выделить нетривиальный цикл в качестве левого сомножителя, в котором элемент у встречается всего лишь однажды.

Если перестановка непростая, то ее можно разлагать на все меньшие и меньшие части, пока не будет получено произведение простых перестановок. Можно даже показать, что такое разложение является единственным с точностью до порядка записи коммутирующих сомножителей.

Теорема С. Каждую перестановку мультимножества можно записать в виде произведения

aija2j---jat, t>0, (21)

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

Термин "непересекающиеся циклы" относится к циклам, не имеющим общих элементов. В качестве примера можно проверить, что перестановка

а а b b с с yb а а с d b с

разлагается на множители ровно пятью способами:

{а Ь) т (а) т (с rf) т {Ь с) = {ab)j (с d) т (а) т (6 с) = (а 6) т (с d) т (Ь с) т (а) = (с rf) т (а Ь) т (6 с) т (а) = {cd)T{ab)j{a)j{bc). (22)

Доказательство. Нужно установить, что выполняется сформулированное в теореме свойство единственности. Применим индукцию по длине перестановки; тогда достаточно доказать, что если р и а - два различных цикла, не содержащих повторяющихся элементов, и

то р и сг - непересекающиеся циклы и

а = атв, Р = ртв,

где в - некоторая перестановка. Пусть у - произвольный элемент цикла р, тогда у любого левого сомножителя в разложении aj0, содержащего этот элемент у, будет левый сомножитель р. Значит, если р и а имеют общий элемент, цикл а должен быть кратен р; тогда а - р (так как они простые), что противоречит нашему предположению. Следовательно, цикл, содержащий у и не имеющий общих элементов с а, должен быть левым сомножителем в разложении р. Применив законы сокращения (7), завершим доказательство.

В качестве иллюстрации теоремы С рассмотрим перестановки мультимножества М = {А а, В Ь, С с}, состоящего из А элементов а, В элементов 6 и С элементов с. Пусть N(A, В,С,т) - число перестановок мультимножества М, двухстрочпое представление которых не содержит столбцов вида и содержит ровно т

столбцов вида I. Отсюда следует, что имеется ровно А - т столбцов вида 1, В - т столбцов вида I, С-В+т столбцов вида ц, С-А+т столбцов вида и А+В-С-т столбцов вида ; следовательно,

N{A,B,C,m) = ( ( ( „ ) . (23)

Теорема С предлагает другой способ подсчета этих перестановок: коль скоро столбцы а; bi с исключены, В разложении перестановки единственно возможны такие простые множители:

(аЬ), (ас), (be), {а be), (acb). (24)

Каждая пара этих циклов имеет хотя бы одну общую букву, значит, разложение единственно. Если цикл (а b с) встречается в разложении к раз, то из нашего предыдущего предположения следует, что (а Ь) встречается т - к раз, (Ь с) встречается С - А + т~ к раз, (а с) встречается С - В + т - к раз и (а с 6) встречается А + В - С-2т + краз. Следовательно, N{A, В, С, т) равно числу перестановок этих циклов (полиномиальному коэффициенту), просуммированному по всем значениям к:

N{A,B,C,m)

V- (С + т-ку.

Y {т-ку.{С-А + т~к)\(С-В + т-ку.к\(А + В-С-2т + ку.

А\ I А-т \ С + т-к

Сравнивая (25) с (23), обнаруживаем, что должно выполняться тождество

?(Г) {с-в+Z-k) ("Г") = ic-A + m) (в-т)-

Оказывается, с этим тождеством мы встречались в упр. 1.2.6-31:

где MA + B-C-m,N--=C-B + m,R = B,S = C,a.j = C-B + m-к.

Аналогично можно подсчитать число перестановок мультимножества {А-а, В-Ь, С с, D с?},"если количество столбцов различных типов в них задано следующим образом.

Тип а а Ь Ь с с d d

столбца: d Ь а с Ь da с (28)

Частота: г А-г q B-q В-Л + r D-r A-q D-A + q

(Здесь A + С = В + D.) Возможными циклами в разложении такой перестановки на простые множители будут

Цикл: (а Ь) (Ь с) (с d) (d а) (abed) (deb а) 29)

Частота: A-r-s B-q-s D-r-s A-q-s s q-A + r + s

при некотором s (см. упр. 12). В этом случае циклы (а Ь) и (с d) заменяют друг друга так же, как циклы (Ь с) и (d а), поэтому необходимо подсчитать число различных разложений на простые множители. Оказывается (см. упр. 10), всегда существует единственное разложение, такое, что цикл (а Ь) никогда не следует непосредственно