Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Цикловые классы (типы).

Читайте также:
  1. Static внутренние классы
  2. Абстрактные классы
  3. Абстрактные методы и классы
  4. Внутренние классы
  5. Внутренние классы в методе и контексте
  6. Внутренние классы и структуры управления
  7. Группы поддержки, классы и мастерские
  8. Девятирунный расклад. Классы значений
  9. Зачем внутренние классы?
  10. И 2 классы относятся к безопасным условиям труда.

Определение. Будем говорить, что перестановка PÎ{1,2,…,n} имеет тип < >, если P имеет k1 циклов длины 1, имеет k2 циклов длины 2, и т. д. Заметим, что = n.

Пусть С(k1, k2,…, kn) есть число перестановок из n элементов типа k=< >.

Выясним, какова формула, определяющее общее число таких перестановок. Для того чтобы найти эту формулу выберем произвольную перестановку типа k и переставим ее элементы всеми возможными n! способами. Имеется две причины, в силу которых не все получившиеся в результате этой операции перестановки оказываются различными: (а) все циклы, в которых входят одни и те же элементы в одном и том же циклическом порядке, не отличаются друг от друга; (b) относительное расположение циклов в перестановке несущественно.

Как уже отмечалось, r-цикл может начинаться с любого из входящих в него r элементов, и, следовательно, имеется возможность (в силу a) получить r дубликатов этого цикла. Общее число дубликатов составит . Далее, если число r-циклов равно kr, то их можно переставлять kr! способами, поэтому (в силу b) окажется дубликатов k1!· k2!·…· kn!.

Следовательно,

С(k1, k2,…, kn)= , где k1 +2k2+…+nkn=n. (1)

Примеры.

1. Шесть перестановок из трех элементов распадаются на три цикловых классов следующим образом:

тип перестановки число
< > (123); (132)  
< > (12)(3); (13)(2); (1)(23)  
< > (1)(2)(3)  

2. Число перестановок типа < > равно n!/n= (n-1)!

Эта формула проверяется с помощью следующего соображения: в n-цикле первым элементом по условию является 1, а для расстановки оставшихся n-1 элементов существует (n-1)! возможностей.

3. Единственная перестановка типа < > совпадает с тождественной перестановкой.

 

Производящая функция чисел С(k1, k2,…, kn) должна иметь вид многочлена от многих переменных, так как n видов циклов должны независимыми. Этот факт выражается соотношением

Сn(t1, t2,…, tn)=ΣС(k1, k2,…, kn)

Следовательно, с учетом (1)

Сn(t1, t2,…, tn)= (2)

Сумма (2) берется по всем неотрицательным целым числам от k1 до kn таким, что k1 +2k2+…+nkn=n, или, что то же самое, по всем разбиением числа n. Функция Сn(t1, t2,…, tn) называется цикловым индикатором (указателем) симметрической группы.

Для первых значений n имеем:

С1(t1) =t1

С2(t1, t2)= +t2

С3(t1, t2, t3)= +3t1t2+2t3

С4(t1, t2, t3, t4)= +6 t2+3 +8t1t2+6t4

Удобно принять С0=1.

Из сопоставления соотношений (2) и (6) следует

Сn(t1, t2,…, tn)=An(1; t1, t2, 2! t3,…, (n-1)!tn)=

= Yn(t1, t2, 2! t3,…, (n-1)!tn) (3)

Последнее выражение является следствием соотношения (2а) при соответствующем изменении буквенных обозначений. В силу (5), это то самое, что и основное порождающее тождество:

exp(uC)= (t1, t2,…, tn)un/n!= exp(ut1+u2t2/2+u3t3/3+…) (3a)

весьма удобное для дальнейшей работы.

 

Свойства Сn(t1, t2,…, tn)

1. Сn(1, 1,…, 1)= n!

Это согласуется с (3а), так как

exp(ut1+u2t2/2+u3t3/3+…) =exp(log(1-u)-1)=(1-u)-1 =1+u+u2+…

2. (тождество Коши)

следует из 1, учитывая (2)

3.Введенная ранее производящая функция числа перестановок n-го порядка Cn(t) может быть получена из Сn(t1, t2,…, tn), если все tr приравнять t, т.е.

Сn(t)=Сn(t, t,…, t)

Следовательно, из (3а) имеем

exp(uC(t))= = exp(t(u+u2/2+u3/3+…) = exp(t·log(1-u)-1=(1-u)-t=

=1+ (4)

что согласуется с ранее полученными результатами для Сn(t).

 




Дата добавления: 2015-09-11; просмотров: 21 | Поможем написать вашу работу | Нарушение авторских прав

Конкретная математика | Производящие функции для сочетаний. | Производящие функции для перестановок. | Решение линейных рекуррентных уравнений. | Числа Стирлинга первого и второго рода. | Композиции чисел. | Принцип включения и исключения. | Число способов, которыми можно пометить граф. | Связные графы. | Эйлеровы графы |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.009 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав