Пойа Теорема

Пусть RD- множество отображений конечного множества D, |D|=n, в множество R и пусть G- группа подстановок множества D, порождающая разбиение RD на классы эквивалентности, при к-ром принадлежат одному и тому же классу тогда и только тогда, когда найдется такое , что f1(g(d)) = f2(d).для всех ; если каждому сопоставлен вес w(r) — элемент коммутативного кольца (вес f полагается равным и вес w(F).класса определяется как вес любого ), то где в левой части равенства сумма берется по всем классам эквивалентности, а есть цикловой индекс G, при этом jk(G) — число циклов длины kподстановки gв разложении ее в произведение независимых циклов. Теорема была опубликована в 1937 Д. Попа (G. Рo1уа, см. [3] с. 36-138), хотя фактически она была известна раньше (см. [3] с. 9-35). Если в качестве веса элементов R брать степени независимой переменной х(или произведение степеней нескольких переменных), то для (т. н. "ряд, перечисляющий фигуры", где — число элементов Rвеса ) и (т. 3) Пусть , D=V2 -все 2-подмножества множества , тогда представляет помеченный граф с вершинами из V, у к-рого две вершины iи jсмежны, если )=1. Пусть w(r)=х r, тогда если w(f)=xk, то k — число ребер в графе, соответствующем отображению f. Если на Vдействует симметрич. группа Sp, то, определив для sSp подстановку gs на Dсоотношением , получают парную группу , действующую на D=V(2). Для последовательности gpk (чисел графов с рвершинами и kребрами), k=l, 2, . .. , по П. т. получают производящую функцию Для единичной группы подстановок Е n, симметрич. группы подстановок Sn и парной группы подстановок цикловой индекс имеет соответственно вид где (r, s) — наибольший общий делитель, [r, s] — наименьшее общее кратное чисел rи s, а суммирование S* проводится по k1, k2, . . ., kn при условии k1+2k2+... +nkn=n. Известны цикловые индексы для знакопеременной, циклической и диэдральной групп, а также формулы для получения цикловых индексов для произведения, декартова произведения и сплетения групп (см. [4]). Имеются обобщения П. т. на случай иного определения как веса функции, так и классов эквивалентности [1]. Лит.:[1] Де Брейн Н. Д ж., в кн.: Прикладная комбинаторная математика, пер. с англ., М., 1968, с. 61-106; [2] Сачков В. Н., Комбинаторные методы дискретной математики, М., 1977; [3] Перечислительные задачи комбинаторного анализа. Сб. переводов, М., 1978; [4] Харари Ф., Палмер 9., Перечисление графов, пер. с англ., М., 1977. В. М. Михеев.