Liczby Stirlinga

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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ń


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

Liczby Stirlinga I rodzaju[edytuj | edytuj kod]

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 \\ 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.

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)

oraz

\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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

Liczby Stirlinga II rodzaju[edytuj | edytuj kod]

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)

oraz

\left\{\begin{matrix} n \\ k \end{matrix}\right\} = S_{2} (n,k)

Liczby Stirlinga drugiego rodzaju są zawsze nieujemne.

Potęgi kroczące[edytuj | edytuj kod]

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

Pochodzenie wzoru rekurencyjnego[edytuj | edytuj kod]

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.

Trójkąt liczbowy[edytuj | edytuj kod]

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

Własności liczb[edytuj | edytuj kod]

  • \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)
  • \left\{ \begin{matrix}  n \\ k\\\end{matrix} \right\} = \left[\begin{matrix} -k \\ -n\\ \end{matrix}\right] (prawo dualności)
  • \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:

\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

\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 \delta_{jk} to delta Kroneckera, j, k \ge 0.


Warto także odnotować fakt, że:


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

określa ilość L(n,k) surjekcji zbioru n elementowego na zbiór k elementowy, co łatwo udowodnić indukcyjnie zauważając związki:

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\ge1.

oraz, że L(n,n)=n!, dla dowolnego n\ge0.

Bibliografia[edytuj | edytuj kod]

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