Числа Стірлінга другого роду
В комбінаториці числом Стірлінга другого роду 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];
}
Див. також
Посилання
- Д. Белешко Комбинаторика (часть 2). СПбГУ ИТМО.