Множество разбиений множества

Обозначим R_n - множество всех разбиений n-множества на непустые блоки, n>1. Для разбиений p,p¢ÎR_n определим частичный порядок: p£p¢ Û p - продолжение разбиения p¢, то есть каждый блок разбиения p¢ есть либо блок разбиения p, либо объединение нескольких блоков разбиения p. Отношение p¢>¾p верно Û p¢ получено с помощью объединения любых двух блоков p. Ч.у.м. R_n есть решетка, называемая решеткой разбиенийn-множества или решеткой эквиваленцийна n-множестве.

Порядок решетки R_n есть число Белла B_n. Нуль решетки R_n - разбиение на n тривиальных блоков, единица решетки - само n-множество, отсюда длина решетки l(R_n)=n-1. Атомы R_n содержат лишь один нетривиальный двухэлементный блок. Коатомы содержат ровно 2 блока.

Заметим, что = =1 при n>1 и = при n>2, где - числа Стирлинга 2-го рода. Тогда ïR₂ï=B₂=2, h(R₂)=1; ïR₃ï=B₃=5, h(R₃)=3. Если n>3, то > = при 1<k<n-1.

Различные разбиения n-множества на k блоков несравнимы, значит, ширина решетки R_n не меньше , отсюда при n>3 получаем оценки с использованием чисел Белла:

h(R_n)³ .

Отношение конгруэнтности

Систему представителей всех классов эквивалентности называют трансверсалом множества X по отношению А. Трансверсал множества по отношению эквивалентности в общем случае определен неоднозначно.

Рассмотрим алгебру A=(X,F), где X – основное множество, F={f₁,…,f_m} – система определенных на X операций арности n₁,…,n_m соответственно.

Отношение эквивалентности @ на Xназываетсяконгруэнцией на алгебре A, если оно согласовано со всеми операциями системы F, то есть если для x_i,x_i¢ÎX из отношений x_i@x_i¢, i=1,…,n_j, при любом j=1,…,m следует

f_j(x₁,…, )@f_j(x₁¢,…, ¢).

Гомоморфные образы абстрактной алгебры с точностью до изоморфизма определяются некоторыми конгруэнциями.

Теорема 3.1 [7, стр.181]. Пусть j - гомоморфизм алгебры A в алгебру B. Тогда отношение q такое, что xqx¢ Û j(x)=j(x¢), есть конгруэнция на алгебре A. w

Графы функций

Функции f:X®Y, где X и Y - конечные множества мощности n и m соответственно, поставим в соответствие ориентированный двудольный граф Г(f)=(XÈY,U), где XÈY - множествовершин, U - множество дуг, и пара (x,y)ÎU Û xÎX, y=f(x)ÎY.Граф Г(f) называют графом функции f.

Графом преобразования g п-множества X называют п-вершинный ориентированный графГ(g) с множеством вершин X и множеством дуг (x,g(x)).

Пусть S={g₁,…,g_m} - система преобразований п-множества X. Графом системы преобразований S называют п-вершинный помеченный орграф Г(S)=Г(g₁)È…ÈГ(g_m), в котором дуга (x,y) помечена максимальным подмножеством {i₁,…,i_s} множества {1,…,m} со свойством: g_j(x)=y для любого jÎ{i₁,…,i_s}. Графу Г(S) биективно соответствует п-вершинный мультиграф, в котором имеется ровно s параллельных дуг (x,y) с метками i₁,…,i_s соответственно.

При l³1 последовательность {x₁,…,x_l} элементов множества X такая, что g(x_l)=x₁и g(x_i)=x_i+1, i=1,…,l-1, образует цикл длины l в графеГ(g). Циклы имеются в графе любого преобразования конечного множества X, так как в последовательности {x,g(x),g²(x),…} совпадения элементов неизбежны при любом xÎX. Неподвижному элементу преобразования g соответствует петля в Г(g).

В общем случае граф небиективного преобразования представляет собой совокупность нескольких независимых циклов, к которым могут иметься подходы, и по крайней мере к одному из циклов подход имеется. В силу однозначности преобразования g графГ(g) содержит лишьнезависимые простые циклы, число которых r удовлетворяет неравенствам: 1£r£n; если g не подстановка, то r<n. Каждый из независимых циклов вкупе со всеми имеющимися подходами к нему образует подграф графаГ(g), являющийся его компонентой связности. Таким образом, граф Г(g) есть объединение своих компонент связности.

Из каждой ациклической вершины графа Г(g) имеется ровно один подход к одному из циклов.

ГрафГ(g) подстановки g в силу инъективности подстановки не содержит подходов и состоит из k независимых циклов, 1£k£n, иначе говоря, каждая подстановка разлагается в произведение независимых циклов единственным образом с точностью до перестановки циклов [18, т.1, гл.XI, §8]. Для вычисления g^t в степень t возводятся все циклы подстановки g.

Подстановка n-множества называется полноцикловой (п.ц.), если ее граф есть единственный цикл длины n.

Теорема 3.11. Число различных п.ц. подстановок n-множества равно (n-1)!.

t Полный цикл элементов n-множества X можно рассматривать как перестановку элементов множества, размещенную на n точках окружности. Значит, число различных полных циклов равно п!. В то же время циклы эквивалентны (реализуют одинаковые п.ц. подстановки) Û отличаются лишь параллельным сдвигом элементов по окружности. Каждый класс эквивалентности состоит из п циклов, тогда число различных п.ц. подстановок п-множества равно (п-1)!. u