Изменения

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

* <tex dpi = "180">\lbrace{n+1\atop k+1}\rbrace</tex> — количество наборов из <tex>k</tex> попарно непересекающихся подмножеств исходного множества <tex>\{1,2..., \dots ,n\}</tex>. Например, <tex dpi = "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 = "180">\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| \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 = "150">x^n = \sum \limits_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace x^{\underline{k}} = \sum \limits_{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> — возрастающий факториал. См. также [[Числа Стирлинга первого рода#Связь между числами Стирлинга | связь между числами Стирлинга]].

* Обозначим как == Переход от базиса обычных степеней к базису убывающих факториальных степеней =={{Теорема|statement=Числа Стирлинга II рода образуют матрицу переходов в линейном пространстве полиномов от базиса обычных степеней к базису убывающих факториальных степеней.|proof=<tex dpi = "180150">x^{\lbraceunderline{k+1}}=x^{n\atop underline{k}\rbrace^d}(x-k)</tex> количество всех способов разбиений множества <tex>n</tex> натуральных чисел на , отсюда <texdpi = "150">x\cdot x^{\underline{k}}=x^{\underline{k+1}}+kx^{\underline{k}}</tex> подмножеств, в которых расстояния между двумя любыми элементами следовательно, <texdpi = "150">ix\cdot x^{\underline{n-1}}</tex>, есть <texbr>j</texbr> не меньше <texdpi = "150">dx\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}}=</tex> <texbr>(|i-j| \geq d)</texbr>. Тогда <tex dpi = "180150">\sum \limits_{k=0}^n \textstyle \lbrace{n-1\atop k-1}\rbracex^d {\underline{k}}+\sum \limits_{k= 0}^n \textstyle \lbrace{n-d+1\atop k-d+1}\rbrace,kx^{\underline{k}}= </tex> <br> <br><tex dpi = "150"> \sum \limits_{k=0}^n \textstyle (k\lbrace{n -1\geq atop k }\rbrace + \lbrace{n-1\geq datop k-1}\rbrace )x^{\underline{k}}=\sum \limits_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace x^{\underline{k}} </tex>}}

* Также числа Стирлинга II рода можно определить как коэффициенты в разложении обычных степеней на факториальные: <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> — возрастающий факториал. См. также ==* [[Числа Стирлинга первого рода#Связь между числами Стирлинга | связь между числами Стирлинга]]. * [[Числа Эйлера I и II рода]]

== Источники информации==