У публікації стисло висвітлено елементи теорії переліку ізоморфних графів, детально викладеної у роботі [1], що базується на оригінальних роботах [2–5]. Для зручності сприйняття публікації учнями загально освітніх навчальних закладів у розділі 1 викладено початки теорії груп. Публікацію адресовано:

• учням класів з поглибленим вивченням математики;

• студентам вищих навчальних закладів, які навчаються за спеціальністю «Математика» чи «Прикладна математика»;

• вчителям математики й інформатики класів з поглибленим вивченням математики.

1. Група

Означення 1. Множину G називають групою, якщо справджуються такі висловлювання.

1. Задано закон множення (композиції), який впорядкованій парі (a; b) елементів G ставить у відповідність добуток ab — елемент G, який називають добутком b на a зліва або добутком a на b справа.

2. Справджується сполучний закон множення: (ab) c = a (bc).

3. Існує ліва одиниця множення (нейтральний елемент) групи e, тобто такий елемент групи, множення на який зліва не змінює жоден елемент групи: ex = x.

4. Для довільного елемента а групи існує лівий обернений до нього а^– 1, тобто такий, при якому добуток оберненого елемента на сам елемент дорівнює лівій одиниці множення: а^– 1 a = e.

Групу називають комутативною (абелевою), якщо множення комутативне, тобто добуток не залежить від порядку співмножників: ab = ba.

Закон асоціативності множення формулюють ще й так: добуток не залежить від порядку виконання дії множення (не плутати з порядком співмножників). Саме у такій редакції його потрібно поширити на більшу кількість співмножників, розуміючи добуток як, наприклад, результат виконання дії множення у порядку запису зліва направо: abc = (ab) c, abcd = ((ab) c) d і т. і. Множина взаємно однозначних відображень довільної множини в себе є групою щодо суперпозиції, тобто послідовного застосування відображень.

Теорема 1. Для довільної групи справджуються такі висловлювання.

1. Лівий обернений елемент є також правим оберненим елементом, який для кожного елемента групи єдиний: a а^– 1 = e.

2. Ліва одиниця є також правою одиницею, тобто множення на неї справа не змінює жоден елемент групи: ae = a.

3. Одиниця множення у групі єдина.

Доведення:

• помножимо зліва рівність а^– 1 aа^– 1 = а^– 1 на елемент, обернений до а^– 1 і використаємо асоціативність множення. В результаті отримаємо: a а^– 1 = e, тобто лівий обернений елемент є також правим оберненим;

• a = ea = (a а^– 1) a = a (а^– 1 a) = ae, тобто кожна ліва одиниця є одночасно правою одиницею;

• помноживши зліва і справа довільний елемент a групи на його обернені b і c та по-різному розставляючи дужки, тобто використовуючи асоціативність множення, легко пересвідчитися, що обернений елемент єдиний: b = b (ac) = (ba) c = c;

• обчислюючи добуток e та e' — (одночасно лівих і правих) одиниць групи —, легко пересвідчитися, що одиниця групи єдина: e = ee' = e'.

Означення 2. Запровадимо такі поняття.

1. Непорожню підмножину A групи G називають підгрупою групи G, якщо:

   • добуток двох елементів A також належить до A;

   • елемент, обернений до елемента з A також належить до A.

2. Нехай A — підгрупа групи G. Правим класом групи G за підгрупою A називають множину вигляду Ax = {ax | a ∈ A}, де x — довільний елемент групи G (аналогічно означають лівий клас суміжності).

3. Підстановкою називають взаємно однозначне відображення скінченої множини у себе. Не обмежуючи загальності міркувань, надалі будемо розглядати лише множини вигляду {1, 2, ... , n} — множини всіх перших n натуральних чисел.

4. Транспозицією називають підстановку, яка кожному елементу, за виключенням двох, ставить у відповідність цей самий елемент.

5. Множину всіх підстановок на множині {1, 2, …, n} при сталому n називають симетричною групою і позначають S_n.

6. Порушенням порядку підстановки на множині {1, 2, …, n}, що числу j ставить у відповідність число i_j при j = 1, 2, …, n, називають сумісну систему таких двох нерівностей: j < k та i_j > i_k.

7. Підстановку називають парною, якщо кількість транспозицій, у добуток яких можна розкласти дану підстановку, є парною.

8. Множину всіх парних підстановок на множині {1, 2, …, n} при натуральному n називають знакозмінною групою і позначають A_n .

9. Циклом довжини k називають підстановку, яка певний елемент j₁ відображає у деякий елемент j₂, j₂ — в j₃ , …, j_k – 1 — в j_k , j_k — в j₁ за умови, що всі елементи j₁, j₂, …, j_k — різні. Такий цикл позначають (j₁ j₂ … j_k).

10. Дві групи називають ізомофними, якщо існує взаємно однозначне відображення f однієї групи в іншу, при якому образ добутку елементів однієї групи є добутком образів співмножників у тому самому порядку: f (ab) = f (a) f (b). Таке відображення f називають ізоморфізмом відповідних груп.

Зауваження 1. Справджуються такі висловлювання.

1. Транспозиція, що пересталяє сусідні натуральні числа, змінює кількість порушень порядку на 1.

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

