Strona główna » Algorytmy » Teoria Liczb » Liczby Stirlinga II rodzaju
{ }nk
 

Liczby Stirlinga II rodzaju

https://mattomatti.com/a0029

Definicja

Liczba możliwych podziałów zbioru n-elementowego na k niepustych (parami rozłącznych) podzbiorów nazywana jest liczbą Stirlinga drugiego rodzaju. Zwykle oznaczana jest przed dużą literę S tj. S(n, k).

Dla n > 0 przyjmuje się, że S(n, 1) = S(n, n) = 1, S(n, k) = 0 k > n, S(0, 0) = 1 oraz S(n, 0) = 0.

Do obliczania dowolnego wyrazu służy wzór rekurencyjny S(n, k) = S(n - 1, k - 1) + k·S(n - 1, k).

Trójkąt Stirlinga

Zazwyczaj podczas podawania zbioru liczb można podać ciąg, który można z nich utworzyć. Ze względu na zależność od dwóch zmiennych bardziej wygodne jest zapisanie ciągu w postaci trójkąta.

nk
0
111
2012
30113
401314
5017615
60115251016
7013190651517

W celu wyliczenia wartości pola należy pobrać wartość do góry na prawo i pomnożyć przez numer pozycji w wierszu i do tej wartości dodać pole do góry po lewo. Jeśli pole z którego ma zostać pobrana wartość nie istnieje to pobrana wartość wynosi 0.

Implementacja

Wyliczanie wyrazu rekurencyjnie

Wzór rekurencyjny należy zaimplementować tłumacząc wzór w sposób dosłowny. W tym jednak przypadku warunków w rekurencji jest znacznie więcej niż w przypadku typowej rekurencji. Przykładowa implementacja wygląda następująco:

  1. int stirlingII (unsigned int n, unsigned int k){
  2.   if (k > n || k == 0)
  3.     return 0;
  4.   if (k == n || k == 1)
  5.     return 1;
  6.   return k*stirlingII(n - 1, k) + stirlingII(n - 1, k - 1);
  7. }

(1.) Funkcja przyjmuje dwa argumenty o wartościach nieujemnych i (2. - 5.) sprawdzane są warunki stopu. Jeśli żaden warunek nei zostanie spełniony to (6.) zwracana jest wartość zgodnie ze wzorem rekurencyjnym.

Nieefektywne wypisywanie trójkąta Stirlinga

Posiadając funkcję stirlingII() istnieje możliwość wyświetlenia trójkątu Stirlinga przy pomocy poniższej funkcji main():

  1. int main () {
  2.   for (int i = 0; i < 6; i++) {
  3.     for (int j = 0; j <= i; j++) {
  4.       cout << stirlingII(i, j) << "\t";
  5.     }
  6.     cout << endl;
  7.   }
  8.   system("pause");
  9.   return 0;
  10. }

Warto jednak zauważyć, że jest to mało efektywne metoda, ponieważ każdy kolejny wiersz możnaby wyliczyć znacznie szybciej polegając na poprzednim wierszu. W tym przypadku jednak każdy wyraz jest wyliczany od nowa za każdym razem.

Trójkąt Stirlinga

Zasada tworzenia trójkąta Stirlinga jest bardzo podobna do trójkąta Pascala. Różni się jedynie mnożeniem jednego z czynników przy pomocy wartości k. Nie przeszkadza to jednak, aby wyliczać następny wiersz na podstawie poprzedniego.

Poniżej został zamieszczony kod wyznaczający kolejne wiersze trójkąta i wypisujące je od razu na ekran:

  1. void wypiszTrojkatStirlinga(unsigned int p) {
  2.   int* tab = new int[p+2];
  3.   tab[0] = 0;
  4.   tab[1] = 1;
  5.   tab[2] = 0;
  6.   cout << "1\n";
  7.   for (int i = 1; i < p; i++) {
  8.     for (int j = i + 1; j > 0; j--) {
  9.       tab[j] = j*tab[j] + tab[j - 1];
  10.     }
  11.     tab[i + 1] = 0;
  12.     for (int j = 0; j <= i; j++) {
  13.       cout << tab[j] << "\t";
  14.     }
  15.     cout << endl;
  16.   }
  17.   delete tab;
  18. }

(2.) Zanicjalizuj tablicę takiej długości, aby zmieścił się ostatni wiersz oraz dwa wyrazy pomocnicze 0. (3. - 5.) Określ postać pierwszego rzędu i (6.) wypisz go w sposób zapisany na stałe (upraszcza do dalszy kod). (7.) Dla każdego kolejnego wiersza: (8. - 10.) wylicz kolejny wiersz polegając na poprzednich wartościach. Ze względu na to, że dane są wpisywane do tablicy na podstawie której generowane są kolejne wiersze to należy wyliczać kolejne pola od prawej do lewej. (11.) Po wyliczeniu nowego wiersza należy ustalić kolejny nieustawiony element na tablicy na 0 (upraszcza to kod sumowanie, bo nie trzeba rozpatrywać przypadku, gdy pobierany element nie istnieje - w tym przypadku istnieje i wynosi 0). W każdej iteracji (12. - 15.) wypisz wiersz. Na koniec po zakończeniu wyliczania kolejnych wierszy (17.) usuń tablicę.

W celu przetestowania działania funkcji można skorzystać z poniższej funkcji main(). W tym przypadku wypisane zostaną pierwsze 8 wierszy trójkąta Stirlinga.

  1. int main() {
  2.   wypiszTrojkatStirlinga(8);
  3.   system("pause");
  4.   return 0;
  5. }

Zadania

Zadanie 1

Popraw kod wypisujący trójkąta Stirlinga tak, aby każdy wiersz został wyśrodkowany.