Liczby Stirlinga

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu kombinatoryka.




permutacja bez powtórzeń
permutacja z powtórzeniami


kombinacja bez powtórzeń
kombinacja z powtórzeniami


wariacja bez powtórzeń
wariacja z powtórzeniami


liczby Bella
liczby Catalana
liczby Stirlinga
liczby Eulera


zasada szufladkowa Dirichleta
zasada włączeń i wyłączeń


Liczby Stirlinga - dwa szczególne ciągi liczbowe analizowane przez Jamesa Stirlinga.

Liczby Stirlinga I rodzaju[edytuj]

Opisują liczbę sposobów na rozmieszczenie n liczb w k cyklach, oznaczane są symbolem:

Który czyta się "k cykli n". Spełniają one związek rekurencyjny postaci:

przy założeniach

Przyjmuje się, że jeżeli , to

Niekiedy liczby Stirlinga pierwszego rodzaju są oznaczane innym symbolem:

oraz

Czasami przyjmuje się także naprzemienne, dodatnie i ujemne wartości liczb Stirlinga pierwszego rodzaju, co ma uzasadnienie przy wzorach na potęgi kroczące. W przyjętej tu konwencji liczby Stirlinga pierwszego rodzaju są zawsze nieujemne.

Pochodzenie wzoru rekurencyjnego[edytuj]

Przyjmując za znaczenie liczb Stirlinga pierwszego rodzaju ilość rozmieszczeń n–liczb w k–cyklach, łatwo jest pokazać pochodzenie rekurencyjnej zależności między nimi. Wystarczy wybrać dowolną liczbę i rozpatrzyć ilość pozostałych cykli. Jeżeli ta liczba była w cyklu, składającym się z jednego elementu, to pozostałe n-1–liczb jest rozmieszczonych w k-1–cyklach, zaś dodanie jednej cyfry następuje w jeden sposób, poprzez stworzenie nowego cyklu. Jeżeli liczba była w liczniejszym cyklu, to pozostałe n-1–liczb jest rozmieszczonych w k–cyklach, zaś dodatkową liczbę można wstawić do dowolnego cyklu w dowolny sposób, czyli "obok" każdej liczby, a liczb jest n-1, co oznacza n-1–sposobów umieszczenia liczby w tym przypadku. Rekurencyjna zależność jest sumą obu przypadków. Warto przy tym zauważyć, że zbiór n–liczb można ustawić w 0 cykli na 0 sposobów, oraz 1 liczbę w 1 cyklu na 1 sposób.

Potęgi kroczące[edytuj]

Liczby Stirlinga pierwszego rodzaju bywają także definiowane jako współczynniki, występujące przy zamianie potęg malejących (silni dolnej) na zwyczajne potęgi:

Przy zamianie normalnych potęg na potęgi rosnące (silnię górną) występuje zależność:

Trójkąt liczbowy[edytuj]

Liczby Stirlinga I rodzaju tworzą trójkąt liczbowy podobny do trójkąta Pascala. (Przyjęto tu naprzemienne, dodatnie i ujemne wartości liczb Stirlinga, co ma uzasadnienie tylko przy wzorach na potęgi kroczące)

n/k 0 1 2 3 4 5 6 7 8 9
0 1
1 0 1
2 0 -1 1
3 0 2 -3 1
4 0 -6 11 -6 1
5 0 24 -50 35 -10 1
6 0 -120 274 -225 85 -15 1
7 0 720 -1764 1624 -735 175 -21 1
8 0 -5040 13068 -13132 6769 -1960 322 -28 1
9 0 40320 -109584 118124 -67284 22449 -4536 546 -36 1

Liczby Stirlinga II rodzaju[edytuj]

Opisują liczbę sposobów podziału zbioru n elementowego na k niepustych podzbiorów, oznaczane są symbolem:

który czyta się "k podzbiorów n". Spełniają one związek rekurencyjny postaci:

przy założeniach

Przyjmuje się, że jeżeli , to

Niekiedy liczby Stirlinga drugiego rodzaju zapisywane są w inny sposób:

oraz

Liczby Stirlinga drugiego rodzaju są zawsze dodatnie.

Potęgi kroczące[edytuj]

Niekiedy liczby Stirlinga drugiego rodzaju są definiowane jako współczynniki, występujące przy zamianie normalnych potęg na potęgi malejące (silnię dolną). Zachodzi wówczas zależność:

Pochodzenie wzoru rekurencyjnego[edytuj]

Przyjmując za znaczenie liczb Stirlinga drugiego rodzaju ilość sposobów podziału zbioru n–elementowego na k–podzbiorów niepustych, łatwo jest uzasadnić rekurencyjną zależność. Rozpatrzymy zbiór n–liczb, i wybierzmy jedną z nich. Jeżeli ta liczba stanowiła jednoelementowy podzbiór, to pozostałe n-1–liczb będzie podzielone na k-1–podzbiorów, zaś jedną liczbę można dodać na jeden sposób, jako kolejny podzbiór. Jeżeli liczba była elementem liczniejszego podzbioru, to pozostałe n-1–liczb zostało podzielone na k–podzbiorów, zaś dodatkową liczbę można dołączyć do każdego z podzbiorów, których jest k. Można to więc w tym przypadku zrobić na dokładnie k–sposobów. Rekurencyjna zależność jest sumą obu przypadków. Warto przy tym zauważyć, że zbiór n–liczb można podzielić na 1 podzbiór na 1 sposób, a także na n–podzbiorów na 1 sposób.

Trójkąt liczbowy[edytuj]

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

Własności liczb[edytuj]

  • (prawo dualności)

Z wzorów, pokazujących zależności między potęgami kroczącymi a normalnymi potęgami wynikają następujące zależności:

oraz

gdzie to delta Kroneckera, .


Warto także odnotować fakt, że:

określa ilość surjekcji zbioru n elementowego na zbiór k elementowy, co łatwo udowodnić indukcyjnie zauważając związki:

oraz, że , dla dowolnego .

Bibliografia[edytuj]

  • Donald Ervin Knuth, Grzegorz Jakacki: Sztuka programowania. T. 1, Algorytmy podstawowe. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002. ISBN 83-204-2540-9 (t. 1).