Liczby Stirlinga

Z Wikipedii

Niniejszy artykuł jest częścią cyklu kombinatoryka.

permutacja

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ń

Ten szablon: pokaż • dyskusja • edytuj

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

[edytuj] Liczby Stirlinga I rodzaju

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

$\left[ \begin{matrix} n\\ k\\ \end{matrix} \right]$

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

$\left[ \begin{matrix} n\\ k\\ \end{matrix} \right] = (n-1) \left[ \begin{matrix} n - 1\\ k\\ \end{matrix} \right] + \left[ \begin{matrix} n - 1\\ k - 1\\ \end{matrix} \right]$

przy założeniach $\left[\begin{matrix} n \\ 0 \end{matrix}\right]=0 \quad \mbox { i } \quad \left[\begin{matrix} 1 \\ 1 \end{matrix}\right] = 1.$

Przyjmuje się, że jeżeli $k > n$ , to $\left[ \begin{matrix} n\\ k\\ \end{matrix} \right] = 0$

Niekiedy liczby Stirlinga pierwszego rodzaju są oznaczane innym symbolem:

$\left[\begin{matrix} n \\ k \end{matrix}\right]=s(n,k)$

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.

[edytuj] Pochodzenie wzoru rekurencyjnego

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.

[edytuj] Potęgi kroczące

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:

$x^{\underline{n}} = x(x-1)\ldots(x-n+1)\ = \sum _{k=0} ^{n} (-1)^{k+1} \left[\begin{matrix} n \\ k \end{matrix}\right] x^k$

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

$x^n = \sum _{k=1} ^{n} (-1)^{k+1} \left[\begin{matrix} n \\ k \end{matrix}\right] x^{\overline{k}}$

[edytuj] Trójkąt liczbowy

Liczby Stirlinga I rodzaju tworzą trójkąt liczbowy podobny do trójkąta Pascala.

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

[edytuj] Liczby Stirlinga II rodzaju

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

$\left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\}$

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

$\left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\} = k \left\{ \begin{matrix} n - 1\\ k\\ \end{matrix} \right\} + \left\{ \begin{matrix} n - 1\\ k - 1\\ \end{matrix} \right\}$

przy założeniach $\left\{\begin{matrix} n \\ 1 \end{matrix}\right\}=1 \quad \mbox { i } \quad \left\{\begin{matrix} n \\ n \end{matrix}\right\} = 1.$

Przyjmuje się, że jeżeli $k > n$ , to $\left\{ \begin{matrix} n\\ k\\ \end{matrix} \right\} = 0$

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

$\left\{\begin{matrix} n \\ k \end{matrix}\right\} = S(n,k)$

Liczby Stirlinga drugiego rodzaju są zawsze nieujemne.

[edytuj] Potęgi kroczące

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ść:

$x^n = \sum _{k=0} ^{n} \left\{\begin{matrix} n \\ k \end{matrix}\right\} x^{\underline{k}}$

[edytuj] Pochodzenie wzoru rekurencyjnego

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.

[edytuj] Trójkąt liczbowy

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

[edytuj] Własności liczb

$\left[ \begin{matrix} n\\ 1\\ \end{matrix} \right] =(n-1)!$
$\left[ \begin{matrix} n\\ n\\ \end{matrix} \right] = \left\{ \begin{matrix} n\\ n\\ \end{matrix} \right\} = 1$
$\left[ \begin{matrix} n\\ n-1\\ \end{matrix} \right] = \left\{ \begin{matrix} n\\ n-1\\ \end{matrix} \right\} = \left( \begin{matrix} n\\ 2\\ \end{matrix} \right)$
$\sum _{k=0} ^{n} \left[ \begin{matrix} n\\ k\\ \end{matrix} \right] = n!$