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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''Числа Стирлинга второго рода''' <math>\begin{Bmatrix} n\\ k \end{Bmatrix}</math> — количество способов разби...»)
(нет различий)

Версия 22:43, 18 декабря 2012

Числа Стирлинга второго рода [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\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 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]