Liczby Stirlinga II rodzaju mówią o liczbie sposobów, na jaki możemy podzielić zbiór rozróżnialnych niepowtarzalnych elementów (np. osoby z jednej klasy) na niepuste nierozróżnialne podzbiory (np. na grupy projektowe), przy czym liczebność tych podzbiorów jest ograniczona jedynie od dołu przez 1.

Jednym ze sposobów wyznaczania liczb Stirlinga II rodzaju jest poniższy wzór rekurencyjny (czytamy $k$ podzbiorów $n$):

$\left\{\begin{array}{c}n\\ k\end{array}\right\}=k\cdot \left\{\begin{array}{c}n-1\\ k\end{array}\right\}+\left\{\begin{array}{c}n-1\\ k-1\end{array}\right\}$

gdzie $n$ to liczba elementów w zbiorze, a $k$ to liczba podzbiorów, na które chcemy podzielić wyjściowy zbiór. Warunki początkowe prezentują się następująco:

$\left\{\begin{array}{c}n\\ 1\end{array}\right\}=1\text{, }\left\{\begin{array}{c}n\\ 0\end{array}\right\}=0\text{, }\left\{\begin{array}{c}n\\ n\end{array}\right\}=1$

Ponadto, jeżeli $k \gt n$ to $\left\{\begin{array}{c} n\\k \end{array}\right\}=0$.

Napisz program, który oblicza rekurencyjnie wartość liczby Stirlinga II rodzaju dla podanych liczebności zbioru n i liczby podzbiorów k. Przetestuj swój program dla liczby Stirlinga $\left\{\begin{array}{c} 7\\4 \end{array}\right\}$.

Zrealizuj zadanie w jednym z dostępnych języków programowania.

Specjalizacja:

Dane:

• n – liczba naturalna oznaczająca liczebność zbioru wejściowego

• k – liczba naturalna określająca, na ile podzbiorów dokonujemy podziału

Wynik:

Program na standardowym wyjściu wypisze wartość liczby Stirlinga II rodzaju $\left\{\begin{array}{c} n\\k \end{array}\right\}$.