101
правка
Изменения
Я взял на себя смелость поправить форматирование этой статьи дабы она была похожа на статью о числах I рода
'''Числа Стирлинга второго рода''' (''Stirling numbers of the second kind'') — количество способов разбиения множества из <tex>n</tex> элементов на <tex>k</tex> непустых подмножеств. Числа Стирлинга II рода обозначаются как <tex dpi="130">S(n,k)</tex> или <tex dpi = "180">\lbrace{n\atop k}\rbrace</tex>.
== Определение Пример ==Существует семь способов разбиения четырехэлементного множества на две части:
<tex>\{1,23,3\}\{4\}</tex> <tex>\{1,2,4\}\{3\}</tex> <tex>qquad \{1,3,4\}\{2,3\}</tex>
<tex>\{2,3,4\}\{1\}</tex>
== Рекуррентная формула Вычисление ===== Рекуррентное соотношение ===
Если задано множество из ''<tex>n'' </tex> элементов, которое необходимо разбить на ''<tex>k'' </tex> непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть(<tex dpi = "180">\lbrace{n-1\atop k-1}\rbrace</tex> способами), либо поместить его в некоторое подмножество (<tex>k</tex><tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способами, поскольку каждый из <tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способов распределения первых ''<tex>n-1'' </tex> элементов по ''<tex>k'' </tex> непустым частям дает ''<tex>k'' </tex> подмножеств, с которыми можно объединить последний элемент).
<tex>\begin{Bmatrix}
Чтобы доказать равносильность двух определений используем метод математической индукции.
<!-- КРОВЬКИШКИТЕХ -->
<tex dpi = "150">x^{k} = x\sum_{i=0}^{k-1} \textstyle \lbrace{k-1\atop i}\rbrace x^{\underline{i}} = \sum_{i=0}^{k-1} \textstyle \lbrace{k-1\atop i}\rbrace x^{\underline{i}}(x-i+i) = \sum_{i=0}^{k-1} \textstyle \lbrace{k-1\atop i}\rbrace (x^{\underline{i+1}}+ix^{\underline{i}}) = \sum_{i=0}^k \textstyle \lbrace{k-1\atop i-1}\rbrace x^{\underline{i}}+\sum_{i=0}^k \textstyle \lbrace{k-1\atop i}\rbrace ix^{\underline{i}} = \sum_{i=0}^k (\textstyle \lbrace{k-1\atop i-1}\rbrace + i\textstyle \lbrace{k-1\atop i}\rbrace)x^{\underline{i}} = \sum_{i=0}^k \textstyle \lbrace{k\atop i}\rbrace x^{\underline{i}}</tex>
=== Таблица значений ==={| styleclass="wikitable" !width:400px; height:200px" border="120" !| n\k ! width="40"| 0 !width="40"| 1 !width="40"| 2 !width="40"| 3 !width="40"| 4 !width="40"| 5 !width="40"| 6 !width="40"| 7 !width="40"| 8 !width="40"| 9
|-
!0
|}
=== Частные случаи ===
<tex dpi = "180">\lbrace{n\atop 0}\rbrace</tex> <tex dpi = "150"> = 0</tex>
== Применения ==
*пусть Пусть дано множество из ''<tex>k'' </tex> [[Вероятностное пространство, элементарный исход, событие|элементарных исходов]] (все исходы равновероятны). Вероятность того, что после ''<tex>n'' </tex> проведенных экспериментов каждое событие произойдет хотя бы один раз, может быть найдена по следующей формуле:<tex dpi = "150">P = </tex><tex dpi = "180">\lbrace{n\atop k}\rbrace {k! \over{k^n}}</tex>
* <tex dpi = "150180">P = \lbrace{n+1\atop k+1}\rbrace</tex> — количество наборов из <tex>k</tex> попарно непересекающихся подмножеств исходного множества <tex>\{1,2...n\}</tex>. Например, <tex dpi = "180">\lbrace{n4\atop k3}\rbrace </tex><tex dpi = "130"> = 6</tex>, так как всего шесть наборов из двух непересекающихся подмножеств множества <tex>\{k! 1,2,3\}</tex>: <tex>\{(1)(23)\},\{(12)(3)\}, \{(13)(2)\}, \{(1)(2)\}, \over{k^n(1)(3)\}, \{(2)(3)\}</tex>.
*Обозначим как <tex dpi = "180">\lbrace{n+1\atop k+1}\rbrace^d</tex> — количество наборов из ''k'' попарно непересекающихся подмножеств исходного всех способов разбиений множества <tex>\{1,2...n\}</tex>. Напримернатуральных чисел на <tex>k</tex> подмножеств, в которых расстояния между двумя любыми элементами <tex dpi = "180">\lbrace{4\atop 3}\rbracei</tex>, <tex dpi = "130"> = 6j</tex>, так как всего шесть наборов из двух непересекающихся подмножеств множества не меньше <tex>\{1,2,3\}d</tex>: <tex>(|i-j| \{(1)(23geq d)</tex>. Тогда <tex dpi = "180">\},\lbrace{(12)(3)n\atop k}, \{(13)(2)\}, rbrace^d = \lbrace{(n-d+1)(2)\atop k-d+1}, \{(1)(3)\}rbrace, </tex><tex dpi = "150"> n \{(2)(3)geq k \}geq d</tex>
*обозначим Также числа Стирлинга II рода можно определить как коэффициенты в разложении обычных степеней на факториальные: <tex dpi = "180150">x^n = \sum_{k=0}^n \textstyle \lbrace{n\atop k}\rbracex^d</tex> количество всех способов разбиений множества ''{\underline{k}} = \sum_{k=0}^n \textstyle \lbrace{n'' натуральных чисел на ''\atop k'' подмножеств, в которых расстояния между двумя любыми элементами ''i'', ''j'' не меньше ''d'' <tex>}\rbrace (|i-j| 1)^{n-k} x^{\geq d)overline{k}}</tex>. Тогда , где <tex dpi = "180150">x^{\lbraceunderline{n\atop k}\rbrace^d } = x\lbrace{ncdot (x-d+1)\atop cdot \ldots\cdot (x-k-d+1}\rbrace,)</tex>— убывающий факториал, <tex dpi = "150"> n x^{\geq overline{k }} = x\cdot (x+1)\cdot \ldots\geq dcdot (x+k-1)</tex>— возрастающий факториал. См. также [[Числа Стирлинга первого рода#Связь между числами Стирлинга | связь между числами Стирлинга]].
== Источники ==
*[http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Wikipedia {{---}} Stirling numbers of the second kind] *[http://oeis.org/A008277 OEIS] *Р. Грэхем, Д. Кнут, О. Паташник Конкретная математика. Основание информатики.—М.:Мир, 1998.—с. 288.— ISBN 5-03-001793-3
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
