Теорема Редфилда — Пойи

---

Впервые эта теорема была получена и опубликована Редфилдом^[англ.] в 1927 году, но работа была сочтена весьма специальной и осталась незамеченной. Пойа независимо доказал то же самое в 1937 году, но оказался куда более успешным популяризатором — так, например, в первой же публикации он показал применимость этого результата к перечислению химических соединений^[1].

Пусть заданы два конечных множества ${\displaystyle X}$ и ${\displaystyle Y}$, а также весовая функция ${\displaystyle w:Y\rightarrow \mathbb {N} }$. Положим ${\displaystyle n=|X|}$. Без потери общности можно считать, что ${\displaystyle X=\{1,2,\ldots ,n\}}$.

Рассмотрим множество функций ${\displaystyle F=\{f\mid f:X\rightarrow Y\}}$. При этом вес функции ${\displaystyle f}$ определяется как

Пусть на множестве ${\displaystyle X}$ действует некоторая подгруппа ${\displaystyle A}$ симметрической группы ${\displaystyle S_{n}}$. Введем отношение эквивалентности на ${\displaystyle F}$

Класс эквивалентности ${\displaystyle f}$ обозначим через ${\displaystyle [f]}$ и будем называть орбитой ${\displaystyle f}$. Так как веса эквивалентных функций совпадают, то можно определить вес орбиты как ${\displaystyle w([f])=w(f)}$.

---