Изменения

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

'''Числа Стирлинга второго рода''' (''Stirling numbers of the second kind'') <tex dpi = "180">\lbrace{n1,2,3\atop k}\rbrace{4\} \qquad \{1,2\}\{3,4\}</tex> — количество способов разбиения множества из ''n'' элементов на ''k'' непустых подмножеств.

Например<tex>\{1, существует семь способов разбиения четырехэлементного множества на две части:2,4\}\{3\} \qquad \{1,3\}\{2,4\}</tex>

<tex>\{1,23,3\}\{4\}</tex> <tex>\{1,2,4\}\{3\}</tex> <tex>qquad \{1,3,4\}\{2,3\}</tex>

Следовательно, <texdpi = "180">\lbrace{1,4\atop 2\}\{3,4\}rbrace</tex><tex> = 7</tex>.

Если задано множество из <tex>\{1,4\}\{2,3\}n</tex> Следовательноэлементов, <tex dpi = "180">\lbrace{4\atop 2}\rbrace</tex><tex> = 7</tex> Также числа Стирлинга 2-го рода можно определить как коэффициенты в разложении обычных степеней которое необходимо разбить на факториальные: <tex dpi = "150">x^n = \sum_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace x^{\underline{k}} = \sum_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace (-1)^{n-k} x^{\overline{k}}</tex>, где <tex dpi = "150">x^{\underline{k}} = x\cdot (x-1)\cdot \ldots\cdot (x-k+1)</tex> — убывающий факториал, <tex dpi = "150">x^{\overline{k}} = x\cdot (x+1)\cdot \ldots\cdot (x+k-1)</tex> — возрастающий факториал. == Рекуррентная формула == Если задано множество из ''n'' элементов, которое необходимо разбить на ''k'' непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть(<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>x^0=x^{\underline{0}} = 1</tex># предположим, что утверждение верно для некоторого <tex>k-1</tex>: <tex dpi = "150">x^{k-1} = \sum_{i=0}^{k-1} \textstyle \lbrace{k-1\atop i}\rbrace x^{\underline{i}}</tex># докажем верность для <tex>k</tex>: -->

*предположим, что утверждение верно для некоторого ''<!-- КРОВЬКИШКИТЕХ <tex dpi = "150">x^{k} = x\sum_{i=0}^{k-1} \lbrace{k-1\atop i}\rbrace x^{\underline{i}} = \sum_{i=0}^{k-1} \lbrace{k-1\atop i}\rbrace x^{\underline{i}}(x-i+i) = \sum_{i=0}^{k-1'':} \lbrace{k-1\atop i}\rbrace (x^{\underline{i+1}}+ix^{\underline{i}}) = \sum_{i=0}^k \lbrace{k-1\atop i-1}\rbrace x^{\underline{i}}+\sum_{i=0}^k \lbrace{k-1\atop i}\rbrace ix^{\underline{i}} = \sum_{i=0}^k (\lbrace{k-1\atop i-1}\rbrace + i \lbrace{k-1\atop i}\rbrace)x^{\underline{i}} = \sum_{i=0}^k \lbrace{k\atop i}\rbrace x^{\underline{i}}</tex> -->

<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>=Таблица значений = Начальные значения чисел Стирлинга второго рода == {| 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 |0 |0 |0 |0 |0 |0 |0 |0

|0 |0 |0 |0 |0 |0 |0 |0

|0 |0 |0 |0 |0 |0 |0

|0 |0 |0 |0 |0 |0

|0 |0 |0 |0 |0

|0 |0 |0 |0

|0 |0 |0

|0 |0

|0

=== Частные случаи ===

<tex dpi = "180">\lbrace{n\atop 0}\rbrace </tex> <tex dpi = "150"> = 0</tex>

<tex dpi = "180">\lbrace{0\atop k}\rbrace </tex> <tex dpi = "150">= 0</tex>

<tex dpi = "180">\lbrace{n\atop n}\rbrace </tex><tex>= 1</tex>

*<tex dpi = "180150"> m!</tex><tex dpi = "180">\lbrace{n\atop m}\rbrace = \sum_{k=0}^n \binom{m}{k} </tex><tex dpi = "150"> k^n(-1)^{m-k}</tex>

*<tex dpi = "180">\left \lbrack{n\atop k} \right \rbrack = \lbrace{-n\atop -k}\rbrace</tex>, <tex dpi = "150">n,k \in \mathbb{Z}</tex>, где <tex dpi = "150180">\left \lbrack{n\atop k} \right \rbrack</tex> — [[Числа Стирлинга первого рода|число Стирлинга первого рода]]

*<tex dpi = "180">\sum_sum \limits_{k=0}^n \lbrace{n\atop k}\rbrace = B_n</tex>, где <tex dpi = "150180">B_n</tex> — число Белла (число всех неупорядоченных разбиений ''n''-элементного множества)

*пусть Пусть дано множество из ''<tex>k'' </tex> [[Вероятностное пространство, элементарный исход, событие|элементарных исходов]] (все исходы равновероятны). Вероятность того, что после ''<tex>n'' </tex> проведенных экспериментов каждое событие произойдет хотя бы один раз, может быть найдена по следующей формуле: <tex dpi = "160150">P = </tex><tex dpi = "180">\lbrace{n\atop k}\rbrace {k! \over{k^n}}</tex>

*<tex dpi = "160180">\lbrace{n+1\atop k+1}\rbrace</tex> — количество наборов из ''<tex>k'' </tex> попарно непересекающихся подмножеств исходного множества <tex>\{1,2..., \dots ,n\}</tex>. Например, <texdpi = "180">\lbrace{4\atop 3}\rbrace </tex><tex dpi = "130"> = 6</tex>, так как всего шесть наборов из двух непересекающихся подмножеств множества <tex>\{1,2,3\}</tex>: <tex>\{(1)(23)\},\{(12)(3)\}, \{(13)(2)\}, \{(1)(2)\}, \{(1)(3)\}, \{(2)(3)\}</tex> .

*обозначим Обозначим как <tex dpi = "160180">\lbrace{n\atop k}\rbrace^d</tex> количество всех способов разбиений множества ''<tex>n'' </tex> натуральных чисел на ''<tex>k'' </tex> подмножеств, в которых расстояния между двумя любыми элементами ''<tex>i''</tex>, ''<tex>j'' </tex> не меньше ''<tex>d'' </tex> <tex>(|i-j| \geq geqslant d)</tex>. Тогда<tex dpi = "180">\lbrace{n\atop k}\rbrace^d = \lbrace{n-d+1\atop k-d+1}\rbrace,</tex><tex dpi = "150"> n \geqslant k \geqslant d</tex>

* Также числа Стирлинга II рода можно определить как коэффициенты в разложении обычных степеней на факториальные: <tex dpi = "160150">x^n = \sum \limits_{k=0}^n \textstyle \lbrace{n\atop k}\rbracex^d {\underline{k}} = \sum \limits_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace (-d+1)^{n-k} x^{\atop overline{k}}</tex>, где <tex dpi = "150">x^{\underline{k}} = x\cdot (x-d1)\cdot \ldots\cdot (x-k+1)</tex> — убывающий факториал, <tex dpi = "150">x^{\overline{k}} = x\cdot (x+1)\rbrace, n cdot \ldots\geq cdot (x+k \geq d-1)</tex>— возрастающий факториал. См. также [[Числа Стирлинга первого рода#Связь между числами Стирлинга | связь между числами Стирлинга]].

== Источники Переход от базиса обычных степеней к базису убывающих факториальных степеней ==*[http:{{Теорема|statement=Числа Стирлинга II рода образуют матрицу переходов в линейном пространстве полиномов от базиса обычных степеней к базису убывающих факториальных степеней.|proof=<tex dpi = "150">x^{\underline{k+1}}=x^{\underline{k}}(x-k)</tex>, отсюда <tex dpi = "150">x\cdot x^{\underline{k}}=x^{\underline{k+1}}+kx^{\underline{k}}</http:tex>, следовательно, <tex dpi = "150">x\cdot x^{\underline{n-1}}</tex> есть <br> <br> <tex dpi = "150">x\sum \limits_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace x^{\underline{k}}=\sum \limits_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace x^{\underline{k+1}}+\sum \limits_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace kx^{\underline{k}}=</en.wikipedia.orgtex> <br> <br> <tex dpi = "150">\sum \limits_{k=0}^n \textstyle \lbrace{n-1\atop k-1}\rbrace x^{\underline{k}}+\sum \limits_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace kx^{\underline{k}}= </wiki/Stirling_numbers_of_the_second_kind Wikipedia tex> <br> <br> <tex dpi = "150">\sum \limits_{k=0}^n \textstyle (k\lbrace{n-1\atop k}\rbrace + \lbrace{n-1\atop k-1}\rbrace )x^{\underline{k}}=\sum \limits_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace x^{\underline{k}} </tex>}} Stirling numbers of the second kind]

== См. также ==* [[Числа Стирлинга первого рода]]*[http://http://oeis.org/A008277 OEIS[Числа Эйлера I и II рода]]

== Источники информации==* [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

 [[Категория: Комбинаторика ]]