Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Лекция № 9. Тема: разбиения на блоки и циклы





Тема: разбиения на блоки и циклы

Основные вопросы, рассматриваемые на лекции:

1. Разбиения множества на m блоков.

2. Число Стирлинга второго рода.

3. Разбиения перестановки на m циклов.

4. Число Стирлинга первого рода.

5. Факториальные многочлены.

Краткое содержание лекционного материала

1. Разбиения множества на m блоков. Говорят, что семейство множеств {M1,…,Mk} является разбиением множества M на k блоков M1,…,Mk, если M1,…,Mk – непустые, попарно не пересекающиеся, подмножества множества M и объединение множеств M1,…,Mk есть множества M. Число (или S(n,k)) всех разбиений n-множества M на k блоков называется числом Стирлинга второго рода.

Пример 1. Перечислим все разбиения множества {1,2,3,4} на 2 блока:

{{1}, {2, 3,4}},

{{2}, {1, 3,4}},

{{3}, {1, 2,4}},

{{4}, {1, 2,3}},

{{1,2}, {3,4}},

{{1,3}, {2,4}},

{{1,4}, {2,3}}

Мы видим, что .

Примечание. Пусть |A|=m, |B|=n. Тогда число элементов:

· множества всех отображений множества A в B равно числу всех размещений с повторениями по m из n, то есть |BA|=nm;

· множества всех инъекций множества A в B равно числу всех размещений без повторений по m из n, то есть ;

· множества всех биекций множества A на B равно числу всех размещений без повторений по m из n, то есть n!;

· множества всех сюръекций множества A на B равно произведению числа всех перестановок n-множества B на число всех разбиений n-множества B на m блоков, то есть n!.

2. Число Стирлинга второго рода. Приведем рекуррентные формулы для числа Стирлинга второго рода:

;

, где n>0;

, где n>0, 1£k£n.

Непосредственно число Стирлинга второго рода вычисляется по следующей формуле: .

k n
             
           
         
       
     
   
 

Число всех разбиений n-множества M называется числом Белла Bn.

Ясно, что .

3. Разбиения перестановки на m циклов. Перестановка p m-множества M называется циклом, если p(x1)=x2, p(x2)=x3, …, p(xm-1)=xm, p(xm)=x1, где x1, x2, x3, …, xm-1, xm – все, различные, элементы множества M. Этот цикл обозначается через (x1x2x3xm-1xm). Каждая перестановка состоит из конечного числа циклов, и эту перестановку можно записать в виде произведения циклов.



Пример 2. Перечислим все перестановки множества {1,2,3,4}, разбиваемые на 2 цикла:

(1)(234); (1)(243);

(2)(134); (2)(143);

(3)(124); (3)(142);

(4)(123); (4)(132);

(12)(34); (13)(24); (14)(23).

Числом Стирлинга первого рода (без знака) (или s(n,k)) называется число разбиений n-множества B на k циклов.

4.Число Стирлинга первого рода. Приведем рекуррентные формулы для числа Стирлинга первого рода

;

, где n>0;

, где n>0, 1£k£n.

k n
             
           
         
       
     
   
 

Ясно, что .

5. Факториальные многочлены. Любой многочлен от одной переменной можно представить как линейную сумму степеней переменной (базисных многочленов): , , , …

Определим многочлены , , которые также являются базисными: .

Связь между двумя базисными многочленами устанавливается при помощи чисел Стерлинга первого и второго родов:

, .

Вместо «убывающих степеней» можно рассматривать «возрастающие степени»: .

, .





Дата добавления: 2014-01-03; Просмотров: 268; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.003 сек.