ПОЙА ТЕОРЕМА

пусть R^D- множество отображений конечного множества D, |D|=n, в множество R и пусть G- группа подстановок множества D, порождающая разбиение R^D на классы эквивалентности, при к-ром принадлежат одному и тому же классу тогда и только тогда, когда найдется такое , что f₁(g(d)) = f₂(d).для всех ; если каждому сопоставлен вес w(r) - элемент коммутативного кольца (вес f полагается равным

и вес w(F).класса определяется как вес любого

), то

где в левой части равенства сумма берется по всем классам эквивалентности, а

есть цикловой индекс G, при этом j_k(G) - число циклов длины kподстановки gв разложении ее в произведение независимых циклов.

Теорема была опубликована в 1937 Д. Попа (G. Рo1уа, см. [3] с. 36-138), хотя фактически она была известна раньше (см. [3] с. 9-35).

Если в качестве веса элементов R брать степени независимой переменной х(или произведение степеней нескольких переменных), то для (т. н. "ряд, перечисляющий фигуры", где - число элементов Rвеса ) и (т. <н. "ряд, перечисляющий конфигурации", где - число классов R^D веса ) согласно П. т. имеет место соотношение:

Примеры. 1) Если и тогда Р(G; т, т, . .., m) - число классов эквивалентности.

2) Если R={0, 1}, w(r)= x^r, то j(х)=1+х, а fR^D с w (f)=z^k можно истолковать как подмножество Dмощности k. Группа Gиндуцирует орбиты подмножеств D, и коэффициент при x^k в многочлене Р(G;1+x) есть число орбит, состоящих из подмножеств мощности k.

3) Пусть R={0, 1}, D=V² -все 2-подмножества {i, j} множества V={1, 2, . . ., р}, тогда представляет помеченный граф с вершинами из V, у к-рого две вершины iи jсмежны, если f({i, j})=1. Пусть w(r)=х ^r, тогда если w(f)=x^k, то k - число ребер в графе, соответствующем отображению f. Если на Vдействует симметрич. группа S_p, то, определив для sS_p подстановку g_s на Dсоотношением g_s{i, j}={s(i), s(j)}, получают парную группу G=S⁽²⁾={g_s}, действующую на D=V⁽²⁾.

Для последовательности g_pk (чисел графов с рвершинами и kребрами), k=l, 2, . .. , по П. т. получают производящую функцию

Для единичной группы подстановок Е _n, симметрич. группы подстановок S_n и парной группы подстановок цикловой индекс имеет соответственно вид

где (r, s) - наибольший общий делитель, [r, s] - наименьшее общее кратное чисел rи s, а суммирование S* проводится по k₁, k₂, . . ., k_n при условии k₁+2k₂+... +nk_n=n. Известны цикловые индексы для знакопеременной, циклической и диэдральной групп, а также формулы для получения цикловых индексов для произведения, декартова произведения и сплетения групп (см. [4]).

Имеются обобщения П. т. на случай иного определения как веса функции, так и классов эквивалентности [1].

Лит.:[1] Де Брейн Н. Д ж., в кн.: Прикладная комбинаторная математика, пер. с англ., М., 1968, с. 61-106; [2] Сачков В. Н., Комбинаторные методы дискретной математики, М., 1977; [3] Перечислительные задачи комбинаторного анализа. Сб. переводов, М., 1978; [4] Харари Ф., Палмер 9., Перечисление графов, пер. с англ., М., 1977.

В. М. Михеев.