Химия - Теорема Редфилда Пойа

01 марта 2011


Оглавление:
1. Теорема Редфилда Пойа
2. Теорема Редфилда—Пойа



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

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

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

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

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

w = \sum_{x\in X} w\left\right).

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

f \sim g\quad\Longleftrightarrow\quad f = g\circ a для некоторого a\in A.

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

Пусть

c_k = \left|\{ y\in Y \mid w=k \}\right| — число элементов Y веса k;
C_k = \left|\{ \mid w=k \}\right| — число орбит веса k;
c = \sum_k c_k\cdot t^k и C = \sum_k C_k\cdot t^k — соответствующие производящие функции.

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

Цикловой индекс подгруппы A симметрической группы Sn определяется как многочлен от n переменных t_1,t_2,\ldots,t_n

Z_A = \frac{1}{|A|}\sum_{a\in A} t_1^{j_1}\cdot t_2^{j_2}\cdot\ldots\cdot t_n^{j_n},

где jk — число циклов длины k в перестановке a.



Просмотров: 2220


<<< Поиск количественных соотношений структура-свойство
Кристаллохимия >>>