Liczby Stirlinga

Liczby Stirlinga – dwie szczególne funkcje liczbowe analizowane przez Jamesa Stirlinga[1].

Liczby Stirlinga I rodzaju

Opisują liczbę sposobów na rozmieszczenie n {\displaystyle n} liczb w k {\displaystyle k} cyklach, oznaczane są symbolem[2]:

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

który czyta się „k cykli n”. Spełniają one związek rekurencyjny postaci:

[ n k ] = ( n − 1 ) [ n − 1 k ] + [ n − 1 k − 1 ] , {\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],}

przy założeniach [ n n ] = 1 , [ n 0 ] = 0 i [ 0 0 ] = 1. {\displaystyle \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.}

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

Niekiedy liczby Stirlinga pierwszego rodzaju są oznaczane innym symbolem:

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

oraz

[ n k ] = s 1 ( n , k ) . {\displaystyle \left[{\begin{matrix}n\\k\end{matrix}}\right]=s_{1}(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 {\displaystyle n} liczb w k {\displaystyle 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 {\displaystyle n-1} liczb jest rozmieszczonych w k − 1 {\displaystyle 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 {\displaystyle n-1} liczb jest rozmieszczonych w k {\displaystyle 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 , {\displaystyle n-1,} co oznacza n − 1 {\displaystyle 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 {\displaystyle 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 n _ = x ( x − 1 ) … ( x − n + 1 )   = ∑ k = 0 n ( − 1 ) n − k [ n k ] x k . {\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}.}

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

x n = ∑ k = 1 n ( − 1 ) k + 1 [ n k ] x k ¯ . {\displaystyle 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. (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 {\displaystyle {\begin{matrix}\mathbf {n} /{\mathit {k}}&\ {\mathit {0}}\ &\ {\mathit {1}}\ &{\mathit {2}}&{\mathit {3}}&{\mathit {4}}&{\mathit {5}}&{\mathit {6}}&{\mathit {7}}&{\mathit {8}}&{\mathit {9}}\\\mathbf {0} &1\\\mathbf {1} &0&\ \ \ 1\\\mathbf {2} &0&-1&\ \ \ 1\\\mathbf {3} &0&\ \ \ 2&-3&\ \ \ 1\\\mathbf {4} &0&-6&\ \ \ 11&-6&\ \ \ 1\\\mathbf {5} &0&\ \ \ 24&-50&\ \ \ 35&-10&\ \ \ 1\\\mathbf {6} &0&-120&\ \ \ 274&-225&\ \ \ 85&-15&\ \ \ 1\\\mathbf {7} &0&\ \ \ 720&-1764&\ \ \ 1624&-735&\ \ \ 175&-21&\ \ \ 1\\\mathbf {8} &0&-5040&\ \ \ 13068&-13132&\ \ \ 6769&-1960&\ \ \ 322&-28&\ \ \ 1\\\mathbf {9} &0&\ \ \ 40320&-109584&\ \ \ 118124&-67284&\ \ \ 22449&-4536&\ \ \ 546&-36&1\\\end{matrix}}}


Liczby Stirlinga II rodzaju

Opisują liczbę sposobów podziału zbioru n {\displaystyle n} -elementowego na k {\displaystyle k} niepustych podzbiorów, oznaczane są symbolem { n k } , {\displaystyle \left\{{\begin{smallmatrix}n\\k\end{smallmatrix}}\right\},} który czyta się „k podzbiorów n”. Spełniają one związek rekurencyjny postaci[3]:

{ n k } = k { n − 1 k } + { n − 1 k − 1 } , {\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\},}

przy założeniach

{ n 1 } = 1 , { n n } = 1 , { n 0 } = 0 i { 0 0 } = 1. {\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.}

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

Niekiedy liczby Stirlinga drugiego rodzaju zapisywane są w inny sposób: { n k } = S ( n , k ) {\displaystyle \left\{{\begin{smallmatrix}n\\k\end{smallmatrix}}\right\}=S(n,k)} bądź { n k } = S 2 ( n , k ) . {\displaystyle \left\{{\begin{smallmatrix}n\\k\end{smallmatrix}}\right\}=S_{2}(n,k).} 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ść[4]:

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

Pochodzenie wzoru rekurencyjnego

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

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 {\displaystyle {\begin{matrix}\mathbf {n} /{\mathit {k}}&\ {\mathit {0}}\ &\ {\mathit {1}}\ &{\mathit {2}}&{\mathit {3}}&{\mathit {4}}&{\mathit {5}}&{\mathit {6}}&{\mathit {7}}&{\mathit {8}}&{\mathit {9}}\\\mathbf {0} &1\\\mathbf {1} &0&1\\\mathbf {2} &0&1&1\\\mathbf {3} &0&1&3&1\\\mathbf {4} &0&1&7&6&1\\\mathbf {5} &0&1&15&25&10&1\\\mathbf {6} &0&1&31&90&65&15&1\\\mathbf {7} &0&1&63&301&350&140&21&1\\\mathbf {8} &0&1&127&966&1701&1050&266&28&1\\\mathbf {9} &0&1&255&3025&7770&6951&2646&462&36&1\end{matrix}}}


Własności liczb

  • [ n 1 ] = ( n − 1 ) ! , {\displaystyle \left[{\begin{matrix}n\\1\end{matrix}}\right]=(n-1)!,}
  • [ n n ] = { n n } = 1 , {\displaystyle \left[{\begin{matrix}n\\n\end{matrix}}\right]=\left\{{\begin{matrix}n\\n\end{matrix}}\right\}=1,}
  • [ n n − 1 ] = { n n − 1 } = ( n 2 ) , {\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),}
  • { n k } = [ − k − n ] {\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=\left[{\begin{matrix}-k\\-n\end{matrix}}\right]} (prawo dualności),
  • ∑ k = 0 n [ n k ] = n ! . {\displaystyle \sum _{k=0}^{n}\left[{\begin{matrix}n\\k\end{matrix}}\right]=n!.}

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

∑ n = 0 max { j , k } ( − 1 ) n + 1 [ n j ] { k n } = δ j k {\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}}

oraz[5]

∑ n = 0 max { j , k } ( − 1 ) n + 1 { n j } [ k n ] = δ j k , {\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},}

gdzie δ j k {\displaystyle \delta _{jk}} to delta Kroneckera, j , k ⩾ 0. {\displaystyle j,k\geqslant 0.}

Warto także odnotować fakt, że:

k ! ⋅ { n k } . {\displaystyle k!\cdot \left\{{\begin{matrix}n\\k\end{matrix}}\right\}.}

określa liczbę L ( n , k ) {\displaystyle L(n,k)} surjekcji zbioru n {\displaystyle n} -elementowego na zbiór k {\displaystyle k} -elementowy, co łatwo udowodnić indukcyjnie zauważając związki:

L ( n , k ) = k ⋅ L ( n − 1 , k ) + L ( n − 1 , k − 1 ) , L ( n , 1 ) = L ( 0 , 0 ) = 1 , L ( n , 0 ) = 0 , n ⩾ 1 {\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}

oraz że L ( n , n ) = n ! , {\displaystyle L(n,n)=n!,} dla dowolnego n ⩾ 0. {\displaystyle n\geqslant 0.}

Przypisy

  1. ↑ Stirling numbers – Encyclopedia of Mathematics [online], www.encyclopediaofmath.org [dostęp 2017-11-01]  (ang.).
  2. ↑ Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 288-299. ISBN 83-01-12124-6.
  3. ↑ Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 290. ISBN 83-01-12124-6.
  4. ↑ Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 293. ISBN 83-01-12124-6.
  5. ↑ a b Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna. PWN, 2001, s. 295. ISBN 83-01-12124-6.

Bibliografia

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

Linki zewnętrzne

  • Eric W.E.W. Weisstein Eric W.E.W., Stirling Number of the First Kind, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-05-12].
  • Eric W.E.W. Weisstein Eric W.E.W., Stirling Number of the Second Kind, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-05-12].