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

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

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

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

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 блока:

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

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

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

· множества всех инъекций множества 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.

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

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

Ясно, что .

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

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

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

;

, где n>0;

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

Ясно, что .

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

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

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

, .

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

, .

Не нашли то, что искали? Воспользуйтесь поиском:

Читайте также:  Прошивка телефона samsung gt s5282

Лучшие изречения: Увлечёшься девушкой-вырастут хвосты, займёшься учебой-вырастут рога 10420 — | 8030 — или читать все.

Выражение [x]n является полиномом степени n от переменной x, следовательно его можно представить в виде следующего разложения по степеням x:

По определению, коэффициенты s(n,k) такого разложения называются числами Стирлинга первого рода.

Утверждение 1.3. Числа Стирлинга первого рода удовлетворяют следующим рекуррентным соотношениям:

Доказательство. По определению

Представляя полиномы в левой и правой частях равенства в виде разложения по степеням x, получим

s(n+1,n+1)x n+1 +  + s(n+1, k)x k + +s(n+1,0)=

(s(n,n)+  +s(n, k-1)x k-1 + s(n,k)x k +  +s(n,0))(x-n).

Вычисляя и приравнивая коэффициенты при x k слева и справа, получаем первую формулу утверждения. Другие две формулы очевидны.

Утверждение 1 .3 дает эффективный способ рекуррентного вычисления чисел Стирлинга первого рода.

Приведем часть значений таблицы s(n,k) для начальных значений n и k :

Отметим связь чисел Стирлинга первого рода, в частности рекуррентного соотношения для них, с изучением циклической структуры перестановок.

Циклическая структура перестановок

Перестановки множеств и мультимножеств — один из самых богатых объектов перечислительной комбинаторики. Основная причина этого — большое разнообразие способов комбинаторного представления перестановки. Перестановку можно представлять как слово или как функцию. В частности, функция : [n]  [n], задаваемая равенством (i) = a i , соответствует слову a1a2 . an.

Если рассматривать перестановку  конечного множества S как взаимно однозначное отображение : S  S, то естественно для каждого xS рассмотреть последовательность x, (x),  2 (x), . . В конце концов (так как  — взаимно однозначное соответствие, и множество S предполагается конечным) мы вновь получим x. Таким образом, для некоторого единственного наименьшего k  1 имеем, что  k (x) = x и элементы x, (x), . ,  k-1 (x) все различны. Назовем последовательность (x, (x), . ,  k-1 (x)) циклом перестановкидлины k. Циклы (x, (x), . ,  k-1 (x)) и ( i (x),  i+1 (x), . ,  k-1 (x), x, . ,  i-1 (x)) считаются эквивалентными. Каждый элемент S встречается тогда в единственном цикле перестановки , и мы можем рассматривать  как объединение непересекающихся циклов или, по-другому, как произведение различных циклов C1, . , Cn. Например, если перестановка : [7]  [7] определена как , то есть (1) = 4, (2) = 2, (3) = 7, (4) = 1, (5) = 3, (6) = 6, (7) = 5, то  = (14)(2)(375)(6). Конечно, возможны различные обозначения такого представления перестановки; например, имеем:  = (753) (14) (6) (2). Можно определить стандартное представление:

Читайте также:  Литература на языке оригинала

в каждом цикле пишется первым его наибольший элемент;

циклы записываются в порядке возрастания их максимальных элементов.

Пусть c(n, k) — число таких перестановок множества из n элементов, которые имеют k циклов. Будем обозначать множество всех перестановок n — элементного множества символом n .

Утверждение 1.4. Числа c(n,k) удовлетворяют следующему рекуррентному сотношению:

c(n, k) = (n — 1) c(n-1, k) + c(n-1, k-1) , n, k 1,

с начальными условиями c(n, k) = 0 при n  0 или k  0, за исключением c(0, 0) = 1.

Докажем сфомулированное утверждение.

