Cdtrjyty

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

История |

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

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

Пусть заданы два конечных множества X{displaystyle X} и Y{displaystyle Y}, а также весовая функция w:Y→N{displaystyle w:Yrightarrow 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:Xrightarrow Y}}. При этом вес функции f{displaystyle f} определяется как

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

Пусть на множестве X{displaystyle X} действует некоторая подгруппа A{displaystyle A} симметрической группы Sn{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)}.

Пусть

ck=|{y∈Y∣w(y)=k}|{displaystyle c_{k}=left|{yin Ymid w(y)=k}right|} — число элементов Y{displaystyle Y} веса k{displaystyle k};

Ck=|{[f]∣w([f])=k}|{displaystyle C_{k}=left|{[f]mid w([f])=k}right|} — число орбит веса k{displaystyle k};

c(t)=∑kck⋅tk{displaystyle c(t)=sum _{k}c_{k}cdot t^{k}} и C(t)=∑kCk⋅tk{displaystyle C(t)=sum _{k}C_{k}cdot t^{k}} — соответствующие производящие функции.

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

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

ZA(t1,t2,…,tn)=1|A|∑a∈At1j1(a)⋅t2j2(a)⋅…⋅tnjn(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)},}

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

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

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

C(t)=ZA(c(t),c(t2),…,c(tn)),{displaystyle C(t)=Z_{A}(c(t),c(t^{2}),ldots ,c(t^{n})),}

где ZA{displaystyle Z_{A}} — цикловой индекс группы A{displaystyle A}^[2][3].

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

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

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

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

Задача. Найти количество ожерелий, составленных из 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, то есть c0=1{displaystyle c_{0}=1} и c1=1{displaystyle c_{1}=1}. Откуда c(t)=1+t{displaystyle c(t)=1+t}.

Пусть F={f∣f:X→Y}{displaystyle F={fmid f:Xrightarrow 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} равен

ZA(t1,…,tn)=1n∑k=1ntn/(k,n)(k,n)=1n∑d∣nφ(n/d)tn/dd=1n∑d|nφ(d)tdn/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)=ZA(1+t,1+t2,…,1+tn)=1n∑d|nφ(d)(1+td)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) равно Ck{displaystyle C_{k}}, коэффициенту при tk{displaystyle t^{k}} в C(t){displaystyle C(t)}:

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

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

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

Примечания |

Литература |

• Перечислительные задачи комбинаторного анализа / Сборник переводов под редакцией Г. П. Гаврилова. — М.: Мир, 1979.


• Комбинаторная прикладная математика / Под ред. Э.Беккенбаха. — М.: Мир, 1968.


• Калужнин Л. А., Сущанский В. И. Преобразования и перестановки. — M.: Наука, 1985.


• Харари Ф. Теория графов. — М.: Мир, 1973.


• Харари Ф., Палмер Э. Перечисление графов. — М.: Мир, 1977.


• Яковенко Д. И. Задача об ожерельях // Вестник Омского университета. — 1998. — Вып. 2. — С. 21—24.


• Рыбников К. А. Введение в комбинаторный анализ. — М.: МГУ, 1972. — 253 с.


• Нефедов В. Н., Осипова В. А. Курс дискретной математики. — М.: МАИ, 1992. — 262 с.