Дискретно-непрерывная математика (стр. 69 )

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

Например, схема

Старая позиция 1 2 3 4 5 6

Новая позиция 3 2 5 6 1 4

характеризует перестановку степени 6, в которой пер­вый элемент становится третьим, второй остается вто­рым, третий становится пятым и т. д.

Предыдущая перестановка очевидным образом представляется в виде ориентированного графа, который показан на рис. 5.10.

Рис. 5.10

Вообще, любую перестановку степе­ни k можно представить ориентированным гра­фом, вершины которого соответствуют числам от 1 до k, причем положи­тельные и отрицательные степени каждой вершины равны 1. Было показано, что такой ориентирован­ный граф обязательно распадается на один или несколько простых контуров без общих вершин (некоторые из них могут быть петлями). Действительно, другое используемое обозна­чение предыдущей перестановки есть так называемое циклическое представление: (1, 3, 5) (2) (4, 6). В об­щем случае, циклическое представление интерпретиру­ется так: позиция, представленная любым числом, ото­бражается в позицию, соответствующую следующему числу справа, за исключением самой правой позиции внутри данной группы, которая отображается в пози­цию, соответствующую самому левому числу в группе. Тип данной перестановки степени k определяется в зависимости от числа контуров длины i, которое она со­держит, для

і=l, 2, .... k. Если пі обозначает число контуров длины i, то тип перестановки удобно описы­вать вектором (п1, п2, ..., nk). Очевидно, тип должен удовлетворять условию 1•nl+2•n2+... +k•nk=k. Тип предыдущей перестановки есть (1, 1, 1, 0, 0, 0), а перестановка степени 12, циклическое представле­ние которой

(1,4,2,6) (3) (5,7,9,8) (10) (11, 12),

имеет тип

(2, 1, 0, 2,0,0, 0, 0, 0, 0, 0, 0).

Другой удобный способ представления типа этой пе­рестановки

у21, у12, у24, где нижние индексы означают длины контуров, а верхние соответствуют числу конту­ров заданной длины. (Символ у не имеет специального значения и применяется как основа для расстановки ин­дексов.) Заметим, что если в перестановке отсутствуют контуры длины i, то символ у0і опускается.

Рассмотрим множество Р, состоящее из k переста­новок степени h. Пусть hj1, j2,...., jk обозначает число пе­рестановок типа (j1, j2, ..., jk). Тогда формальный ряд

где суммирование ведется по всем типам, называется циклическим индексом Р. Будем рассматривать множе­ства Р перестановок (одной и той же степени), которые образуют группу относительно бинарной операции по­следовательного применения двух перестановок. Таким образом, Р должно содержать тождественную переста­новку, обратную перестановку для каждой из переста­новок и произведение любых двух перестановок группы.

В данном случае нас интересуют перестановки множества всех неупорядоченных пар (или в случае на­правленного графа упорядоченных пар) вершин графа, которые получаются в результате перестановки вершин графа. Например, если вершины четырехвершипного графа переставлены, как показано на рис. 5.11, а, то получается перестановка неупорядоченных пар вершин, показанная на рис. 5.11, b.

Рис. 5.11.

Для данного частного при­мера заметим, что перестановка четырех вершин, имею­щая тип у11 у13, индуцирует перестановку шести неупо­рядоченных пар вершин, тип которой у23. Подобным же образом, каждая из п! возможных перестановок п вер­шин индуцирует вполне определенную перестановку п(п—1)/2 неупорядоченных пар вершин (или п(п—1) упорядоченных пар, если мы изучаем ориентированные графы).

Далее нам потребуется знать число перестановок как для упорядоченных, так и для неупорядоченных пар каждого типа, индуцированных всеми возможными пе­рестановками четырех вершин, а также число перестано­вок неупорядоченных пар, индуцированных всеми воз­можными перестановками пяти вершин. Для интересующих нас случаев информа­ция о числе перестановок каждого типа содержится в следующих циклических индексах:

четыре вершины, неупорядоченные пары:

четыре вершины, упорядоченные пары:

пять вершин, неупорядоченные пары:

