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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
15 розбиттів 4-елементної множини
у вигляді діаграми Гассе

Тут присутні S(4,1),...,S(4,4) = 1,7,6,1.

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

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

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

, для n ≥ 0,
, для n > 0,
для

Дійсно будь-яке розбиття n-елементної множини на k непустих підмножин або містить одноелементну множину {n} або не містить її. В першому випадку кількість розбиттів становить оскільки решту n-1 елементів слід розбити на k-1 підмножину. У другому випадку кількість розбиттів становить оскільки слід 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

Властивості[ред.ред. код]

  • де
Доведемо методом математичної індукції. Дане твердження справджується для випадку n=1.
Припустимо, що твердження виконується для деякого n. Тоді:
Оскільки:
то маємо:
де використано а також рекурентне співвідношення для чисел Стірлінга другого роду.

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

  • число Белла.
Очевидно випливає з визначень чисел Белла і Сттірлінга другого роду.
  •  :
Дійсно, розбиття на n-1 підмножину можливе тоді коли одна підмножина має два елементи, а всі інші — по одному. Саме вибір цих двох елементів і визначає розбиття, тобто кількість розбиттів рівна кількості способів вибрати два елементи з n-1, що й демонструє дана формула.
Справді є всього 2 n упорядкованих пар взаємодоповнюючих множин A і B. В одному випадку A є пустою, в іншому B є пустою, тому залишається 2 n − 2 пар підмножин. Для невпордкованих пар потрібно дане число поділити на 2, що й дає необхідний результат.
З рекурентного відношення також одержуємо:

Програми для обчислення[ред.ред. код]

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];
}

Див. також[ред.ред. код]

Посилання[ред.ред. код]