Liczby Stirlinga – dwie szczególne funkcje liczbowe analizowane przez Jamesa Stirlinga[1].
Opisują liczbę sposobów na rozmieszczenie
liczb w
cyklach, oznaczane są symbolem[2]:
![{\displaystyle \left[{\begin{matrix}n\\k\end{matrix}}\right],}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/772a00ffb9d0d694bda17951b2e5cc2af656bf40)
który czyta się „k cykli n”. Spełniają one związek rekurencyjny postaci:
![{\displaystyle \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],}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/ed04a6a21defe3023e54ed6d9ef61103dd8197fe)
przy założeniach
Przyjmuje się, że jeżeli
to
Niekiedy liczby Stirlinga pierwszego rodzaju są oznaczane innym symbolem:
![{\displaystyle \left[{\begin{matrix}n\\k\end{matrix}}\right]=s(n,k)}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/03a86615f2217e1bcb2401407be4f1261e8da424)
oraz
![{\displaystyle \left[{\begin{matrix}n\\k\end{matrix}}\right]=s_{1}(n,k).}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/c80d7cab061eb2f311c62baf7f1407d7d1780cc5)
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.
Przyjmując za znaczenie liczb Stirlinga pierwszego rodzaju ilość rozmieszczeń
liczb w
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
liczb jest rozmieszczonych w
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
liczb jest rozmieszczonych w
cyklach, zaś dodatkową liczbę można wstawić do dowolnego cyklu w dowolny sposób, czyli „obok” każdej liczby, a liczb jest
co oznacza
sposobów umieszczenia liczby w tym przypadku. Rekurencyjna zależność jest sumą obu przypadków. Warto przy tym zauważyć, że zbiór
liczb można ustawić w 0 cykli na 0 sposobów, oraz 1 liczbę w 1 cyklu na 1 sposób.
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:
![{\displaystyle x^{\underline {n}}=x(x-1)\dots (x-n+1)\ =\sum _{k=0}^{n}(-1)^{n-k}\left[{\begin{matrix}n\\k\end{matrix}}\right]x^{k}.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/22431bfe081dc01fa349fe53d49b58e2875e7ea8)
Przy zamianie normalnych potęg na potęgi rosnące (silnię górną) występuje zależność:
![{\displaystyle x^{n}=\sum _{k=1}^{n}(-1)^{k+1}\left[{\begin{matrix}n\\k\end{matrix}}\right]x^{\overline {k}}.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/542469fa44f93493411e1dbe2ea56d7095b75a2e)
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)
|
Opisują liczbę sposobów podziału zbioru
-elementowego na
niepustych podzbiorów, oznaczane są symbolem
który czyta się „k podzbiorów n”. Spełniają one związek rekurencyjny postaci[3]:
![{\displaystyle \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\},}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/818b10b0509d703534579bd4816d639b47178b38)
przy założeniach
![{\displaystyle \left\{{\begin{smallmatrix}n\\1\end{smallmatrix}}\right\}=1,\quad \left\{{\begin{smallmatrix}n\\n\end{smallmatrix}}\right\}=1,\quad \left\{{\begin{smallmatrix}n\\0\end{smallmatrix}}\right\}=0\quad {\mbox{i}}\quad \left\{{\begin{smallmatrix}0\\0\end{smallmatrix}}\right\}=1.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/330e709c49dff3e7c91670733e6718bde2ae6dc3)
Przyjmuje się, że jeżeli
to
Niekiedy liczby Stirlinga drugiego rodzaju zapisywane są w inny sposób:
bądź
Liczby Stirlinga drugiego rodzaju są zawsze dodatnie.
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ść[4]:
![{\displaystyle x^{n}=\sum _{k=0}^{n}\left\{{\begin{matrix}n\\k\end{matrix}}\right\}x^{\underline {k}}.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/3dcb1e9122ae034811ee9f458ae30e2f354184bf)
Przyjmując za znaczenie liczb Stirlinga drugiego rodzaju liczbę sposobów podziału zbioru
-elementowego na
podzbiorów niepustych, łatwo jest uzasadnić rekurencyjną zależność. Rozpatrzymy zbiór
liczb, i wybierzmy jedną z nich. Jeżeli ta liczba stanowiła jednoelementowy podzbiór, to pozostałe
liczb będzie podzielone na
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
liczb zostało podzielone na
podzbiorów, zaś dodatkową liczbę można dołączyć do każdego z podzbiorów, których jest
Można to więc w tym przypadku zrobić na dokładnie
sposobów. Rekurencyjna zależność jest sumą obu przypadków. Warto przy tym zauważyć, że zbiór
liczb można podzielić na 1 podzbiór na 1 sposób, a także na
podzbiorów na 1 sposób.
|
![{\displaystyle \left[{\begin{matrix}n\\1\end{matrix}}\right]=(n-1)!,}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/bb373744bbd7b0c03a67856a35cf4b7f507efb04)
![{\displaystyle \left[{\begin{matrix}n\\n\end{matrix}}\right]=\left\{{\begin{matrix}n\\n\end{matrix}}\right\}=1,}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/cb2a7c92b82a2e9339d1a5a08a0631212f5ac50c)
![{\displaystyle \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),}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/c6012119da3e62d569df0986448b0161606d04ca)
(prawo dualności),
![{\displaystyle \sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]=n!.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/35487b398aecd147e7afd91bd3b7f6fcaeedc462)
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[5]:
![{\displaystyle \sum _{n=0}^{\max\{j,k\}}(-1)^{n+1}\left[{\begin{matrix}n\\j\end{matrix}}\right]\left\{{\begin{matrix}k\\n\end{matrix}}\right\}=\delta _{jk}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/f4fe189d8918c601c66d8af0134d352bf8cc354b)
oraz[5]
![{\displaystyle \sum _{n=0}^{\max\{j,k\}}(-1)^{n+1}\left\{{\begin{matrix}n\\j\end{matrix}}\right\}\left[{\begin{matrix}k\\n\end{matrix}}\right]=\delta _{jk},}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/616c1bc7b0b8243567ac52b98278122aa593c5a7)
gdzie
to delta Kroneckera,
Warto także odnotować fakt, że:
![{\displaystyle k!\cdot \left\{{\begin{matrix}n\\k\end{matrix}}\right\}.}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/c1c130500cd49f6a585818ee9ed2318cf31fc8a5)
określa liczbę
surjekcji zbioru
-elementowego na zbiór
-elementowy, co łatwo udowodnić indukcyjnie zauważając związki:
![{\displaystyle L(n,k)=k\cdot L(n-1,k)+L(n-1,k-1),\;L(n,1)=L(0,0)=1,\;L(n,0)=0,n\geqslant 1}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/afcefe7e77a9558d4a864e71aaa8dd3701909097)
oraz że
dla dowolnego
- ↑ Stirling numbers – Encyclopedia of Mathematics [online], www.encyclopediaofmath.org [dostęp 2017-11-01] (ang.).
- ↑ Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 288-299. ISBN 83-01-12124-6.
- ↑ Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 290. ISBN 83-01-12124-6.
- ↑ Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 293. ISBN 83-01-12124-6.
- ↑ a b Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 295. ISBN 83-01-12124-6.
zagadnienia – znajdowanie liczby | |
---|
inne |
|
---|