Числа стирлинга второго рода формула

Числа стирлинга второго рода формула

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

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

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. Факториальные многочлены.Любой многочлен от одной переменной можно представить как линейную сумму степеней переменной (базисных многочленов): , , , …

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

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

Читайте также:  Как выполнить простую сортировку

, .

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

, .

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

Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 8958 — | 7623 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Числа Стирлинга второго рода (англ. stirling numbers of the second kind) — количество способов разбиения множества из [math]n[/math] элементов на [math]k[/math] непустых подмножеств. Числа Стирлинга II рода обозначаются как [math]S(n,k)[/math] или [math]lbrace
brace[/math] .

Содержание

Пример [ править ]

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

Следовательно, [math]lbrace<4atop 2>
brace[/math] [math] = 7[/math] .

Вычисление [ править ]

Рекуррентное соотношение [ править ]

Если задано множество из [math]n[/math] элементов, которое необходимо разбить на [math]k[/math] непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть ( [math]lbrace
brace[/math] способами), либо поместить его в некоторое подмножество ( [math]k[/math] [math]lbrace
brace[/math] способами, поскольку каждый из [math]lbrace
brace[/math] способов распределения первых [math]n-1[/math] элементов по [math]k[/math] непустым частям дает [math]k[/math] подмножеств, с которыми можно объединить последний элемент).

[math]egin n \ k end = egin kegin n-1 \ k end + egin n-1 \ k-1 end, 0lt klt n \ 0, k = 0 \ 0, n = 0 \ 0, k gt n \ 1, k = n end [/math]

Таблица значений [ править ]

nk 1 2 3 4 5 6 7 8 9
1
1 1
2 1 1
3 1 3 1
4 1 7 6 1
5 1 15 25 10 1
6 1 31 90 65 15 1
7 1 63 301 350 140 21 1
8 1 127 966 1701 1050 266 28 1
9 1 255 3025 7770 6951 2646 462 36 1

Частные случаи [ править ]

[math]lbrace
brace[/math] [math] = 0[/math]

[math]lbrace<0atop k>
brace[/math] [math]= 0[/math]

[math]lbrace
brace [/math] [math]= 1[/math]

Свойства [ править ]

  • [math]lbrace
    brace = sum_^n inom extstyle lbrace
    brace[/math]
  • [math]m![/math] [math]lbrace
    brace = sum_^n inom[/math] [math] k^n(-1)^[/math]
  • [math]left lbrack
    ight
    brack = lbrace<-natop -k>
    brace[/math] , [math]n,k in mathbb[/math] , где [math]left lbrack
    ight
    brack[/math] — число Стирлинга первого рода
  • [math]sum limits_^n lbrace
    brace = B_n[/math] , где [math]B_n[/math] — число Белла (число всех неупорядоченных разбиений n-элементного множества)
Читайте также:  Вставка нерастяжимого пробела выполняется с помощью клавиш

Применения [ править ]

  • Пусть дано множество из [math]k[/math] элементарных исходов (все исходы равновероятны). Вероятность того, что после [math]n[/math] проведенных экспериментов каждое событие произойдет хотя бы один раз, может быть найдена по следующей формуле: [math]P = [/math] [math]lbrace
    brace >[/math]
  • [math]lbrace
    brace[/math] — количество наборов из [math]k[/math] попарно непересекающихся подмножеств исходного множества [math]<1,2, dots ,n>[/math] . Например, [math]lbrace<4atop 3>
    brace[/math] [math] = 6[/math] , так как всего шесть наборов из двух непересекающихся подмножеств множества [math]<1,2,3>[/math] : [math]<(1)(23)>,<(12)(3)>, <(13)(2)>, <(1)(2)>, <(1)(3)>, <(2)(3)>[/math] .
  • Обозначим как [math]lbrace
    brace^d[/math] количество всех способов разбиений множества [math]n[/math] натуральных чисел на [math]k[/math] подмножеств, в которых расстояния между двумя любыми элементами [math]i[/math] , [math]j[/math] не меньше [math]d[/math] [math](|i-j| geqslant d)[/math] . Тогда [math]lbrace
    brace^d = lbrace
    brace,[/math] [math] n geqslant k geqslant d[/math]
  • Также числа Стирлинга II рода можно определить как коэффициенты в разложении обычных степеней на факториальные: [math]x^n = sum limits_^n extstyle lbrace
    brace x^<underline> = sum limits_^n extstyle lbrace
    brace (-1)^ x^<overline
    >[/math] , где [math]x^<underline> = xcdot (x-1)cdot ldotscdot (x-k+1)[/math] — убывающий факториал, [math]x^<overline> = xcdot (x+1)cdot ldotscdot (x+k-1)[/math] — возрастающий факториал. См. также связь между числами Стирлинга.

Переход от базиса обычных степеней к базису убывающих факториальных степеней [ править ]

Теорема:
Доказательство:
[math] riangleright[/math]
[math]x^<underline>=x^<underline>(x-k)[/math] , отсюда [math]xcdot x^<underline>=x^<underline>+kx^<underline>[/math] , следовательно, [math]xcdot x^<underline>[/math] есть

[math]xsum limits_^n extstyle lbrace
brace x^<underline

>=sum limits_^n extstyle lbrace
brace x^<underline>+sum limits_^n extstyle lbrace
brace kx^<underline
>=[/math]

[math]sum limits_^n extstyle lbrace
brace x^<underline

>+sum limits_^n extstyle lbrace
brace kx^<underline
>= [/math]

Wikimedia Foundation . 2010 .

Смотреть что такое "Число Стирлинга второго рода" в других словарях:

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

Числа Стирлинга второго рода — В комбинаторике числом Стирлинга второго рода из 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 … Википедия

Число Белла — В комбинаторике числом Белла Bn называется число всех неупорядоченных разбиений n элементного множества, при этом по определению полагают B0 = 1. Число Белла можно вычислить как сумму чисел Стирлинга второго рода: Для чисел Белла справедлива… … Википедия

Разбиение множества — Разбиение множества это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств. Разбиение множества … Википедия

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

Числа Белла — В комбинаторике числом Белла называется число всех неупорядоченных разбиений n элементного множества, при этом по определению полагают . Численные значения Значения чисел Белла для образуют последовательность: 1, 1, 2, 5, 15, 52, 203, 877, 4140,… … Википедия

Ольмеки — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей. Ольмеки название племени … Википедия

Природный газ — (Natural gas) Природный газ это один из самых распространенных энергоносителей Определение и применение газа, физические и химические свойства природного газа Содержание >>>>>>>>>>>>>>> … Энциклопедия инвестора

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