3. Парність кількості транспозицій у розкладі підстановки не залежить від конкретного подання добутком транспозицій і збігається з парністю кількості порушень порядку.

4. Цикл з непарної довжиною є добутком парної кількості транспозицій.

5. Цикл з парної довжиною є добутком непарної кількості транспозицій.

6. Підстановка є парною тоді й лише тоді, коли її подання добутком циклів без спільних елементів містить парну кількість циклів парної довжини.

Зауваження 2. Довільну підстановку можна подати добутком циклів без спільних елементів.

Наприклад:

• S₃ ={(1)(2)(3), (12)(3), (13)(2), (23)(1), (123), (132)} — група всіх симетрій правильного трикутника (вказано дію на вершинах, занумерованих числами 1, 2 і 3);

• A₃ ={(1)(2)(3), (123), (132)} — група поворотів правильного трикутника навколо його центра на 0°, 120° і 240°.

Зауваження 3. Для довільної скінченої групи множення справа (зліва) на певний елемент задає підстановку на множині елементів цієї групи. Тому довільна скінчена група ізоморфна підгрупі S_n , де n = | G | — кількість елементів групи G.

Зауваження 4. Класи суміжності за однією підгрупою мають однакову кількість елементів, що збігається з кількістю елементів підгрупи.

2. Твірна функція

Означення 3. Твірною функцією послідовності a₀, a₁, a₂, ... називають степеневий ряд такого вигляду:

Надалі такі ряди будемо розглядати формально, тобто не досліджуючи питання збіжності, але використовуючи операції додавання, множення і (почленного) диференціювання твірних функцій. У задачах переліку числа a₁, a₂, ... — кількості об'єктів з певними властивостями. Тому твірну функцію називають рядом переліку.

Теорема 2. Якщо A(x) = e^a(x) при

то при довільному натуральному j справджується така рівність:

Доведення. A' (x) = e^a(x) a' (x) = A(x) a' (x), тобто

Коефіцієнти при x ^{j – 1} лівої та правої частин цієї рівності відповідно дорівнюють:

звідки й випливає твердження теореми.

3. Циклові індекси групи підстановок

Означення 4. Запровадимо такі позначення й поняття.

1. Позначимо через j_k(a) кількість усіх циклів довжини k, що входять у розклад підстановки a на цикли без спільних елементів. Тут k лежить в межах від 1 до n — кількості об'єктів множини, на якій діє підстановка.

2. Характеристикою підстановки a називають впорядкований набір вигляду

   ( j₁(a), j₂(a), …, j_n(a)).

3. Цикловим індексом групи підстановок G на множині n елементів називають многочлен n змінних x₁, x₂, …, x_n такого вигляду:

   		n
   |G | –1	∑	∏	xk jk(a).
   	a ∈ G	k = 1

   Такий многочлен позначають Z(G, x₁, x₂, …, x_n) або Z(G).

Зауваження 5.

де додавання здійснюють за всіма можливими характеристиками с елементів групи, h(с) — кількість елементів групи з характеристокою с = (j₁(a), j₂(a), ..., j_n(a)).

Наприклад:

• Z(S₃ ) = (x₁³ + 3x₁x₂ + 2x₃ )/6 ;
• Z(A₃ ) = (x₁³ + 2x₃ )/3 .

Теорема 3. При всіх натуральних j справджуються такі рекурентні співвідношення:

Доведення. Для довільної підстановки a позначимо через l(a) довжину циклу, що містить j-ий елемент. Маємо:

При сталому l(a) = l доданки під знаком першої суми (при прогляданні виразу справа наліво — у порядку обчислення) в останньому виразі ті самі, що й для відповідної суми для Z(S_j – l). Кратність кожного такого доданку дорівнює кількості циклів довжини l, що містять j-ий елемент. Згідно з комбінаторним правилом множення таку кількість можна подати добутком:

Врахувавши множник перед знаком другої суми, отримаємо твердження теореми.

Теорема 4.

Доведення. Див. твердження попередньої теореми й доведення теореми 2.

4. Лема Коші — Фробеніуса (Бернсайда)

Означення 5. Нехай A — група підстановок на деякій множині X. Наприклад, X = {1, 2, …, n}. Запровадимо такі поняття.

1. Елементи x та y множини X називають A-еквівалентними, якщо існує така пiдстановка a з A, при якій ax = y.

2. Множину A-еквівалентних між собою елементів називають орбітою.

3. Для кожногого x з множини X означимо стабілізатор елемента x як множину всіх тих підстановок з A, які залишають нерухомим x, і позначимо її через A(x) :

Зауваження 7.

1. Відношення A-еквівалентності насправді є відношенням еквівалентності, бо A — група. Тому розбиття на орбіти є розбиттям на класи еквівалентності.

2. Стабілізатор довільного елемента є підгрупою початкової групи підстановок.

3. Якщо x та y належать до однієї орбіти, то їхні стабілізатори є спряженими підгрупами групи A. Інакше кажучи, існує такий елемент a групи A, при якому справджується рівність:

   A(x) = a A(y) a ^{– 1}.

   У цьому випадку | A(x) | = | A(y) |.

