3. Решение системы уравнений с перестановками

Пусть M - множество T - множество Для каждого i из есть некоторое подмножество (быть может пустое) множества M. Для различных возможно равество Через обозначается симметрическая группа перестановок множества M. Через обозначается множество всех перестановок удовлетворяющих системе:

При этом считаем, что для каждой из

Для описания множества решений системы (3.1) нам понадобятся следующие определения:

О п р е д е л е н и е 5. Собственным множеством системы  назовем любое непустое множество вида:

где J есть любое непустое подмножество множества T.

Будем считать также собственным множеством системы  множество

если оно не пусто.

О п р е д е л е н и е 6. Перестановку , действующую на M, будем называть собственной перестановкой системы  если существует собственное множество L системы  такое, что выполняется условие:

если

Пусть - множество всех собственных множеств системы (3.1), для Ясно, что , если

Тогда справедливы следующие предложения.

1. Если и то

Действительно, если одно из множеств равно то другое лежит в Если получены как пересечения на различных множеств , то Предложение доказано.

2. где I  - множество индексов всевозможных собственных множеств системы (3.1). Следовательно, есть разбиение множества M.

3. Для каждого непустого множества существует множество J из I такое, что

Из предложений 1 - 3 легко следует.

Предложение 12. Перестановка , действующая на T, есть решение системы  тогда и только тогда, когда она представима в виде произведения собственных перестановок системы 

Предложение 13. Система  эквивалентна системе:

где - собственное множество системы  I  - множество индексов всевозможных собственных множеств системы 

Д о к а з а т е л ь с т в о. Пусть Тогда из определения 5 следует,что есть решение системы ( 3.2). Если же есть решение системы ( 3.2), то в силу утверждения 3, является решением системы ( 3.1). Предложение 13. доказано.

О п р е д е л е н и е 7. Систему вида  будем называть канонической системой системы 

Ясно,что для любой системы вида (3.1 ) существует каноническая система и две системы вида (3.1) тогда и только тогда эквивалентны (т.е. множества решений их равны), когда их канонические системы совпадают.

обозначает прямое произведение групп

Теорема 1. Пусть - множество всех перестановок, удовлетворяющих системе  тогда

1. множество - группа ;

2. где  - симметрическая группа перестановок на множестве  - множество всех собственных множеств системы .

Заметим, что множество есть множество всех орбит на M группы С этой точки зрения определение дает алгоритм нахождения всех орбит группы c помощью теоретико - множественных операций над множествами Ясно, что где  - симметрическая группа перестановок степени