Numbers Stirling's: Liczby Stirlinga II rodzaju

Liczby Stirlinga II rodzaju

Opisują liczbe sposobów podziału n elementowego na k niepustych podzbiorów, 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)$

Liczby Stirlinga drugiego rodzaju są zawsze nieujemne.

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ść:

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

Własności liczb

$\left[\begin{matrix} n\\ 1\\ \end{matrix}\right]=(n-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\Big(L(n-1,k)+L(n-1,k-1)\Big),\;L(n,1)=L(0,0)=1,\;L(n,0)=0, n\ge1.$

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

Numbers Stirling's

wtorek, 6 listopada 2012

Liczby Stirlinga II rodzaju

Liczby Stirlinga II rodzaju

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ść:

Pochodzenie wzoru rekurencyjnego

Trójkąt liczbowy

Własności liczb

$\left[\begin{matrix} n\\ 1\\ \end{matrix}\right]=(n-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!$

Brak komentarzy:

Prześlij komentarz