234
правки
Изменения
Нет описания правки
== Определение == '''Числа Стирлинга второго рода''' (''Stirling numbers of the second kind'') <mathtex dpi = "180">\beginlbrace{Bmatrix}n\\atop k}\end{Bmatrix}rbrace</mathtex> — количество способов разбиения множества из ''n'' элементов на ''k'' непустых подмножеств.
Например, существует семь способов разбиения четырехэлементного множества на две части:
<mathtex>\{1,2,3\}\{4\}</mathtex> <tex>\{1,2,4\}\{3\}</tex> <tex>\{1,3,4\}\{2\}</tex>
<mathtex>\{12,23,4\}\{31\}</mathtex>
<mathtex>\{1,3,42\}\{23,4\}</mathtex>
<mathtex>\{21,3,4\}\{12,4\}</mathtex>
<mathtex>\{1,24\}\{2,3,4\}</mathtex>
Следовательно, <mathtex dpi = "180">\lbrace{1,34\atop 2}\{2,4\}rbrace</tex><tex> = 7</mathtex>
== Рекуррентная формула ==
Если задано множество из '''n''' элементов, которое необходимо разбить на '''k''' непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть(<mathtex dpi = "180">\beginlbrace{Bmatrix}n-1 \\atop k-1}\end{Bmatrix}rbrace</mathtex> способами), либо поместить его в некоторое подмножество (<mathtex>k</tex><tex dpi = "180">\beginlbrace{Bmatrix}n-1 \\atop k}\end{Bmatrix}rbrace</mathtex> способами, поскольку каждый из <mathtex dpi = "180">\beginlbrace{Bmatrix}n-1 \\atop k}\end{Bmatrix}rbrace</mathtex> способов распределения первых '''n-1''' элементов по '''k''' непустым частям дает '''k''' подмножеств, с которыми можно объединить последний элемент)
<mathtex>\begin{Bmatrix}
n \\
k
1, k = n
\end{cases}
</mathtex> Чтобы доказать равносильность двух определений используем метод математической индукции.*<tex>x^0=x^{\underline{0}} = 1</tex> *предположим, что утверждение верно для некоторого ''k-1'': <tex dpi = "150">x^{k-1} = \sum_{i=0}^{k-1} \textstyle \lbrace{k-1\atop i}\rbrace x^{\underline{i}}</tex> *докажем верность для ''k'':
<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>
== Начальные значения чисел Стирлинга второго рода ==
|1
|}
== Частные случаи ==
<tex dpi = "180">\lbrace{n\atop 0}\rbrace = 0</tex>
<tex dpi = "180">\lbrace{0\atop k}\rbrace = 0</tex>
<tex dpi = "180">\lbrace{n\atop n}\rbrace = 1</tex>
<tex dpi = "180">\lbrace{n\atop n-1}\rbrace = \binom{n}{2}</tex>
<tex dpi = "180">
\lbrace{n\atop 2}\rbrace = \frac{ \frac11 (2^{n-1}-1^{n-1}) }{0!} \\[8pt]
\lbrace{n\atop 3}\rbrace = \frac{ \frac11 (3^{n-1}-2^{n-1})- \frac12 (3^{n-1}-1^{n-1}) }{1!} \\[8pt]
\lbrace{n\atop 4}\rbrace = \frac{ \frac11 (4^{n-1}-3^{n-1})- \frac22 (4^{n-1}-2^{n-1}) + \frac13 (4^{n-1}-1^{n-1})}{2!} \\[8pt]
\lbrace{n\atop 5}\rbrace = \frac{ \frac11 (5^{n-1}-4^{n-1})- \frac32 (5^{n-1}-3^{n-1}) + \frac33 (5^{n-1}-2^{n-1}) - \frac14 (5^{n-1}-1^{n-1}) }{3!} \\[8pt]
{}\ \ \vdots
</tex>
== Свойства ==
* <mathtex dpi = "180">x^\lbrace{n +1\atop m+1}\rbrace = \sum_{k=0}^n \binom{n}{k} \textstyle \lbrace{k\atop m}\rbrace</tex>*<tex dpi = "180"> m!\lbrace{n\atop m}\rbrace = \sum_{k=0}^n \rbrace xbinom{m}{k} k^n(-1)^{m-k}</tex> *<tex dpi = "180">\left \lbrack{n\atop k} \right \rbrack = \underlinelbrace{-n\atop -k}\rbrace</tex>, <tex dpi = "150">n,k\in \mathbb{Z}</tex>, где <tex dpi = "150">\left \lbrack{n\atop k} \right \rbrack</tex> — [[Числа Стирлинга первого рода|число Стирлинга первого рода]] *<tex dpi = "180">\sum_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace = B_n</tex>, где <tex dpi = "150">B_n</tex> — число Белла (число всех неупорядоченных разбиений ''n''-1элементного множества) == Применения ==*пусть дано множество из ''k'' [[Вероятностное пространство, элементарный исход, событие|элементарных исходов]] (все исходы равновероятны)^. Вероятность того, что после ''n'' проведенных экспериментов каждое событие произойдет хотя бы один раз, может быть найдена по следующей формуле: <tex dpi = "160">P = \lbrace{n-\atop k} x^\rbrace {k! \overlineover{k^n}}</mathtex>, где *<mathtex dpi = "160">x^\lbrace{n+1\atop k+1}\rbrace</tex> — количество наборов из ''k'' попарно непересекающихся подмножеств исходного множества <tex>\underline{k1,2...n\}</tex>. Например, <tex>\lbrace{4\atop 3} \rbrace = x6</tex>, так как всего шесть наборов из двух непересекающихся подмножеств множества <tex>\{1,2,3\cdot }</tex>: <tex>\{(x-1)(23)\},\{(12)(3)\}, \{(13)(2)\}, \cdot {(1)(2)\ldots}, \cdot {(x-k+1)(3)\}, \{(2)(3)\}</mathtex> — убывающий факториал, *обозначим как <mathtex dpi = "160">x^\lbrace{n\overline{atop k}} = x\cdot rbrace^d</tex> количество всех способов разбиений множества ''n'' натуральных чисел на ''k'' подмножеств, в которых расстояния между двумя любыми элементами ''i'', ''j'' не меньше ''d'' <tex>(x+1|i-j| \geq d)</tex>. Тогда <tex dpi = "160">\cdot lbrace{n\atop k}\ldotsrbrace^d = \cdot (xlbrace{n-d+1\atop k-d+1)}\rbrace, n \geq k \geq d</mathtex> — возрастающий факториал == Источники ==*[http://http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Wikipedia {{---}} Stirling numbers of the second kind] *[http://http://oeis.org/A008277 OEIS]
*<math> \textstyle \lbrace{n+1\atop m+1}\rbrace = \sum_{k=0}^n \binom{n}{k} \textstyle \lbrace{k\atop m}\rbrace</math>Р. Грэхем, Д. Кнут, О. Паташник Конкретная математика. Основание информатики.—М.:Мир, 1998.—с. 288.— ISBN 5-03-001793-3
