Читать курсовая по математике: "Практическое применение теоремы Пойа и перечисления графов" Страница 6

(Назад) (Cкачать работу)

Об элементе y из Y, для которого , говорят, что он имеет вес k, а функцию w называют весовой функцией. Далее, ряд

относительно переменной x, который перечисляет элементы множества Y в соответствии с их весами, называют «перечисляющим рядом для фигур».

Вес функции f из YX определяется формулой

и тогда нетрудно показать, что функции, принадлежащие одной и той же орбите степенной группы , имеют одинаковые веса. Весом w(F) орбиты F группыназовем вес любой функции f из орбиты F. Так какдля всякого k = 0, 1, 2, …, то существует только конечное число орбит каждого веса. Обозначим черезчисло орбит веса k. Ряд относительно переменной x назовем «перечисляющим рядом для функций» или «перечисляющим рядом для конфигураций».

Теперь мы можем сформулировать основную теорему, выражающую ряд C(x) в терминах циклового индекса Z(A) и ряда c(x). В приводимой ниже формуле Z(A, c(x)) является сокращением для Z(A, c(x), c(), c(), …).

Теорема (теорема перечисления Пойа, 1927)

Ряд C(x), перечисляющий функции, получается с помощью подстановки в цикловой индекс Z(A) на место каждой переменнойрядаперечисляющего фигуры. Символически:

Доказательство. Пусть e - тождественная подстановка на Y. Для всякой подстановки a из A и любого k = 0, 1, 2, … обозначим через ц(a, k) число функций веса k, неподвижных относительно подстановки (a; e). Ограничивая для каждого k действие степенной группына множество функций веса k и применяя ограниченную форму леммы Бернсайда (1.13), имеем

Следовательно,

и, меняя порядок суммирования, получаем

Рядперечисляет все функции, неподвижные относительно подстановки (a; e), и мы постараемся найти другую форму для этого ряда.

Предположим, что функция f изнепожвижна относительно подстановки (a; e). Тогдадля всех x из X и в силу формулы (1.14), имеем . Таким образом, для всех x должно выполняться равенство , то есть функция f должна быть постоянной на непересекающихся циклах подстановки a. Обратно, все функции, постоянные на циклах подстановки a, неподвижны относительно подстановки (a; e).

Пусть- цикл длины r в подстановке a. Если функция f отображает элементы циклав один изэлементов множества Y, имеющих вес k, то циклвносит в вес функции f значение r·k. Тогда легко видеть, что для каждого k коэффициент прив ряду

равен числу способов, которыми можно определить функцию f на элементах циклатак, чтобы она была неподвижна относительно подстановки (a; e) и чтобы вклад в вес w(f) составлял r·k. Отсюда следует, что рядперечисляет в соответствии с их весами различные способы определения функций, постоянных на всех циклах длины r подстановки a.

Рассматривая все циклы подстановки a, мы можем выразить ряд для функций, постоянных на циклах, в виде произведения

Теперь утверждение теоремы Пойа (18) следует из (1.21), (1.23) и определения циклового индекса Z(A).

2. Практическое применение Теоремы Пойа и перечисления графов .1 Решение задач о перечислении графов с помощью теоремы ПойаМы будем перечислять графы с n

Похожие работы