Возьмем перестановку   n-1 с k циклами. Мы можем вставить символ n после любого из символов 1, 2, . , n-1 в разложении перестановки  на непересекающиеся циклы n-1 способом, получив таким образом разложение на непересекающиеся циклы перестановки n с k циклами, где n встречается в цикле длины, не меньшей 2. Следовательно, существует (n-1)c(n-1,k) перестановок n c k циклами, для которых (n)n.

С другой стороны, если выбрана перестановка n-1 с k-1 циклом, ее можно достроить до перестановки n с k циклами, удовлетворяющей условию (n) = n. Положим

Следовательно, имеется c(n — 1, k — 1) перестановок n с k циклами, для которых (n) = n, и доказательство закончено.

Числа c(n,k) = ( — 1) n-k s(n,k) известны под названием чисел Стирлинга первого рода без знака.

Укажем на еще одну важную роль чисел c(n, k).

Пусть x — переменная. Фиксируем n  0. Тогда имеет место

Отсюда следует, что

b(n, k) = (n  1)b(n  1, k) + b(n  1, k  1).

Поэтому b(n, k) удовлетворяют тем же рекуррентным соотношениям и начальным условиям, что и c(n, k), а значит, они совпадают.

Числа Стирлинга второго рода — В комбинаторике числом Стирлинга второго рода из n по k, обозначаемым или , называется количество неупорядоченных разбиений n элементного множества на k непустых подмножеств. Содержание 1 Рекуррентная формула … Википедия

Читайте также:  Кнопка питания горит но компьютер не включается

Числа стирлинга второго рода — В комбинаторике числом Стирлинга второго рода S(n, k) называется число неупорядоченных разбиений n элементного множества на k непустых подмножеств. Числа Стирлинга второго рода задаются рекуррентным соотношением: S(n,n) = 1, для n ≥ 0, S(n,0) = 0 … Википедия

Число Стирлинга первого рода — Числа Стирлинга первого рода количество перестановок из n предметов, имеющие ровно k циклов. Содержание 1 Определение 2 Рекуррентное соотношение 3 Пример 4 Свойст … Википедия

Числа Эйлера I рода — В комбинаторике числом Эйлера I рода из n по k, обозначаемым или , называется количество перестановок порядка n с k подъёмами, то есть таких перестановок , что существует ровно k индексов j, для которых . Числа Эйлера I рода обладают также… … Википедия

Числа Стирлинга — комбинаторные понятия, введенные Джеймс‎ом Стирлингом в середине XVIII века. Числа Стирлинга первого рода Числа Стирлинга второго рода Литература Белешко Д. Комбинаторика (часть 2). СПбГУ ИТМО. Иванов Б. Н. Дискретная математика. М.:ЛБЗ, 2001.… … Википедия

Число Стирлинга второго рода — В комбинаторике числом Стирлинга второго рода S(n, k) называется число неупорядоченных разбиений n элементного множества на k непустых подмножеств. Числа Стирлинга второго рода задаются рекуррентным соотношением: S(n,n) = 1, для n ≥ 0, S(n,0) = 0 … Википедия

Полиномы Белла — В математике, в частности в комбинаторике, полиномы Белла это полиномы вида где сумма берётся по всем последовательностям j1, j2, j3, . jn−k+1 неотрицательных целых чисел таким, что и … Википедия

Парадокс дней рождения — Парадокс дней рождения это кажущееся парадоксальным утверждение, что вероятность совпадения дней рождения (числа и месяца) хотя бы у двух членов группы из 23 и более человек, превышает 50 %. С практической точки зрения это означает,… … Википедия

Жидкостный ракетный двигатель — (ЖРД) химический ракетный двигатель, использующий в качестве ракетного топлива жидкости, в том числе сжиженные газы. По количеству используемых компонентов различаются одно , двух и трёхкомпонентные ЖРД. Содержание 1 История … Википедия

Ссылка на основную публикацию
Adblock detector