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

Теорема (теория) Редфилда — Пойи — классический результат перечислительной комбинаторики.

История

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

Вводные определения

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

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

w ( f ) = ∑ x ∈ X w ( f ( x ) ) {displaystyle w(f)=sum _{xin X}wleft(f(x) ight)} .

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

f ∼ g ⟺ f = g ∘ a {displaystyle fsim gquad Longleftrightarrow quad f=gcirc a} для некоторого a ∈ A {displaystyle ain A} .

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

Пусть

c k = | { y ∈ Y ∣ w ( y ) = k } | {displaystyle c_{k}=left|{yin Ymid w(y)=k} ight|} — число элементов Y {displaystyle Y} веса k {displaystyle k} ; C k = | { [ f ] ∣ w ( [ f ] ) = k } | {displaystyle C_{k}=left|{[f]mid w([f])=k} ight|} — число орбит веса k {displaystyle k} ; c ( t ) = ∑ k c k ⋅ t k {displaystyle c(t)=sum _{k}c_{k}cdot t^{k}} и C ( t ) = ∑ k C k ⋅ t k {displaystyle C(t)=sum _{k}C_{k}cdot t^{k}} — соответствующие производящие функции.

Цикловой индекс

Цикловой индекс подгруппы A {displaystyle A} симметрической группы S n {displaystyle S_{n}} определяется как многочлен от n {displaystyle n} переменных t 1 , t 2 , … , t n {displaystyle t_{1},t_{2},ldots ,t_{n}}

Z A ( t 1 , t 2 , … , t n ) = 1 | A | ∑ a ∈ A t 1 j 1 ( a ) ⋅ t 2 j 2 ( a ) ⋅ … ⋅ t n j n ( a ) , {displaystyle Z_{A}(t_{1},t_{2},ldots ,t_{n})={frac {1}{|A|}}sum _{ain A}t_{1}^{j_{1}(a)}cdot t_{2}^{j_{2}(a)}cdot ldots cdot t_{n}^{j_{n}(a)},}

где j k ( a ) {displaystyle j_{k}(a)} — число циклов длины k {displaystyle k} в перестановке a {displaystyle a} .

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

Теорема Редфилда — Пойи утверждает, что

C ( t ) = Z A ( c ( t ) , c ( t 2 ) , … , c ( t n ) ) , {displaystyle C(t)=Z_{A}{ig (}c(t),c(t^{2}),ldots ,c(t^{n}){ig )},}

где Z A {displaystyle Z_{A}} — цикловой индекс группы A {displaystyle A} .

Доказательство теоремы Редфилда — Пойи опирается на лемму Бёрнсайда.

Известны многочисленные обобщения теоремы Редфилда — Пойи.

Примеры приложений

Задача о количестве ожерелий

Задача. Найти количество ожерелий, составленных из n {displaystyle n} бусинок двух цветов. Ожерелья, совпадающие при повороте, считаются одинаковыми (перевороты не допускаются).

Решение. Пусть множество X = { 1 , 2 , … , n } {displaystyle X={1,2,ldots ,n}} соответствует номерам бусинок в ожерелье, а Y = { 0 , 1 } {displaystyle Y={0,1}} — множество возможных цветов. Весовую функцию положим равной w ( y ) = y {displaystyle w(y)=y} для всех y ∈ Y {displaystyle yin Y} . Во множестве Y {displaystyle Y} имеется один элемент веса 0 и один — веса 1, то есть c 0 = 1 {displaystyle c_{0}=1} и c 1 = 1 {displaystyle c_{1}=1} . Откуда c ( t ) = 1 + t {displaystyle c(t)=1+t} .

Пусть F = { f ∣ f : X → Y } {displaystyle F={fmid f:X o Y}} — множество всех функций из X {displaystyle X} в Y {displaystyle Y} . Любая функция f ∈ F {displaystyle fin F} задаёт некоторое ожерелье и, наоборот, каждое ожерелье задаётся некоторой функцией из F {displaystyle F} . При этом вес функции равен количеству бусинок цвета 1 в соответствующем ожерелье.

На множестве X {displaystyle X} действует группа поворотов A {displaystyle A} , порожденная циклической перестановкой ( 1 , 2 , … , n ) {displaystyle (1,2,ldots ,n)} , которая определяет отношение эквивалентности на F {displaystyle F} . Тогда ожерелья совпадающие при повороте будут в точности соответствовать эквивалентным функциям, и задача сводится к подсчёту числа орбит.

Цикловой индекс группы A {displaystyle A} равен

Z A ( t 1 , … , t n ) = 1 n ∑ k = 1 n t n / ( k , n ) ( k , n ) = 1 n ∑ d ∣ n φ ( n / d ) t n / d d = 1 n ∑ d | n φ ( d ) t d n / d , {displaystyle Z_{A}(t_{1},ldots ,t_{n})={frac {1}{n}}sum _{k=1}^{n}t_{n/(k,n)}^{(k,n)}={frac {1}{n}}sum _{dmid n}varphi (n/d)t_{n/d}^{d}={frac {1}{n}}sum _{d|n}varphi (d)t_{d}^{n/d},}

где φ ( d ) {displaystyle varphi (d)} — функция Эйлера, ( k , n ) {displaystyle (k,n)} — наибольший общий делитель чисел k {displaystyle k} и n {displaystyle n} .

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

C ( t ) = Z A ( 1 + t , 1 + t 2 , … , 1 + t n ) = 1 n ∑ d | n φ ( d ) ( 1 + t d ) n / d . {displaystyle C(t)=Z_{A}(1+t,1+t^{2},ldots ,1+t^{n})={frac {1}{n}}sum _{d|n}varphi (d)(1+t^{d})^{n/d}.}

Число орбит веса k {displaystyle k} (то есть различных ожерелий с k {displaystyle k} бусинками цвета 1) равно C k {displaystyle C_{k}} , коэффициенту при t k {displaystyle t^{k}} в C ( t ) {displaystyle C(t)} :

C k = 1 n ∑ d | ( n , k ) φ ( d ) ( n / d k / d ) . {displaystyle C_{k}={frac {1}{n}}sum _{d|(n,k)}varphi (d){inom {n/d}{k/d}}.}

Общее число различных орбит (или ожерелий) равно

∑ k C k = C ( 1 ) = 1 n ∑ d | n φ ( d ) 2 n / d . {displaystyle sum _{k}C_{k}=C(1)={frac {1}{n}}sum _{d|n}varphi (d)2^{n/d}.}