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

В комбинаторике числом Стирлинга второго рода 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.

Пример

Первые ряды:

	0	1	2	3	4	5	6
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

Свойства

• $x^n = \sum_{k=0}^n S(n, k) \cdot (x)_k,$ где $(x)_k = x (x-1) \cdots (x-k+1).$
• $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$ — число Белла.

Программы для расчета

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). СПбГУ ИТМО.