Numbers Stirling's: Liczby Stirlinga

Liczby Stirlinga są to dwa szczególne ciągi liczbowe analizowane przez Jamesa Stirlinga

Liczby Stirlinga I rodzaju

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

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]$

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.

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.

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}}$

Trójkąt liczbowy

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

http://numbers-stirlinga.blogspot.com/2012/11/liczby-stirlinga.html

Numbers Stirling's

wtorek, 6 listopada 2012

Liczby Stirlinga