В комбінаториці числом Стірлінга другого роду 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 90 11 0 12 0 1 13 0 1 3 14 0 1 7 6 15 0 1 15 25 10 16 0 1 31 90 65 15 17 0 1 63 301 350 140 21 18 0 1 127 966 1701 1050 266 28 19 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]; }

Див. також Число Стірлінга першого роду Функція fusc

Джерела