Tekst źródłowy strony Liczby Stirlinga

'''Liczby Stirlinga''' – dwie szczególne funkcje liczbowe analizowane przez [[James Stirling (matematyk)|Jamesa Stirlinga]]<ref>{{Cytuj |tytuł = Stirling numbers – Encyclopedia of Mathematics |data dostępu = 2017-11-01 |opublikowany = www.encyclopediaofmath.org |url = https://www.encyclopediaofmath.org/index.php/Stirling_numbers |język = en}}</ref>.

== Liczby Stirlinga I rodzaju ==
Opisują liczbę sposobów na rozmieszczenie <math>n</math> liczb w <math>k</math> [[Permutacja#Cykle|cyklach]], oznaczane są symbolem<ref name="knuth_mk288-299">{{Cytuj książkę | autor = Ronald L. Graham, Donald E. Knuth, Oren Patashnik | tytuł = Matematyka konkretna | wydawca = PWN | data = 2001 | strony = 288-299 | isbn = 8301121246}}</ref>:
:: <math>\left[\begin{matrix}n\\k\end{matrix}\right],</math>

który czyta się „k cykli n”. Spełniają one związek rekurencyjny postaci:
:: <math>
\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],</math>

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

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

Niekiedy liczby Stirlinga pierwszego rodzaju są oznaczane innym symbolem:
:: <math>\left[\begin{matrix} n \\ k \end{matrix}\right]=s(n,k)</math>

oraz
:: <math>\left[\begin{matrix} n \\ k \end{matrix}\right]=s_1 (n,k).</math>

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ń <math>n</math> liczb w <math>k</math> 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 <math>n-1</math> liczb jest rozmieszczonych w <math>k-1</math> 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 <math>n-1</math> liczb jest rozmieszczonych w <math>k</math> cyklach, zaś dodatkową liczbę można wstawić do dowolnego cyklu w dowolny sposób, czyli „obok” każdej liczby, a liczb jest <math>n-1,</math> co oznacza <math>n-1</math> sposobów umieszczenia liczby w tym przypadku. Rekurencyjna zależność jest sumą obu przypadków. Warto przy tym zauważyć, że zbiór <math>n</math> 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ęgi kroczące|potęg malejących]] (silni dolnej) na zwyczajne [[Potęgowanie|potęgi]]:
:: <math>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.</math>

Przy zamianie normalnych potęg na potęgi rosnące (silnię górną) występuje zależność:
:: <math>x^n = \sum_{k=1}^n (-1)^{k+1} \left[\begin{matrix} n \\ k \end{matrix}\right] x^{\overline{k}}.</math>

=== Trójkąt liczbowy ===
Liczby Stirlinga I rodzaju tworzą trójkąt liczbowy podobny do [[trójkąt Pascala|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)
{|
|
{{Trójkąt Stirlinga I}}
|}

== Liczby Stirlinga II rodzaju ==
Opisują liczbę sposobów podziału zbioru <math>n</math>-elementowego na <math>k</math> niepustych podzbiorów, oznaczane są symbolem <math>\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\},</math> który czyta się „k podzbiorów n”. Spełniają one związek rekurencyjny postaci<ref name="knuth_mk290">{{Cytuj książkę | autor = Ronald L. Graham, Donald E. Knuth, Oren Patashnik | tytuł = Matematyka konkretna | wydawca = PWN | data = 2001 | strony = 290 | isbn = 8301121246}}</ref>:
:: <math>
\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\},</math>

przy założeniach
:: <math>
\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.</math>

Przyjmuje się, że jeżeli <math>k > n,</math> to <math>\left\{ \begin{smallmatrix} n\\ k \end{smallmatrix} \right\} = 0.</math>

Niekiedy liczby Stirlinga drugiego rodzaju zapisywane są w inny sposób: <math>\left\{\begin{smallmatrix} n \\ k \end{smallmatrix}\right\} = S(n,k)</math> bądź <math>\left\{\begin{smallmatrix} n \\ k \end{smallmatrix}\right\} = S_2 (n,k).</math> Liczby Stirlinga drugiego rodzaju są zawsze dodatnie.

=== 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ść<ref name="knuth_mk293">{{Cytuj książkę | autor = Ronald L. Graham, Donald E. Knuth, Oren Patashnik | tytuł = Matematyka konkretna | wydawca = PWN | data = 2001 | strony = 293 | isbn = 8301121246}}</ref>:
: <math>x^n = \sum_{k=0}^n \left\{\begin{matrix} n \\ k \end{matrix}\right\} x^{\underline{k}}.</math>

