Числа Стирлинга второго рода — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 211: Строка 211:
 
* <tex dpi = "180">\lbrace{n+1\atop k+1}\rbrace</tex> — количество наборов из <tex>k</tex> попарно непересекающихся подмножеств исходного множества <tex>\{1,2...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+1\atop k+1}\rbrace</tex> — количество наборов из <tex>k</tex> попарно непересекающихся подмножеств исходного множества <tex>\{1,2...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| \geq 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 \geq k \geq d</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_{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> — возрастающий факториал. См. также [[Числа Стирлинга первого рода#Связь между числами Стирлинга | связь между числами Стирлинга]].  
 
* Также числа Стирлинга 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> — возрастающий факториал. См. также [[Числа Стирлинга первого рода#Связь между числами Стирлинга | связь между числами Стирлинга]].  
Строка 220: Строка 220:
 
Числа Стирлинга II рода образуют матрицу переходов в линейном пространстве полиномов от базиса обычных степеней к базису убывающих факториальных степеней.
 
Числа Стирлинга II рода образуют матрицу переходов в линейном пространстве полиномов от базиса обычных степеней к базису убывающих факториальных степеней.
 
|proof=
 
|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}}</tex>, следовательно, <tex dpi = "150">x\cdot x^{\underline{n-1}}</tex> есть <br> <tex dpi = "150">x\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace x^{\underline{k}}=\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace x^{\underline{k+1}}+\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace kx^{\underline{k}}=</tex> <br> <tex dpi = "150">\sum_{k=0}^n \textstyle \lbrace{n-1\atop k-1}\rbrace x^{\underline{k}}+\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace kx^{\underline{k}}= </tex> <tex dpi = "150">\sum_{k=0}^n \textstyle (k\lbrace{n-1\atop k}\rbrace + \lbrace{n-1\atop k-1}\rbrace )x^{\underline{k}}=\sum_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace x^{\underline{k}} </tex>
+
<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}}</tex>, следовательно, <tex dpi = "150">x\cdot x^{\underline{n-1}}</tex> есть <br> <br> <tex dpi = "150">x\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace x^{\underline{k}}=\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace x^{\underline{k+1}}+\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace kx^{\underline{k}}=</tex> <br> <br> <tex dpi = "150">\sum_{k=0}^n \textstyle \lbrace{n-1\atop k-1}\rbrace x^{\underline{k}}+\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace kx^{\underline{k}}= </tex> <br> <br> <tex dpi = "150">\sum_{k=0}^n \textstyle (k\lbrace{n-1\atop k}\rbrace + \lbrace{n-1\atop k-1}\rbrace )x^{\underline{k}}=\sum_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace x^{\underline{k}} </tex>
 
}}
 
}}
 +
 +
== См. также ==
 +
[http://neerc.ifmo.ru/wiki/index.php?title=%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%AD%D0%B9%D0%BB%D0%B5%D1%80%D0%B0_I_%D0%B8_II_%D1%80%D0%BE%D0%B4%D0%B0 Числа Эйлера]
  
 
== Источники информации==
 
== Источники информации==

Версия 20:53, 15 января 2015

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

Пример

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

[math]\{1,2,3\}\{4\} \qquad \{1,2\}\{3,4\}[/math]

[math]\{1,2,4\}\{3\} \qquad \{1,3\}\{2,4\}[/math]

[math]\{1,3,4\}\{2\} \qquad \{1,4\}\{2,3\}[/math]

[math]\{2,3,4\}\{1\}[/math]

Следовательно, [math]\lbrace{4\atop 2}\rbrace[/math][math] = 7[/math].

Вычисление

Рекуррентное соотношение

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

[math]\begin{Bmatrix} n \\ k \end{Bmatrix} = \begin{cases} k\begin{Bmatrix} n-1 \\ k \end{Bmatrix} + \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}, 0\lt k\lt n \\ 0, k = 0 \\ 0, n = 0 \\ 0, k \gt n \\ 1, k = n \end{cases} [/math]


Таблица значений

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

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

[math]\lbrace{n\atop 0}\rbrace[/math] [math] = 0[/math]

[math]\lbrace{0\atop k}\rbrace[/math] [math]= 0[/math]

[math]\lbrace{n\atop n}\rbrace [/math][math]= 1[/math]

[math]\lbrace{n\atop n-1}\rbrace = \binom{n}{2}[/math]

[math] \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 [/math]

Свойства

  • [math]\lbrace{n+1\atop m+1}\rbrace = \sum_{k=0}^n \binom{n}{k} \textstyle \lbrace{k\atop m}\rbrace[/math]
  • [math]m![/math][math]\lbrace{n\atop m}\rbrace = \sum_{k=0}^n \binom{m}{k}[/math][math] k^n(-1)^{m-k}[/math]
  • [math]\sum_{k=0}^n \lbrace{n\atop k}\rbrace = B_n[/math], где [math]B_n[/math] — число Белла (число всех неупорядоченных разбиений n-элементного множества)

Применения

  • Пусть дано множество из [math]k[/math] элементарных исходов (все исходы равновероятны). Вероятность того, что после [math]n[/math] проведенных экспериментов каждое событие произойдет хотя бы один раз, может быть найдена по следующей формуле:[math]P = [/math][math]\lbrace{n\atop k}\rbrace {k! \over{k^n}}[/math]
  • [math]\lbrace{n+1\atop k+1}\rbrace[/math] — количество наборов из [math]k[/math] попарно непересекающихся подмножеств исходного множества [math]\{1,2...n\}[/math]. Например, [math]\lbrace{4\atop 3}\rbrace[/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{n\atop k}\rbrace^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{n\atop k}\rbrace^d = \lbrace{n-d+1\atop k-d+1}\rbrace,[/math][math] n \geqslant k \geqslant d[/math]
  • Также числа Стирлинга II рода можно определить как коэффициенты в разложении обычных степеней на факториальные: [math]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}}[/math], где [math]x^{\underline{k}} = x\cdot (x-1)\cdot \ldots\cdot (x-k+1)[/math] — убывающий факториал, [math]x^{\overline{k}} = x\cdot (x+1)\cdot \ldots\cdot (x+k-1)[/math] — возрастающий факториал. См. также связь между числами Стирлинга.

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

Теорема:
Числа Стирлинга II рода образуют матрицу переходов в линейном пространстве полиномов от базиса обычных степеней к базису убывающих факториальных степеней.
Доказательство:
[math]\triangleright[/math]
[math]x^{\underline{k+1}}=x^{\underline{k}}(x-k)[/math], отсюда [math]x\cdot x^{\underline{k}}=x^{\underline{k+1}}+kx^{\underline{k}}[/math], следовательно, [math]x\cdot x^{\underline{n-1}}[/math] есть

[math]x\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace x^{\underline{k}}=\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace x^{\underline{k+1}}+\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace kx^{\underline{k}}=[/math]

[math]\sum_{k=0}^n \textstyle \lbrace{n-1\atop k-1}\rbrace x^{\underline{k}}+\sum_{k=0}^n \textstyle \lbrace{n-1\atop k}\rbrace kx^{\underline{k}}= [/math]

[math]\sum_{k=0}^n \textstyle (k\lbrace{n-1\atop k}\rbrace + \lbrace{n-1\atop k-1}\rbrace )x^{\underline{k}}=\sum_{k=0}^n \textstyle \lbrace{n\atop k}\rbrace x^{\underline{k}} [/math]
[math]\triangleleft[/math]

См. также

Числа Эйлера

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