Теорема Рефілдера-Пойа

Означення 10. Нехай:

— група підстановок на множині

— скінчена група підстановок на зліченій множині Y, що містить не менше двох елементів;

— вагова функція, визначена на Y, зі значеннями у множині невід’ємних цілих чисел і така, що при довільному невід’ємному цілому j кількість cj його прообразів скінчена: .

Уведемо такі поняття.

1. Степеневою групою підстановок, яку позначають BA, називають таку групу:

група діє на множині усіх функцій з в

елементом групи є впорядкована пара при ;

на функцію елемент групи діє таким чином:

, .

2. Кажуть, що елемент множини має вагу , якщо .

3. Степеневий ряд змінної , який перераховує елементи множини у порядку зростання їхніх ваг і має такий вигляд:

називають «рядом переліку для фігур».

Вагу функції f з означимо як суму:

Якщо (група, що містить лише тотожне перетворення), то функції, які належать до однієї орбіти степеневої групи , мають одну й ту саму вагу, яку називають вагою орбіти.

Степеневий ряд змінної , який у випадку перераховує кількості орбіт у порядку зростання їхніх ваг і має такий вигляд:

називають «рядом переліку для конфігурацій». Тут — кількість орбіт групи з вагою .

Теорема 9. Ряд переліку конфігурацій отримують підстановкою в

цикловий індекс групи на місце кожної змінної ряду переліку фігур

Доведення.

Позначимо:

• — тотожне перетворення на ;

• — число функцій з вагою , нерухомих відносно підстановки

Обмеживши для кожного дію групи на множину функцій з вагою і

застосувавши обмежену форму леми Бернсайда, маємо:

тому

В останньому виразі ряд  перераховує всі функції, нерухомі відносно підстановки (a; e). Для кожної такої функції при всіх з маємо:

Інакше кажучи, кожна функція, нерухома відносно підстановки стала на циклах, що не перетинаються, підстановки . І навпаки: кожна функція, стала на циклах, що не перетинаються, підстановки, нерухома відносно підстановки . Розглянемо цикл довжини у довільній підстановці . Якщо функція відображає елементи циклу в один з елементів множини , то цей цикл вносить вклад у вагу функції .

При кожному невід’ємному цілому коефіцієнт при у ряді

дорівнює числу способів, якими можна означити функцію f на елементах циклу довжини k таким чином, щоб функція f була нерухомою відносно підстановки (a; e) і її вклад на вибраному циклі у вагу w (f) складав jk.

Ряд перераховує способи визначення функцій, сталих на всіх циклах довжини k підстановки a. Розглянувши всі цикли підстановки a, можемоподати отриманий раніше ряд переліку функцій, сталих на циклах, що не перетинаються, добутком:

Для завершення доведення теореми потрібно поєднати у систему останню рівність, отриману на початку доведення подання ряду та означення 4 циклового індексу.

Повідомлення про цю теорему вперше опублікував Говард Редфілд у 1927 році. На жаль, робота залишилася непоміченою, бо видалася занадто специфічною. Дьйорд Пойа (він же Джордж Поліа) опублікував своє доведення у 1937 році й виявився успішнішим популяризатором. Вже у першій його публікації на цю тему вказано на можливість застосування теореми до переліку хімічних сполук.

Дата добавления: 2015-06-27