=== Pochodzenie wzoru rekurencyjnego ===
Przyjmując za znaczenie liczb Stirlinga drugiego rodzaju liczbę sposobów podziału zbioru <math>n</math>-elementowego na <math>k</math> podzbiorów niepustych, łatwo jest uzasadnić rekurencyjną zależność. Rozpatrzymy zbiór <math>n</math> liczb, i wybierzmy jedną z nich. Jeżeli ta liczba stanowiła jednoelementowy [[podzbiór]], to pozostałe <math>n-1</math> liczb będzie podzielone na <math>k-1</math> 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 <math>n-1</math> liczb zostało podzielone na <math>k</math> podzbiorów, zaś dodatkową liczbę można dołączyć do każdego z podzbiorów, których jest <math>k.</math> Można to więc w tym przypadku zrobić na dokładnie <math>k</math> sposobów. Rekurencyjna zależność jest sumą obu przypadków. Warto przy tym zauważyć, że zbiór <math>n</math> liczb można podzielić na 1 podzbiór na 1 sposób, a także na <math>n</math> podzbiorów na 1 sposób.

=== Trójkąt liczbowy ===
{|
|
{{Trójkąt Stirlinga II}}
|}

== Własności liczb ==
* <math>\left [\begin{matrix}n \\ 1  \end{matrix}\right] = (n-1)!,</math>
* <math>\left [\begin{matrix}n \\ n  \end{matrix}\right] = \left\{\begin{matrix}n\\n\end{matrix}\right\}= 1,</math>
* <math>\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),</math>
* <math>\left\{\begin{matrix}n \\ k  \end{matrix}\right\} = \left[\begin{matrix} -k \\ -n \end{matrix}\right]</math> (prawo dualności),
* <math>\sum_{k=0}^n \left[\begin{matrix}n\\k\end{matrix}\right]= n!.</math>

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<ref name="knuth_mk295">{{Cytuj książkę | autor = Ronald L. Graham, Donald E. Knuth, Oren Patashnik | tytuł = Matematyka konkretna | wydawca = PWN | data = 2001 | strony = 295 | isbn = 8301121246}}</ref>:
:: <math>\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}</math>

oraz<ref name="knuth_mk295" /> 
:: <math>\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},</math>

gdzie <math>\delta_{jk}</math> to [[Symbol Kroneckera|delta Kroneckera]], <math>j, k \geqslant 0.</math>

Warto także odnotować fakt, że:
:: <math>k!\cdot \left\{\begin{matrix} n \\ k \end{matrix}\right\}.</math>

określa liczbę <math>L(n,k)</math> [[Funkcja „na”|surjekcji]] zbioru <math>n</math>-elementowego na zbiór <math>k</math>-elementowy, co łatwo udowodnić indukcyjnie zauważając związki:
:: <math>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</math>

oraz że <math>L(n,n)=n!,</math> dla dowolnego <math>n\geqslant 0.</math>

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{Cytuj książkę |nazwisko = Knuth |imię = Donald Ervin | autor link = Donald Knuth |nazwisko2 = Jakacki |imię2 = Grzegorz |tytuł = Sztuka programowania. T. 1, Algorytmy podstawowe |data = 2002 |wydawca = [[Wydawnictwa Naukowo-Techniczne]] |miejsce = Warszawa |id = {{ISBN|83-204-2540-9}} (t. 1)}}

== Linki zewnętrzne ==
* {{Pismo Delta | url = 2001/11/liczby-stirlinga-a-skoki-narciarskie/ | autor = [[Adam Woryna]] | tytuł = Liczby Stirlinga a skoki narciarskie | data = listopad 2001 | data dostępu = 2024-11-02 }}
* {{MathWorld | adres = StirlingNumberoftheFirstKind | tytuł = Stirling Number of the First Kind }} [dostęp 2024-05-12].
* {{MathWorld | adres = StirlingNumberoftheSecondKind | tytuł = Stirling Number of the Second Kind }} [dostęp 2024-05-12].

{{Kombinatoryka}}
{{Typy liczb naturalnych}}

[[Kategoria:Kombinatoryka]]
[[Kategoria:Działania na liczbach]]
[[Kategoria:Rodzaje liczb naturalnych|S]]