Читать курсовая по математике: "Решения комбинаторных задач теории графов с помощью теоремы Пойа" Страница 5


назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

3s1s2. Наконец, подстановки (123) и (132) вносят 2s3. Таким образом, имеем Z(S3) = (1/3!)(s13 + 3s1s2 + 2s3). Для вычисления циклового индекса симметрической группы Sn введем понятие разбиения числа и рассмотрим несколько утверждений. [2] Назовем разбиением натурального числа n его представление в виде суммы некоторых натуральных чисел. Заметим, что каждая подстановка a на n объектах может быть связана с определенным разбиением числа n, имеющим для каждого k = 1, 2, …, n точно jk(a) частей, равных числу k. Будем задавать разбиение числа n посредством вектора

(j) = (j1, j2, …, jn),

где jk - число частей разбиения, равных k. Итак,

Пример

4 = 1 + 1 + 1 + 1

(4, 0, 0, 0)

4 = 1 + 1 + 2

(2, 1, 0, 0)

4 = 2 + 2

(0, 2, 0, 0)

4 = 1 + 3

(1, 0, 1, 0)

4 = 4

(0, 0, 0, 1)

Глава 2. Лемма Бернсайда о числе классов эквивалентности .1 Определение эквивалентности, порождаемой группой подстановок Определение: Если множество А={1,2,…,n} постоянно, то взаимнооднозначное отображение р:А→А называется подстановкой, которая обозначается: где ik = p(k). Произведение двух подстановок есть их последовательное исполнение.

Множество подобных подстановок, определенных на множестве А с операциями умножения подстановок и взятия обратной подстановки образуют симметрическую группу Sn с единицей: которая есть тождественная подстановка. Заметим, что симметричная группа Sn не коммутативна и содержит n! элементов.

Пусть Sn есть симметрическая группа подстановок, определенных на множестве Х={1,2,…,n}.

Утверждение: Всякая конечная группа порядка n(число элементов в группе) изоморфна некоторой подгруппе симметрической группы Sn.

Пусть G=(p0=e,p1,…,pr} есть некая группа подстановок, определенная на множестве X={1,2,…,n} с единицей p0=e (тождественной подстановкой).

Введём отношение X~Y на Х так, чтобы X~Y ⇔ ∃p∈G (p(x)=y)

X~Y есть отношение эквивалентности, то есть он удовлетворяет трем аксиомам:

. X~X

. X~Y ⇒ Y~X

. X~Y и Y~Z ⇒ X~Z

Замечание: Отношение X~Y индуцирует разбиение множества Х на попарно непересекающиеся классы эквивалентных между собой элементов.

Определение: Класс эквивалентности в множестве Х по отношению к соотношениям X~Y называется орбитой группы подстановок G. Длина орбиты есть число её элементов.

Замечание: Для ∀а∈Х множество А(а)={р0(a)=a, р1(a),…,рn-1(a)} перечисляет все элементы, эквивалентные а, и потому множество А(а) есть орбита группы G.

Замечание: Орбита О замкнута относительно ∀ функции р(х)∈G, то есть ∀a∈O ∀P∈G р(a)∈O.

Утверждение: ∀O={i1,…,iu} группа подстановок G для ∀ элемента с∈О орбита О=А(с)={р0(с)=с, р1(с),…,рn-1(с)}

Следствие: Все орбиты группы подстановок G исчерпываются орбитами вида А(а).

Замечание: Множество Х={1,2,…,n} распадается в сумму попарно непересекающихся между собой орбит группы G.[1] .2 Лемма Бернсайда Уильям Бернсайд сформулировал и доказал эту лемму (без указания авторства) в одной из своих книг (1897 год), но историки математики обнаружили, что он не был первым, кто открыл её. Коши в 1845 году и Фробениусу в 1887 году также была известна эта формула. По-видимому, лемма была столь хорошо известна, что Бернсайд просто опустил указание авторства Коши. Поэтому эта лемма иногда называется леммой не Бернсайда. Это название не столь туманно, как кажется:



Интересная статья: Быстрое написание курсовой работы