Пойа теорема

пусть RD- множество отображений конечного множества D, |D|=n, в множество R и пусть G- группа подстановок множества D, порождающая разбиение RD на классы эквивалентности, при к-ром [img: http://localhost:8080/file/041722-45.jpg] принадлежат одному и тому же классу тогда и только тогда, когда найдется такое [img: http://localhost:8080/file/041722-46.jpg], что f1(g(d)) = f2(d).для всех [img: http://localhost:8080/file/041722-47.jpg]; если каждому [img: http://localhost:8080/file/041722-48.jpg] сопоставлен вес w(r) - элемент коммутативного кольца (вес f полагается равным [img: http://localhost:8080/file/041722-49.jpg] и вес w(F).класса [img: http://localhost:8080/file/041722-50.jpg] определяется как вес любого [img: http://localhost:8080/file/041722-51.jpg]), то [img: http://localhost:8080/file/041722-52.jpg] где в левой части равенства сумма берется по всем классам эквивалентности, а [img: http://localhost:8080/file/041722-53.jpg] есть цикловой индекс G, при этом jk(G) - число циклов длины kподстановки gв разложении ее в произведение независимых циклов. Теорема была опубликована в 1937 Д. Попа (G. Рo1уа, см. [3] с. 36-138), хотя фактически она была известна раньше (см. [3] с. 9-35). Если в качестве веса элементов R брать степени независимой переменной х(или произведение степеней нескольких переменных), то для [img: http://localhost:8080/file/041722-54.jpg] (т. н. "ряд, перечисляющий фигуры", где [img: http://localhost:8080/file/041722-55.jpg] - число элементов Rвеса [img: http://localhost:8080/file/041722-56.jpg]) и [img: http://localhost:8080/file/041722-57.jpg] (т. [img: http://localhost:8080/file/041722-60.jpg] Примеры. 1) Если [img: http://localhost:8080/file/041722-61.jpg] и тогда Р(G; т, т,..., m) - число классов эквивалентности. 2) Если R={0, 1}, w(r)= xr, то j(х)=1+х, а f [img: http://localhost:8080/file/041722-62.jpg] RD с w (f)=zk можно истолковать как подмножество Dмощности k. Группа Gиндуцирует орбиты подмножеств D, и коэффициент при xk в многочлене Р(G;1+x) есть число орбит, состоящих из подмножеств мощности k. 3) Пусть R={0, 1}, D=V2 -все 2-подмножества {i, j} множества V={1, 2,..., р}, тогда [img: http://localhost:8080/file/041722-63.jpg] представляет помеченный граф с вершинами из V, у к-рого две вершины iи jсмежны, если f({i, j})=1. Пусть w(r)=х r, тогда если w(f)=xk, то k - число ребер в графе, соответствующем отображению f. Если на Vдействует симметрич. группа Sp, то, определив для s [img: http://localhost:8080/file/041722-64.jpg] Sp подстановку gs на Dсоотношением gs{i, j}={s(i), s(j)}, получают парную группу G=S(2)={gs}, действующую на D=V(2). Для последовательности gpk (чисел графов с рвершинами и kребрами), k=l, 2,..., по П. т. получают производящую функцию [img: http://localhost:8080/file/041722-65.jpg] Для единичной группы подстановок Е n, симметрич. группы подстановок Sn и парной группы подстановок [img: http://localhost:8080/file/041722-66.jpg] цикловой индекс имеет соответственно вид [img: http://localhost:8080/file/041722-67.jpg] где (r, s) - наибольший общий делитель, [r, s] - наименьшее общее кратное чисел rи s, а суммирование S* проводится по k1, k2,..., kn при условии k1+2k2+... +nkn=n. Известны цикловые индексы для знакопеременной, циклической и диэдральной групп, а также формулы для получения цикловых индексов для произведения, декартова произведения и сплетения групп (см. [4]). Имеются обобщения П. т. на случай иного определения как веса функции, так и классов эквивалентности [1].