234
правки
Изменения
Новая страница: «'''Числа Стирлинга второго рода''' <math>\begin{Bmatrix} n\\ k \end{Bmatrix}</math> — количество способов разби...»
'''Числа Стирлинга второго рода''' <math>\begin{Bmatrix}
n\\
k
\end{Bmatrix}</math> — количество способов разбиения множества из ''n'' элементов на ''k'' непустых подмножеств.
Например, существует семь способов разбиения четырехэлементного множества на две части:
<math>\{1,2,3\}\{4\}</math>
<math>\{1,2,4\}\{3\}</math>
<math>\{1,3,4\}\{2\}</math>
<math>\{2,3,4\}\{1\}</math>
<math>\{1,2\}\{3,4\}</math>
<math>\{1,3\}\{2,4\}</math>
<math>\{1,4\}\{2,3\}</math>
Следовательно, <math>\begin{Bmatrix}
4 \\
2
\end{Bmatrix} = 7</math>
== Рекуррентная формула ==
Если задано множество из '''n''' элементов, которое необходимо разбить на '''k''' непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть(<math>\begin{Bmatrix}
n-1 \\
k-1
\end{Bmatrix}</math> способами), либо поместить его в некоторое подмножество (<math>k\begin{Bmatrix}
n-1 \\
k
\end{Bmatrix}</math> способами, поскольку каждый из <math>\begin{Bmatrix}
n-1 \\
k
\end{Bmatrix}</math> способов распределения первых '''n-1''' элементов по '''k''' непустым частям дает '''k''' подмножеств, с которыми можно объединить последний элемент)
<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<k<n \\
0, k = 0 \\
0, n = 0 \\
0, k > n \\
1, k = n
\end{cases}
</math>
== Начальные значения чисел Стирлинга второго рода ==
{| style="width:400px; height:200px" border="1"
!n\k
! 0
!1
!2
!3
!4
!5
!6
!7
!8
!9
|-
!0
|1
|0
|0
|0
|0
|0
|0
|0
|0
|0
|-
!1
|0
|1
|0
|0
|0
|0
|0
|0
|0
|0
|-
!2
|0
|1
|1
|0
|0
|0
|0
|0
|0
|0
|-
!3
|0
|1
|3
|1
|0
|0
|0
|0
|0
|0
|-
!4
|0
|1
|7
|6
|1
|0
|0
|0
|0
|0
|-
!5
|0
|1
|15
|25
|10
|1
|0
|0
|0
|0
|-
!6
|0
|1
|31
|90
|65
|15
|1
|0
|0
|0
|-
!7
|0
|1
|63
|301
|350
|140
|21
|1
|0
|0
|-
!8
|0
|1
|127
|966
|1701
|1050
|266
|28
|1
|0
|-
!9
|0
|1
|255
|3025
|7770
|6951
|2646
|462
|36
|1
|}
== Свойства ==
* <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> — возрастающий факториал.
*<math> \textstyle \lbrace{n+1\atop m+1}\rbrace = \sum_{k=0}^n \binom{n}{k} \textstyle \lbrace{k\atop m}\rbrace</math>
*<math> m!\textstyle \lbrace{n\atop m}\rbrace = \sum_{k=0}^n \binom{m}{k} k^n(-1)^{m-k}</math>
*<math>\left \lbrack{n\atop k} \right \rbrack = \textstyle \lbrace{-n\atop -k}\rbrace</math>, <math>n,k \in \mathbb{Z}</math>
n\\
k
\end{Bmatrix}</math> — количество способов разбиения множества из ''n'' элементов на ''k'' непустых подмножеств.
Например, существует семь способов разбиения четырехэлементного множества на две части:
<math>\{1,2,3\}\{4\}</math>
<math>\{1,2,4\}\{3\}</math>
<math>\{1,3,4\}\{2\}</math>
<math>\{2,3,4\}\{1\}</math>
<math>\{1,2\}\{3,4\}</math>
<math>\{1,3\}\{2,4\}</math>
<math>\{1,4\}\{2,3\}</math>
Следовательно, <math>\begin{Bmatrix}
4 \\
2
\end{Bmatrix} = 7</math>
== Рекуррентная формула ==
Если задано множество из '''n''' элементов, которое необходимо разбить на '''k''' непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть(<math>\begin{Bmatrix}
n-1 \\
k-1
\end{Bmatrix}</math> способами), либо поместить его в некоторое подмножество (<math>k\begin{Bmatrix}
n-1 \\
k
\end{Bmatrix}</math> способами, поскольку каждый из <math>\begin{Bmatrix}
n-1 \\
k
\end{Bmatrix}</math> способов распределения первых '''n-1''' элементов по '''k''' непустым частям дает '''k''' подмножеств, с которыми можно объединить последний элемент)
<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<k<n \\
0, k = 0 \\
0, n = 0 \\
0, k > n \\
1, k = n
\end{cases}
</math>
== Начальные значения чисел Стирлинга второго рода ==
{| style="width:400px; height:200px" border="1"
!n\k
! 0
!1
!2
!3
!4
!5
!6
!7
!8
!9
|-
!0
|1
|0
|0
|0
|0
|0
|0
|0
|0
|0
|-
!1
|0
|1
|0
|0
|0
|0
|0
|0
|0
|0
|-
!2
|0
|1
|1
|0
|0
|0
|0
|0
|0
|0
|-
!3
|0
|1
|3
|1
|0
|0
|0
|0
|0
|0
|-
!4
|0
|1
|7
|6
|1
|0
|0
|0
|0
|0
|-
!5
|0
|1
|15
|25
|10
|1
|0
|0
|0
|0
|-
!6
|0
|1
|31
|90
|65
|15
|1
|0
|0
|0
|-
!7
|0
|1
|63
|301
|350
|140
|21
|1
|0
|0
|-
!8
|0
|1
|127
|966
|1701
|1050
|266
|28
|1
|0
|-
!9
|0
|1
|255
|3025
|7770
|6951
|2646
|462
|36
|1
|}
== Свойства ==
* <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> — возрастающий факториал.
*<math> \textstyle \lbrace{n+1\atop m+1}\rbrace = \sum_{k=0}^n \binom{n}{k} \textstyle \lbrace{k\atop m}\rbrace</math>
*<math> m!\textstyle \lbrace{n\atop m}\rbrace = \sum_{k=0}^n \binom{m}{k} k^n(-1)^{m-k}</math>
*<math>\left \lbrack{n\atop k} \right \rbrack = \textstyle \lbrace{-n\atop -k}\rbrace</math>, <math>n,k \in \mathbb{Z}</math>
