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

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

15 розбиттів 4-елементної множини
у вигляді діаграми Гассе

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

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

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

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

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

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

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

Властивості

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

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

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

${\displaystyle x^{n+1}=x^{n}\cdot x=\sum _{k=0}^{n}S(n,k)\cdot (x)_{k}\cdot ((x-k)+k),}$

Оскільки:

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

то маємо:

${\displaystyle 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}}$

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

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

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

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

• ${\displaystyle 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 .}$
• :${\displaystyle \left\{{\begin{matrix}n\\n-1\end{matrix}}\right\}={n \choose 2}.}$

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

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

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

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

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

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

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

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

${\displaystyle \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]; } 

Див. також

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

Посилання

• Д. Белешко . СПбГУ ИТМО.