Числа Стірлінга другого роду

В комбинаториці числом Стірлінга другого роду S(n, k) називається число невпорядкованих розбиттів n-елементної множини на k непустих підмножин. Дані числа названі на честь Джеймса Стірлінґа.

Рекурентні співвідношення

Числа Стірлінга другого роду задаються рекурентним співвідношенням:

$S(n, n) = 1 \,$, для n ≥ 0,

$S(n, 0) = 0 \,$, для n > 0,

$S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k)$ для $0 < k < n.$

Дійсно будь-яке розбиття n-елементної множини на k непустих підмножин або містить одноелементну множину {n} або не містить її. В першому випадку кількість розбиттів становить $S(n-1, k-1) \,$ оскільки решту n-1 елементів слід розбити на k-1 підмножину. У другому випадку кількість розбиттів становить $k \cdot S(n-1, k) \,$ оскільки слід n-1 елементів розбити на k підмножин, після чого до якоїсь із них додати елемент n. Просумувавши оба випадки одержуємо необхідне співвідношення.

Приклади

Перші ряди:

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

Властивості

• $x^n = \sum_{k=0}^n S(n, k) \cdot (x)_k,$ де $(x)_k = x (x-1) \cdots (x-k+1).$

Доведемо методом математичної індукції. Дане твердження справджується для випадку n=1.

Припустимо, що твердження виконується для деякого n. Тоді:

$x^{n+1}= x^n \cdot x = \sum_{k=0}^n S(n, k) \cdot (x)_k \cdot ((x-k)+k),$

Оскільки:

$(x)_k(x-k)=(x)_{k+1} \,$

то маємо:

$x^{n+1}=\sum_{k=0}^n S(n, k)(x)_{k+1}+\sum_{k=0}^n kS(n, k)(x)_k = \sum_{k=0}^{n+1}S(n, k-1) + k \cdot S(n, k)(x)_k=\sum_{k=0}^{n+1} S(n+1, k) \cdot (x)_k$

де використано $S(n, 0)=S(n, n+1)=0 , \,$ а також рекурентне співвідношення дл чисел Стірлінга другого роду.

Таким чином отримуємо, що твердження виконується для всіх цілих чисел.

• $S(m,n)=\sum^{m-1}_{i=n-1} \binom{m-1}{i}\,S(i,n-1)$
• $\sum_{m=0}^n S(n,m) = B_n$ — число Белла.

Очевидно випливає з визначень чисел Белла і Сттірлінга другого роду.

• $S(n, k)\equiv\binom{z}{w}\pmod{2},\quad z = n - \left\lceil\dfrac{k + 1}{2}\right\rceil,\ w = \left\lfloor\dfrac{k - 1}{2}\right\rfloor.$
•  :$\left\{\begin{matrix} n \\ n-1 \end{matrix}\right\} = {n \choose 2}.$

Дійсно, розбиття на n-1 підмножину можливе тоді коли одна підмножина має два елементи, а всі інші — по одному. Саме вибір цих двох елементів і визначає розбиття, тобто кількість розбиттів рівна кількості способів вибрати два елементи з n-1, що й демонструє дана формула.

$\left\{\begin{matrix} n \\ 2 \end{matrix}\right\} = 2^{n-1}-1.$

Справді є всього 2 ⁿ упорядкованих пар взаємодоповнюючих множин A і B. В одному випадку A є пустою, в іншому B є пустою, тому залишається 2 ⁿ − 2 пар підмножин. Для невпордкованих пар потрібто дане число поділити на 2, що й дає необхідний результат.

З рекурентного відношення таклж одержуємо:

$\left\{\begin{matrix} n \\ 2 \end{matrix}\right\} = \frac{ \frac11 (2^{n-1}-1^{n-1}) }{0!}$

$\left\{\begin{matrix} n \\ 3 \end{matrix}\right\} = \frac{ \frac11 (3^{n-1}-2^{n-1})- \frac12 (3^{n-1}-1^{n-1}) }{1!}$

$\left\{\begin{matrix} n \\ 4 \end{matrix}\right\} = \frac{ \frac11 (4^{n-1}-3^{n-1})- \frac22 (4^{n-1}-2^{n-1}) + \frac13 (4^{n-1}-1^{n-1})}{2!}$

$\left\{\begin{matrix} n \\ 5 \end{matrix}\right\} = \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!}$

$\vdots$

Програми для обчислення

Delphi

type
  TTwoDimArray = array of array of Double;
 
procedure GetStirlingNumbers(n_max, m_max: Integer; var StirlingNumbers: TTwoDimArray);
var
  I, J: Integer;
begin
  { Виділення пам'яті під масив чисел }
  SetLength(StirlingNumbers, n_max+1, m_max+1);
 
  { Заповнення масиву }
  { S(n,0) = 0 }
  for I := 0 to n_max do
    StirlingNumbers[I, 0] := 0;
 
  { S(n,n) = 1 }
  for I := 0 to n_max do
    StirlingNumbers[I, I] := 1;
 
  { S(n,m) = S(n-1,m-1) + m*S(n-1,m) }
  for I := 1 to n_max do
    for J := 1 to I-1 do
      StirlingNumbers[I, J] := StirlingNumbers[I-1, J-1] + J * StirlingNumbers[I-1, J];
end;

C#

void GetStirlingNumbers(int n_max, int m_max, double[,] StirlingNumbers)
{
  // Виділення пам'яті під масив чисел
  StirlingNumbers = new double [n_max+1, m_max+1];
 
  // Заповнення масиву
  // S(n,0) = 0
  for (int i = 0; i < n_max; i++)
    StirlingNumbers[i, 0] = 0;
 
  // S(n,n) = 1
  for (int i = 0; i < n_max; i++)
    StirlingNumbers[i, i] = 1;
 
  // S(n,m) = S(n-1,m-1) + m*S(n-1,m)
  for (int i = 1; i <= n_max; i++)
    for (int j = 1; j <= i-1; j++)
      StirlingNumbers[i, j] = StirlingNumbers[i-1, j-1] + j * StirlingNumbers[i-1, j];
}

Див. також

• Число Стірлінга першого роду

Посилання

• Д. Белешко Комбинаторика (часть 2). СПбГУ ИТМО.