Теорема 5. Для довільного елемента y з орбіти Y групи A справджується така рівність:

| A | = | A(y) | ∙ | Y |

Доведення. Подамо групу A об'єднанням правих класів суміжності a_j A(y) за підгрупою A(y). Позначимо кількість таких класів суміжності через m. Для кожного j = 1, 2, …, m класу суміжності a_j A(y) поставимо у відповідність елемент a_j y з орбіти Y.

1. При різних a_j і a_k різними також є a_j y і a_k y, бо інакше добуток a_j^–1a_k належить до групи A(y), а тому a_k належить до a_j A(y). Останнє висловлювання суперечить відсутності спільних елементів множин a_j A(y) та a_k A(y), тобто розбиттю на класи суміжності. Отже, вказане відображення є відображенням «в» (ін'єкцією).

2. Згідно з означенням орбiти, для довільного елемента y' орбіти Y існує елемент a групи A, при якому y' = ay. У свою чергу, згідно з розбиттям A на праві класи суміжності a_j A(y), існують a_j та елемент b групи A(y), при яких a = a_j b. В результаті маємо:

   y' = ay = a_j by = a_j y.

   Отже, вказане відображення є відображенням «на» (сюр'єкцією). Інакше кажучи, кожний елемент орбіти Y є образом деякого класу суміжності.

Таким чином, доведено існування взаємно однозначного відображення з множини класів суміжності в обіту Y, тому вони мають однакову кількість елементів. Теорему доведено.

Теорема 6. Кількість N(A) орбіт групи підстановок A дорівнює середньому арифметичному кількості нерухомих точок групи A:

Доведення. Позначимо через Y₁, Y₂, ... , Y_m різні орбіти групи A. Для кожного j = 1, 2, …, m виберемо довільним чином елемент y_j з Y_j . Додавши праві та ліві частини рівностей у твердженні попередньої теореми, записаних для Y = Y_j для кожного j = 1, 2, …, m, отримаємо таку рівність:

Вже встановлено, що для елементів з однієї орбіти їхні стабілізатори спряжені, а тому мають однакову кількість елементів. Праву частину останньої рівності можна подати таким чином:

Теорему доведено.

Теорему 6, широко відому як лема Бернсайда, опублікували раніше Огюстен Коші [2] та Фердінанд Георг Фробеніус [3].

Зауваження 8 (обмежена форма). Якщо:

• група підстановок A діє на множині X;
• Y — об'єднання орбіт групи A, що є підмножиною X;
• A | Y — група підстановок, отримана звуженням дії A на Y;
• j₁(a | Y ) — кількість елементів Y, нерухомих відносно підстановки a,

то справджується така рівність:

5. Теорема Редфілда — Пойа

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

• A — група підстановок на множині X = {1, 2, ... , n};

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

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

Запровадимо такі поняття.

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

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

   • елементом групи є впорядкована пара (a; b) при a ∈ A, b ∈ B;

   • на функцію f елемент групи (a; b) діє таким чином:

   ((a; b) f ) (x) = bf (ax)   при всіх x з X.

2. Кажуть, що елемент y множини Y має вагу j, якщо w(y) = j.

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

   	+ ∞
   c(x) =	∑	сj x j,
   	j = 0

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

4. Вагу w( f ) функції f з Y ^X означимо як суму:

   w( f ) =	∑	w( f (x))
   	x ∈ X

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

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

   	∞
   С(x) =	∑	Сj x j,
   	j = 0

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

Теорема 7. Ряд С(x) переліку конфігурацій отримують підстановкою в цикловий індекс Z(A, x₁, x₂, …, x_n) групи A на місце кожної змінної x_j ряду c(x^j) переліку фігур:

Доведення. Позначимо:

• e — тотожнє перетворення на Y;
• C_j(a) — число функцій з вагою j, нерухомих відносно (a; e).

Обмеживши для кожного j дію групи E ^A на множину функцій з вагою j і застосувавши обмежену форму леми Бернсайда, маємо:

тому

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

Інакше кажучи, кожна функція, нерухома відносно підстановки (a; e), стала на циклах, що не перетинаються, підстановки a. І навпаки: кожна функція, стала на циклах, що не перетинаються, підстановки a, нерухома відносно підстановки (a; e).

Розглянемо цикл довжини k у довільній підстановці a. Якщо функція f відображає елементи цикла в один з c_j елементів множини {y ∈ Y | w(y) = j}, то цей цикл вносить вклад  jk  у вагу функції f.

При кожному невід'ємному цілому k коефіцієнт при x ^jk у ряді

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

Ряд (c(x ^k)) ^j_k(a) перераховує способи визначення функцій, сталих на всіх циклах довжини k підстановки a.

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

+ ∞		n
∑	Cj(a) x j =	∏	(c(x k)) jk(a).
j = 0		k = 1

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

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

6. Перелік розфарбувань

Зауваження 9. Якщо в умові теореми 7:

• | Y | = m — натуральне число;
• w(y) = 1 — стала на елементах Y вагова функція,

то кількість орбіт дорівнює такій величині:

C(1) = Z(A, c(1), c(1), …, c(1)) = Z(A, m, m, …, m).

Якщо при цьому:

• A — група підстановок, що діють на множині вершин деякого неорієн­тованого графа і зберігають суміжність вершин;

• m — кількість кольорів, якими можна розфарбовувати вершини деякого графа,

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

У свою чергу граф може бути моделлю геометричної фігури, наприклад, регулярного многогранника. Іншими словами, вершинами графа є вершини, ребра чи грані многогранника. Тоді знайдена кількість C(1) є кількістю різних способів розфарбування геометричної фігури.

Знайдемо кількість способів розфарбування вершин (сторін) правильного трикутника жовтим і блакитним кольором: m = 2.

1. Z(S₃) = (x₁³ + 3x₁x₂ + 2x₃ )/6, тому допустивши всі рухи, маємо:
   С(1) = (2³ + 3 ∙ 2 ∙ 2 + 2 ∙ 2)/6 = 4.
2. Z(A₃) = (x₁³ + 2x₃ )/3, тому допустивши лише повороти, маємо:
   С(1) = (2³ + 2 ∙ 2)/3 = 4.

В обох розглянутих випадках є такі 4 способи розфарбування:

• три вершини пофарбовано жовтим кольором;
• дві вершини пофарбовано жовтим кольором і одну — блакитним;
• одну вершину пофарбовано жовтим кольором і дві — блакитним;
• три вершини пофарбовано блакитним кольором.

Алгоритм обчислення кількості розфарбувань можна подати у такому вигляді.

1. При всіх натуральних k в межах від 1 до | A | змінній p_k надати величину 0.

2. Для кожного елемента групи симетрій A:

   • знайти j — кількість циклів, на які він розкладається;
   • збільшити на 1 величину p_j.

3. Обчислити шукану кількість:

(p₁ ∙ m + p₂ ∙ m² + p₃ ∙ m³ + ⋯ + p_{| A |} ∙ m^{| A |}) : | A |.

Вкажемо на зв'язок матеріалу публікації зі змістом завдань учнівських олімпіад з інформатики. У 2001–2006 автор публікації одноосібно упорядковував завдання орієнтовні завдання для ІІ (районного) і ІІІ (міського) етапу Всеукраїнської учнівської олімпіади з інформатики у місті Києві. При цьому робився наголос на алгоритмічно змістовних задачах, теоретичні основи яких не виходять за межі навчальних програм поглибленого вивчення математики. Поняття симетрії і неявне запровадження групи симетрій платонових тіл — обов'язковий фрагмент такої навчальної програми. Тому:

• орієнтовні завдання ІІ етапу учнівської олімпіади з інформатики у місті Києві 2004 року містили задачу подання підстановки добутком циклів без спільних елементів. При цьому вхідні дані містили інформацію про підстановку на множині вершин чи граней правильного многогранника, яка (підстановка) відповідали симетрії многогранника;

• завдання ІІІ етапу учнівської олімпіади з інформатики у місті Києві 2005 року містили задачу, у якій потрібно було знайти групу симетрій регулярного многогранника за інформацією про суміжність граней. Точніше, потрібно було знайти подання групи дією на множині граней. Далі потрібно було перебрати дерева — моделі різних одноколірних розгорток многогранника.

Синтезом розв'язань вказаних двох задач з використанням теореми 7 можна отримати оптимальне розв'язання задачі про кількість розфарбувань вершин, ребер чи граней регулярних многогранників. Відверто кажучи, на момент упорядкування завдань автор не був знайомий зі змістом теореми Редфілда — Пойа і не був впевнений у:

• доступності теоретичного матеріалу;

• можливості програмної реалізації відповідних алгоритмів в умовах проведення учнівської олімпіади з інформатики.

Зараз ця впевненість уже, бо матеріал статті «обкатано» на учнях 10 і 11 класів під час викладання спеціального курсу «Прикладна математика» у Києво-Печерському ліцеї № 171 «Лідер». Зауважимо: від учасника олімпіади вимагається вміння використати лише кінцевий результат, а не відтворити його отримання. Але така задача буде посильною лише для фаворитів змагань, що претендують на участь у Міжнародній олімпіаді з інформатики.

Розглянемо популярну у навчальній літературі задачу про знаходження кількості різних намист, що складаються з намистинок k кольорів і містять по p намистинок. Два намиста вважають різними, якщо їх не можна сумістити рухами у площині.

Нехай p — просте число. У цьому випадку група поворотів намиста має вигляд Z_p = {e, a, a², …, a ^p – 1}, де:

• e = (1)(2)…(p) — тотожнє перетворення, що має характеристику (p, 0, 0, 0, 0) і якому відповідає доданок x₁^p у цикловому індексі;

• a = (2, 3, …, p, 1) — поворот на одну намистинку, що характеристику (0, 0, …, 0, 1) і якому відповідає доданок x_n у цикловому індексі;

• повороти a², a³, … , a ^{p – 1} мають таку саму характеристику, що й a. Тому їм відповідає той самий доданок x_n у цикловому індексі.

Цикловий індекс групи:

Z(Z_p, x₁, x₂, …, x_p) = (x₁^p + ( p – 1) x_p) : p.

Шукана кількість різних намист:

Z(Z_p, k, k, …, k) = (k ^p + ( p – 1) k) : p.

Якщо p — відмінне від 1 не просте натуральне число, то цикловий індекс Z(A, x₁, x₂, …, x_n) дорівнює такому виразу:

	n
n–1	∑	(xn/НСД(k, n)) НСД(k, n) = n–1	∑	φ(n/d ) (xn/d) d = n–1	∑	φ(d ) xd n/d.
	k = 1		d | n		d | n

Тут:

• НСД(k, n) — найбільший спільний дільник натуральних k і n;

• φ(d ) — функція Ейлера — кількість натуральних чисел, які не перевищують d і взаємно прості з ним;

• додавання здійснюють за всіма d — натуральними дільниками n.

У загальному випадку шукана кількість різних намист така:

n–1	∑	φ(d ) k n/d.
	d | n

Використаємо отриманий результат для аналізу задачі зі зміненою умовою: знайти кількість різних намист, що складаються з намистинок k кольорів, містять по p намистинок і в яких поряд не зустрічаються намистинки одного кольору. Будь-яке таке намисто з його розташуванням можна задати таким чином:

• вказати колір однієї намистинки s₁;

• задати послідовність p натуральних чисел {t_j} (j = 1, 2, …, p) у межах від 1 до k – 1 включно.

При цьому колір кожної наступної намистини s_j + 1 має таку саму остачу від ділення на k, що й s_j + t_j. Така залежність гарантує відсутність пари сусідніх намистин одного кольору. Для сумісності висловлювань щодо кольорів усіх намистин потрібно накласти таку додаткову умову: сума t₁ + t₂ + ⋯ + t_p кратна k. Знайдемо кількістю усіх можливих послідовностей {t_j} без останнього обмеження з точністю до поворотів на площині таким чином.

1. Покладемо: w( j ) = j при j = 1, 2, …, k – 1.

2. Отримаємо: c_j = 1 при j = 1, 2, …, k – 1, тому

   c(x) = x¹ + x² + ⋯ + x ^{k– 1}.

3. Знайдемо ряд С(x) переліку конфігурацій підстановкою в цикловий індекс Z(A, x₁, x₂, …, x_n) групи поворотів A на місце кожної змінної x_j ряду c(x ^j ) переліку фігур:

   C(x) = Z(A , c(x) , c(x²) , ... , c(xⁿ)).

4. Знайдемо суму коефіцієнтів ряду переліку конфігурацій з індексами, що кратні k:

   С_k + С_2k + С_3k + ⋯ .

   Шукана кількість класів еквівалентних послідовностей дорівнює цій сумі.

Таблиця 1
Кількість різних щодо циклічних підстановок
довжини n (номери рядків)
послідовностей n натуральних чисел
у межах від 1 до k – 1,
сума яких кратна k (номери стовпчиків)

	2	3	4	5	6	7	8	9	10	11	12	13	14	15
2	1	0	1	0	1	0	1	0	1	0	1	0	1	0
3	1	2	2	2	6	6	12	22	36	62	120	210	394	734
4	2	2	8	12	34	78	214	548	1490	4026	11112	30660	85490	239158
5	2	4	14	44	140	468	1646	5828	21000	76260	279700	1032444	3835028	14316604
6	3	8	29	104	447	1860	8167	36184	162867	739820	3391341	15650040	72662763	339084416
7	3	10	48	222	1118	5718	30018	159970	863916	4711650	25914668	143524110	799637202	4477952390
8	4	14	80	420	2468	14706	90160	560476	3531364	22469622	144182608	931625100	6055577860	39563012874
9	4	20	116	728	4872	33288	233076	1657052	11930832	86767016	636294120	4698767640	34905147688	260624979908
10	5	24	169	1184	8885	68328	538253	4304688	34869045	285282360	2353588465	19552814064	163405728725	1372607548184
11	5	30	230	1818	15170	129870	1136480	10101030	90910004	826446290	7575765320	69930069930	649350714290	6060606061842
12	6	38	312	2684	24654	231990	2233222	21832924	216147894	2161452050	21794666808	221299436820	2260415908086	23206934279930
13	6	44	402	3828	38308	393756	4134642	44100716	476289336	5195862732	57154509484	633095889828	7054497254844	79010367051748
14	7	52	517	5304	57519	640296	7283827	84162728	984708823	11637405156	138679135969	1664148937320	20088655669411	243742347689724
15	7	62	644	7174	83706	1003938	12298566	153044914	1928367980	24542819210	314966223012	4070332170534	52914318718918	691413758049314

7. Перелік неорієнтованих дерев з виділеною вершиною-коренем

Означення 7. Запровадимо такі поняття.

1. Графи називають ізоморфними, якщо існує взаємно однозначне відображення вершин одного графа у вершини іншого графа, що зберігає суміжність вершин.

2. Взаємно однозначне відображення вершин одного графа у вершини іншого графа, що зберігає суміжність вершин, називають ізоморфізмом графів.

3. Підстановка на множині вершин графа, що зберігає суміжність вершин, називають автоморфізмом графа.

4. Коли говорять про ізоморфізм чи автоморфізм графа з виділеною вершиною-коренем чи виділеним ребром, то крім збереження суміжності вершин вимагають, щоб образ виділеного елемента був виділеним.

Запровадимо такі позначення:

T_j — кількість різних (неізоморфних) неорієнтованих дерев з виділеною вершиною-коренем, що мають j вершин;

	+ ∞
T(x) =	∑	Tj x j = x + x2 + 2x3 + 4x4 + ⋯
	j = 1

— твірна функція неорієнтованих дерев з виділеною вершиною-коренем.

Рис.1. Неізоморфні кореневі дерева, порядок яких не перевищує 4. Корені виділено кругами більшого радіусу.

Теорема 8. Ряд T(x) переліку неорієнтованих кореневих дерев задовольняє таке співвідношення:

	+ ∞
T(x) = x exp(	∑	T(x j ) / j).
	j = 1

Доведення. Спочатку розглянемо лише такі неорієнтовані кореневі дерева, у яких степінь кореня сталий і дорівнює деякому натуральному n. Інакше кажучи, у таких деревах корінь є кінцем n різних ребер. Зауважимо: довільне таке дерево можна подати як результат такого перетворення сукупності n кореневих дерев: долучається ще одна точка-корінь, що стає безпосереднім предком коренів n кореневих дерев, заданих спочатку.

Запровадимо такі позначення:
X = {1, 2, ... , n};
Y — множина всіх неорієнтованих кореневих дерев;
E — група з одним елементом (одиницею групи);
E^S_n — степенева група з множиною об'єктів Y ^X.

Кожна функція з Y^X задає впорядкований набір (кортеж) n неорієнтованих кореневих дерев. Означимо вагу довільного дерева з Y як кількість його вершин. Тоді твірна фунція T(x) є рядом, що перераховує фігури (неорієнтовані кореневі дерева) у порядку зростання їхніх ваг. Згідно з зауваженням, виділеним курсивом, кожна орбіта степеневої групи E^S_n відповідає деякому кореневому дереву, корінь якого має степінь n. Вага такої орбіти на 1 менша від кількості вершин того кореневого дерева, що ставлять у взаємно одназначну відповідність орбіті. Взявши у теоремі 7 A = S_n і c(x) = T(x), отримаємо ряд переліку функцій (конфігурацій):

Z(S_n, T(x), …) = Z(S_n, T(x), T(x²), …, T(xⁿ)).

Коефіцієнт при x ^j у степеневому розкладі x Z(S_n, T(x), …) дорівнює числу неорієн­тованих кореневих дерев з j вершинами. При цьому степінь кореня всіх таких дерев дорівнює n. Здійснивши додавання за всіма можливими невід'єм­ними цілими n, отримаємо таке:

	+ ∞
T(x) = x	∑	Z(Sn , T(x) , T(x2) , …, T(xn)).
	n = 0

Для завершення доведення теореми достатньо записати твердження теореми 4 для x = 1, а після «вивільнення» змінної x покласти x_j = T(x ^j) при всіх натуральних j.

Теорема 9. Кількості неорієнтованих кореневих дерев з різною кількістю вершин задовольняють таке рекурентне співвідношення:

	j
Tj + 1 = j –1	∑	k ak Tj – k + 1,
	k = 1

де

ak = k –1	∑	d Td
	d | k

при довільному натуральному k.

Доведення. Справдження останньої рівності при довільному натуральному k означає збіг степеневих рядів:

+ ∞		+ ∞
∑	ak x k =	∑	T(x l ) / l .
k = 1		l = 1

Для завершення доведення теореми потрібно скористатися попередньою теоремою 8 та теоремою 2 про експоненту твірної функції.

Перші 333 члени послідовності {T_j} опубліковано на сайті «Київські учнівські олімпіади з інформатики».

8. Перелік неорієнтованих дерев з виділеним ребром

Означення 8. Запровадимо такі поняття.

1. Граф, у якому виділено ребро, називають реберно-кореневим графом.

2. Виділене ребро в реберно-кореневому графі називають кореневим ребром.

3. Ребро графа називають симетричним, якщо існує автоморфізм графа, що міняє кінці цього ребра місцями.

Запровадивши серед вершин графа відношення еквівалентності «розташування по один бік від обраного ребра», можна пересвідчитися в істинності такого вислов­лювання.

Зауваження 10. Кількість симетричних ребер у довільному дереві не перевищує 1.

Теорема 10. Запровадимо такі позначення:

L_j — кількість різних (тобто неізоморфних) реберно-кореневих неорієнтованих дерев порядку j (тобто дерев, що мають j вершин);

	+ ∞
L(x) =	∑	Lj x j
	j = 1

— твірна функція реберно-кореневих неорієнтованих дерев. Маємо:

L(x) = (Т ²(x) – Т(x²))/2.

Доведення. Кореневе ребро розбиває реберно-кореневе неорієнтоване дерево на два кореневі неорієнтовані дерева. Тому L_j дорівнює кількості різних невпорядкованих пар кореневих неорієнтованих дерев за умови, що у кожній такій парі загальна кількість вершин дорівнює j.

При непарному j кожна така пара містить різні кореневі дерева:

	j – 1
Lj =	∑	Tk Tj – k / 2 .
	k = 1

При парному j серед усіх таких пар знайдеться T_j/2 пар, що мають однакові елементи:

	j – 1
Lj = (	∑	Tk Tj – k – Tj/2 ) / 2 .
	k = 1

Помноживши обидві частини останніх двох рівностей на x ^j і здійснивши додавання за всіма натуральними j, отримаємо твердження теореми.

9. Перелік неорієнтованих дерев

Означення 9. Запровадимо такі поняття.

1. Вершину графа називають точкою сполучення, якщо при видаленні її разом з інциндентними ребрами кількість компонент зв'язності графа зростає щонайменше на 1.

2. Зв'язний граф без точок сполучення називають двозв'язним.

3. Максимальні за вмістом (вершин і ребер) двозв'язні підграфи називають двозв'язними компонентами або блоками.

4. Нехай A(G) — група автоморфізмів графа G. Дві вершини (два ребра, два блоки) цього графа називають A(G)-еквівалентними (подібними), якщо існує авто­морфізм графа G, що відображає одну вершину в іншу (одне ребро в інше, один блок в інший).

5. Дві вершини (два ребра, два блоки) графа G називають неподібними, якщо вони не є еквівалентними щодо групи A(G) автоморфізмів цього графа.

Теорема 11. Для довільного графа G запровадимо такі позначення:

• p — кількість неподібних вершин, тобто кількість класів еквівалентності подібних вершин;

• b — кількість неподібних блоків, тобто кількість класів еквівалентності подібних блоків;

• p_j — кількість неподібних вершин j-го блоку при j = 1, 2, ... , b.

Маємо:

	b
p – 1 =	∑	( pj – 1).
	j = 1

Доведення (методом математичної індукції за кількістю класів еквівалентності подібних блоків).

1. База індукції. При b = 1 маємо: p = p₁, тому твердження теореми справджується.

2. Припущення індукції. Припустимо, що твердження теореми справджується для довільного графа, у якому кількість неподібних блоків не перевищує певне натуральне b.

3. Крок індукції. Нехай кількість різних класів еквівалентності блоків графа дорівнює b + 1. Розглянемо серед блоків той, що має лише одну точку сполучення. Необмежуючи загальності міркувань, занумеруємо класи еквівалентності таким чином, щоб вибраний клас мав номер b + 1. Вилучимо з графа вершини всіх блоків, що належать до цього класу еквівалентності, за виключенням точок сполучення. Новостворений граф має b різних класів блоків, тому для нього справджується припущення індукції. При цьому кількість різних класів еквівалентності вершин новоствореного графа дорівнює p – ( p_b + 1 – 1). Тому твердження теореми справджується і для початкового графа.

Зауваження 11. У довільному неорієнтованому дереві блоком є ребро, тому для кожного такого блоку-ребра маємо: p_j = 2. Виключення складає симетричне ребро, у якому ця кількість дорівнює 1. Позначивши через s кількість симетричних ребер, що не перевищує 1, твердження теореми 11 запишемо таким чином: p – (b – s) = 1.

Теорема 12. Запровадимо такі позначення:

t_j — кількість різних (тобто неізоморфних) неорінтованих дерев порядку j (тобто дерев, що мають j вершин);

	+ ∞
t(x) =	∑	tj x j
	j = 1

— твірна функція неорієнтованих дерев. Маємо:

t(x) = Т(x) – (Т²(x) – Т(x²))/2,

де Т(x) — твірна функція кореневих неорієнтованих дерев.

Доведення. Розглянемо рівність 1 = p – (b – s) у позначеннях теореми 11 і зауваження 11 для усіх неорієнтованих дерев, що мають сталу кількість вершин j. Здійснивши додавання за всіма такими деревами, отримаємо: t_j = T_j – L_j при довільному натуральному j. Перейшовши до твірних функцій, отримаємо: t(x) = Т(x) – L(x) і скористаємося твердженням теореми 10 для завершення доведення.

Рис.2. Неізоморфні дерева, порядок яких не перевищує 5.

Перші 333 члени послідовності {t_j} опубліковано на сайті «Київські учнівські олімпіади з інформатики». Маємо:

t(x) = x + x² + x³ + 2x⁴ + 3x⁵ + ⋯ .

10. Перелік орієнтованих дерев з виділеною вершиною-коренем

Запровадимо такі позначення:

R_j — кількість різних (неізоморфних) орієнтованих дерев з виділеною вершиною-коренем, що мають по j вершин;

	+ ∞
R(x) =	∑	Rj x j = x + 2x2 + 7x3 + ⋯
	j = 1

— твірна функція кореневих орієнтованих дерев.

Рис.3. Неізоморфні кореневі орієнтовані дерева, порядок яких не перевищує 3.
Корені виділено кругами більшого радіусу.

Теорема 13. Ряд R(x) переліку кореневих орієнтованих дерев задовольняє таке співвідношення:

	+ ∞
R(x) = x exp2(	∑	R(x j) / j) .
	j = 1

Доведення. Позначимо через R^*(x) ряд переліку орієнтованих дерев з виділеним коренем, що має степінь 1 (корінь є початком чи кінцем лише однієї дуги). Існує взаємно однозначна відповідність між довільною n-елементною (невпорядкованою) множиною таких дерев і орієнтованим деревом, у якому корінь інциндентний n вершинам. Застосувавши теорему 7 Редфілда — Пойа до симетричної групи S_n з використанням ряду переліку фігур R^*(x)/x, отримаємо ряд переліку функцій

Z(S_n, R^*(x)/x, …).

У цьому ряді коефіцієнт при x ^j  дорівнює кількості орієнтованих кореневих дерев, що містять по j + 1 вершині та у яких корені інциндентні n вершинам. Здійснивши додавання за всіма невід'ємними цілими n, отримаємо таке подання:

	+ ∞
R(x) = x	∑	Z(Sn, R*(x)/x, R*(x2)/x2, …, R*(xn)/xn).
	n = 0

Для кожного орієнтованого дерева з j вершинами і виділеним коренем можна побудувати два різних дерева, у яких корінь має степінь 1 і які містять (j + 1) вершину. Для цього достатньо додати дугу, що входить у корінь або виходить з кореня початкового дерева, а інший кінець цієї дуги не є вершиною початкового дерева. У термінах твірних функцій маємо: R^*(x) = 2x · R(x). Для завершення доведення достатньо скористатися твердженням теореми 4.

Теорема 14. Кількості орієнтованих кореневих дерев задовольняють таке рекурентне співвідношення:

	j
Rj + 1 = j –1	∑	k ak Rj – k + 1,
	k = 1

де

ak = 2k –1	∑	d Rd
	d | k

при довільному натуральному k.

Доведення. Справдження останньої рівності при довільному натуральному k означає рівність степеневих рядів:

+ ∞		+ ∞
∑	ak xk = 2	∑	R(xl) / l .
k = 1		l = 1

Для завершення доведення теореми потрібно скористатися попередньою теоремою 13 та теоремою 2 про експоненту твірної функції.

Перші 222 члени послідовності {R_j} опубліковано на сайті «Київські учнівські олім­піади з інформатики».

11. Перелік орієнтованих дерев

Теорема 15. Запровадимо такі позначення:

L_j — кількість різних (неізоморфних) орієнтованих дерев з виділеною дугою, що мають j вершин. Зміст цього позначення у цьому розділі відрізняється від того, що був у розділах 8 і 9;

	+ ∞
L(x) =	∑	Lj x j
	j = 1

— твірна функція орієнтованих дерев з виділеною дугою.

Маємо: L(x) = R²(x).

Доведення. Існує взаємно однозначна відповідність між орієнтованими деревами з виділеною дугою та функціями f з двоелементної множини {1, 2} у множину всіх орієнтованих дерев з виділеним коренем: орієнтоване дерево з виділеною дугою отримують об'єднанням кореневих дерев f (1) і f (2) та долученням кореневої дуги, спрямованої з кореня f (1) у корінь f (2). Тому при довільному натуральному j справджується така рівність:

	j – 1
Lj =	∑	Tk Tj – k .
	k = 1

Помноживши обидві частини останніх двох рівностей на x ^j і здійснивши додавання за всіма натуральними j, отримаємо твердження теореми.

Рис.4. Неізоморфні орієнтовані дерева, порядок яких не перевищує 3.

Теорема 16. Запровадимо такі позначення:

r_j — кількість різних (неізоморфних) орієнтованих дерев, що мають по j вершин;

	+ ∞
r(x) =	∑	rj x j = x + x2 + 3x3 + ⋯
	j = 1

— твірна функція таких орієнтованих дерев.

Тоді ряди r(x) і R(x) задовольняють таку рівність:

r(x) = R(x) – R²(x).

Доведення. Поняття симетричної дуги в орієнтованому графі відсутнє, тому у такому графі справджується рівність 1 = p – b у позначеннях теореми 11. Як і для неорієнтованих дерев, з останньої рівності маємо:

r(x) = R(x) – L(x),

де ряд L(x) перераховує орієнтовані дерева з виділеною дугою і згідно з твердженням теореми 15 дорівнює R²(x).

Перші 222 члени послідовності {r_j} опубліковано на сайті «Київські учнівські олім­піади з інформатики».

Література

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

2. Cauchy A., Memoire sur diverses proprietes remarquables des substitutions regulieres ou irregulieres, et des systemes de substitutiones conjugees // Comptes Rendus Acad. Sci. Paris 21, 835, 1845. Reprinted in Ouvres Completes d'Augustin Cauchy, Tome IX. Paris: Gauthier-Villars, 1896, pp. 342–360.

3. Frobenius F. G., Uber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul // J. reine angew. Math. 101, 1887, pp. 273-299. Reprinted in Ferdinand Georg Frobenius Gesammelte Abhandlungen, Band II. Berlin: Springer-Verlag, 1968, pp. 304–330.

4. Redfield, J. Howard. The Theory of Group-Reduced Distributions // American Journal of Mathematics, Vol. 49, No. 3 (Jul., 1927), pp. 433–455.

5. Polya G., Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen und chemische Verbindungen // Acta Mathematica, 1937, 68 (1): pp. 145–254.