Введем еще несколько вспомогательных понятий. Рассмотрим множество абстрактных объемов, называе­мых фигурами, и предположим, что с каждой фигурой связано одно из нескольких неотрицательных чисел (мы будем использоватьлолько числа 0, 1 и 2), которое бу­дем называть ее объемом (в более общей форме, теоре­ма Поня позволяет связывать с каждой фигурой некоторый целочисленный вектор). Если аk обозначает число различных фигур, имеющих объем k, то формальный ряд

называется рядом, перечисляющим фигуры (здесь х яв­ляется фиктивной переменной).

Конфигурация длины s есть последовательность или упорядоченное множество s фигур. Под объемом конфи­гурации понимается простая сумма объемов фигур. Не­которые конфигурации длины s считаются эквивалент­ными. В частности, пусть Р — группа перестановок сте­пени s, и пусть h — число перестановок в группе. Тогда говорят, что две конфигурации эквивалентны относи­тельно Р в том и только в том случае, когда одна полу­чается из другой подходящей перестановкой из Р.

Если bk обозначает число неэквивалентных конфигу­раций (длины s), имеющих объем k, то формальный ряд

называется рядом подсчета, перечисляющим конфигу­рации (относительно Р).

Теорема Пойя позволяет определить В(х), зная ряд, перечисляющий фигуры А(х), и циклический индекс Z(P) подгруппы перестановок Р. В частности, мы имеем (без доказательства) следующую теорему.

Теорема 5.5. (Пойя). Если А(х) и Z(P) обозначают ряд, перечисляющий фигуры, и циклический индекс Р соответственно, то ряд, перечисляющий конфигурации, можно получить подстановкой А (хk) вместо каждого уk в циклический индекс группы Р.

Рассмотрим снова задачу подсчета всех неизоморф­ных обыкновенных графов, имеющих пять вершин. Возьмем в качестве фигур 10 неупорядоченных пар раз­личных вершин. Будем считать, что фигуры имеют объ­ем 1 или 0 в зависимости от того, соединены соответ­ствующие вершины ребрами или нет. Тогда ряд, перечисляющий фигуры, принимает простую форму

А(х) = 1+х.

Рассмотрим затем конфигурации длины 10, соответствующие последовательностям, образованным из 10 фигур. В данном случае группа перестановок Р состоит из мно­жества перестановок 10 фигур (т. е. неупорядоченных пар различных вершин). Она индуцирована группой Р* всех возможных перестановок пяти вершин (заме­тим, что имеется 5! таких перестановок).

Подставляя 1+ хk вместо каждого yk в циклический индекс Z(P), определенный ранее, и упрощая получен­ное выражение, получим

На основе этого можно, например, сделать вывод, что существуют 6 различных графов с четырьмя ребрами, так как в выражении присутствует член 6x4. Эти графы показаны на рис. 5.12.

Рис. 5.12.

Для того чтобы найти число различных обыкновен­ных ориентированных графов, имеющих 4 вершины, представим фигуры как упорядоченные пары вершин. В этом случае ряд, перечисляющий фигуры, останется прежним А(х)=1+х, так как упорядоченная пара вер­шин либо соединена, либо не соединена дугой. Цикли­ческий индекс Z(P) для группы Р перестановок 12 упо­рядоченных пар вершин, индуцированных всеми воз­можными перестановками вершин, был выписан выше. Подставляя A(xk) вместо уk в Z(P) и делая упрощения, получим

Наличие члена 5х2, например, позволяет сделать вывод, что имеется 5 различных графов с двумя дугами. Эти графы показаны на рис. 5.13.

Рис. 5.13.

Вернемся снова к задаче подсчета числа различных графов, имеющих 4 вершины, в которых нет петель, а любая пара вершин соединяется самое большее двумя ребрами. В этом случае в качестве фигуры снова бе­рется неупорядоченная пара вершин. Однако при этом объем может принимать три значения 0, 1 или 2 в зависимости от числа ребер, соединяющих вершины. Поэтому ряд, перечисляющий фигуры, имеет вид э