Liczba Stirlinga dla cykli \(\left[\begin{array} {c}n \\ k\end{array}\right ] \) (często nazywana liczbą Stirlinga pierwszego rodzaju) to liczba permutacji zbioru \( n \)-elementowego złożonych z dokładnie \( k \) cykli, czyli takich permutacji \( \pi \in S_n \), że \( c(\pi)=k \). Przyjmujemy, że \( \left[\begin{array} {c}0 \\ 0\end{array} \right]=1 \), a więc że jest jedna permutacja zbioru pustego bez cykli (funkcja pusta). Z powodów technicznych, w przekształceniach rachunkowych wygodnie jest mieć zdefiniowaną wartość \( \left[\begin{array} {c}n \\ k\end{array} \right] \) dla wszystkich \( k\in\mathbb{Z} \). Przyjmujemy, że \( \left[\begin{array} {c}n \\ k\end{array} \right]=0 \) dla \( k < 0 \).
Przykład
Lista permutacji \( \mathbb{Z}_4 \) złożonych z \( 2 \) cykli:
\( \begin{array} {ccc} (0,1,2)(3) & (0,2,3)(1) & (0,1)(2,3) \\ (0,2,1)(3) & (0,3,2)(1) & (0,2)(1,3) \\ (0,1,3)(2) & (1,2,3)(0) & (0,3)(1,2) \\ (0,3,1)(2) & (1,3,2)(0) \end{array} \)
Obserwacja 6.10
Dla \( n\in\mathbb{N} \)
Dowód
Pierwszy punkt jest natychmiastowa konsekwencją faktu, że nie można podzielić niepustego zbioru na \( 0 \) części (cykli).
Liczba \( \left[\begin{array} {c}n \\ 1\end{array} \right] \) opisuje permutacje o jednym cyklu. Każda taka permutacja jest zadana wzorcem \( (\underbrace{\bullet,\ldots,\bullet}_{n\ pozycji}) \). Wzorzec taki może być wypełniony \( n \)-elementami na \( n! \) sposobów. Ale ten sam cykl ma wiele opisów różniących się jedynie przesunięciem. Zatem każdy \( n \)-elementowy cykl może być zapisany według takiego wzorca na \( n \) sposobów, czyli liczba cykli na zbiorze \( n \)-elementowym to \( \frac{n!}{n}=(n-1)! \), co dowodzi punktu drugiego.
Liczba \( \left[\begin{array} {c}n \\ n-1\end{array} \right] \) opisuje permutacje o \( n-1 \) cyklach. Permutacja taka musi wiec być typu \( [1^{n-2}2^1] \), czyli jest transpozycją. Każda transpozycja jest jednoznacznie wyznaczona przez dwuelementowy zbiór elementów, które ze sobą zamienia. Zatem transpozycji jest dokładnie tyle co podzbiorów \( 2 \)-elementowych, czyli \( {n\choose2} \), co dowodzi punktu trzeciego.
Dla dowodu punktu czwartego zauważmy jedynie, że jedyną permutacją o \( n \) cyklach na zbiorze \( n \)-elementowym jest identyczność.
Równie łatwo jest stwierdzić, że zbiór \( n \)-elementowy nie może być podzielony na więcej niż \( n \) niepustych części (mających stanowić cykle).
Liczby Stirlinga dla cykli, podobnie jak współczynniki dwumianowe, można generować używając zależności rekurencyjnej. Na jej podstawie można zbudować Trójkąt Stirlinga dla cykli.
Obserwacja 6.11
Dla \( 0 < k\leq n \)
\( \left[\begin{array} {c}n \\ k\end{array} \right]=(n-1)\left[\begin{array} {c}n-1 \\ k\end{array} \right]+\left[\begin{array} {c}n-1 \\ k-1\end{array} \right]. \)
Dowód
Niech \( x \) będzie wyróżnionym i ustalonym elementem \( n \)-elementowego zbioru \( X \). Permutacje zbioru \( X \) o \( k \) cyklach można podzielić na dwa typy, w których:
W pierwszym przypadku pozostałe \( n-1 \) elementów zbioru \( X \) muszą uformować \( k-1 \) cykli, co jest możliwe na \( \left[\begin{array} {c}n-1 \\ k-1\end{array} \right] \) sposobów. W drugim przypadku, po usunięciu elementu \( x \) permutacje badanego typu wciąż będą mieć \( k \) cykli. Jest ich zatem tyle, co permutacji \( (n-1) \)-elementowego zbioru o \( k \) cyklach, czyli \(\left [\begin{array} {c}n-1 \\ k\end{array} \right] \). Element \( x \) może rozbudować każdą permutację zbioru \( X-{\{ {x} \} }n-1 \) sposobów (wchodząc do cyklu jako następnik jednego z \( n-1 \) elementów). Zatem permutacji drugiego typu jest dokładnie \( (n-1) \left[\begin{array} {c}n-1 \\ k\end{array} \right] \).
W Trójkącie Stirlinga dla cykli, \( n \)-ty wiersz zawiera liczby permutacji zbioru \( n \)-elementowego o kolejno \( 0,1,\ldots,n \) cyklach. Zatem suma wszystkich tych wartości to liczba wszystkich permutacji zbioru \( n \)-elementowego, czyli \( n! \). Dostajemy stąd natychmiast:
Obserwacja 6.12
Dla \( n\in\mathbb{N} \)
\( \displaystyle\sum_{i=0}^n\left[\begin{array} {c}n \\ i\end{array} \right]=n! \)
Ciekawy jest nastepujacy związek liczb Stirlinga dla cykli z liczbami harmonicznymi \( H_n \).
Obserwacja 6.13
Dla \( n\in\mathbb{N} \)
\( \displaystyle \sum_{i=0}^ni\left[\begin{array} {c}n \\ i\end{array} \right]=n!H_n. \)
Dowód
Dla \( n=0 \) tożsamość jest oczywista, a dla \( n>0 \) przybiera postać \( \displaystyle \sum_{i=1}^ni\left[\begin{array} {c}n \\ i\end{array} \right]=n!H_n \) Pokażemy że obydwie liczby z naszej obserwacji to sumaryczna liczba cykli we wszystkich permutacjach zbioru \( n \)-elementowego, tzn. \( \displaystyle \sum_{\sigma\in S_n} c(\sigma) \).
czyli \( n\cdot(n-1\cdot\ldots\cdot(n-i+1))=n^{\underline{i}} \). Zatem zliczanych cykli \( i \)-elementowych jest dokładnie \( \frac{n^{\underline{i}}}{i} \) .
Każdy cykl \( i \)-elementowy występuje w dokładnie \( (n-i)! \) permutacjach zbioru \( n \)-elementowego, gdyż tyle jest permutacji pozostałych \( n-i \) elementów. Zatem sumaryczna liczba cykli we wszystkich permutacjach zbioru \( n \)-elementowego wynosi:
\( \displaystyle \sum_{\sigma\in S_n} c(\sigma) =\sum_{i=1}^n\frac{n^{\underline{i}}}{i}(n-i)! =\sum_{i=1}^n\frac{n!}{i}=n!H_n. \)
W liczbach Stirlinga \( \left[\begin{array} {c}n \\ k\end{array} \right] \) dla cykli wypełnialiśmy wzorce postaci:
\( \underbrace{(\bullet,\ldots,\bullet)(\bullet,\ldots,\bullet) \ldots (\bullet,\ldots,\bullet)}_{k \ cykli, \ w \ sumie \ o \ n \ miejscach} \)
w sposób injektywny i z dokładnością do:
Jeśli zupełnie zaniedbamy kolejność elementów w cyklach, dostaniemy wzorzec:
\( \underbrace{{\{ {\bullet,\ldots,\bullet} \} }{\{ {\bullet,\ldots,\bullet} \} } \ldots {\{ {\bullet,\ldots,\bullet} \} }}_{k \ zbiorów, \ w \ sumie \ o \ n \ miejscach}, \)
czyli podział zbioru \( n \)-elementowego na \( k \) parami rozłącznych podzbiorów. W podziale, podzbiory takie nazywamy blokami. Przypomnijmy, że podział zbioru \( X \) na \( k \) bloków wyznacza relację równoważności na zbiorze \( X \) o \( k \) klasach równoważności.
Liczba Stirlinga dla podziałów \( \left\{\begin{array} {c}n \\ k\end{array} \right\} \) (często nazywana liczbą Stirlinga drugiego rodzaju) to liczba podziałów zbioru \( n \)-elementowego na dokładnie \( k \) bloki. Znów przyjmujemy, że \( \left\{\begin{array} {c}0 \\ 0\end{array} \right\}=1 \) oraz \( \left\{\begin{array} {c}n \\ k\end{array} \right\}=0 \) dla \( k < 0 \).
Przykład
Lista podziałów \( \mathbb{Z}_4 \) na dwa bloki:
\( \begin{array} {cc} \{0,1,2\}\{3\} & \{0,1 \}\{2,3\} \\ \{0,1,3\}\{2 \} & \{0,2 \} \{1,3 \} \\ \{0,2,3 \}\{1\} & \{0,3\}\{1,2\} \\ \{1,2,3\} \{ 0 \} \end{array} \)
zatem \( \left\{\begin{array} {c}4 \\ 2\end{array} \right\}=7 \).
Obserwacja 6.14
Dla \( n,k\in\mathbb{N} \)
Dowód
Pierwszy punkt jest oczywisty po zauważeniu, że w liczbach Stirlinga dla podziałów zliczamy te same obiekty co w liczbach Stirlinga dla cykli, ale po zaniedbaniu kolejności elementów.
Drugi punkt to stwierdzenie, że niepusty zbiór nie może zostać podzielony na \( 0 \) bloków.
Trzeci punkt orzeka, że jest tylko jeden podział niepustego zbioru na jeden blok - blok ten musi być całym dzielonym zbiorem.
Dla dowodu czwartego załóżmy, że \( \vert X\vert=n \) i niech \( x\in X \). Zauważmy, że podział na dwa bloki jest zdeterminowany jednym z tych bloków - drugi to po prostu dopełnienie pierwszego. Niech więc blokiem determinującym podział, będzie blok zawierający \( x \). Element \( x \) może stanowić blok z dowolnym podzbiorem pozostałego \( (n-1) \)-elementowego zbioru \( X-{\{ {x} \} } \) poza podzbiorem pełnym, gdyż wtedy drugi blok byłby pusty. Zatem jest dokładnie \( 2^{n-1}-1 \) możliwości wyboru bloku dla \( x \), i tym samym tyleż jest podziałów \( X \).
Dowody pozostałych trzech własności można przeprowadzić jak dla liczb Stirlinga dla cykli.
Liczby Stirlinga dla podziałów, podobnie jak współczynniki dwumianowe, czy liczby Stirlinga dla cykli można generować używając zależności rekurencyjnej. Na jej podstawie można zbudować Trójkąt Stirlinga dla podziałów.
Obserwacja 6.15
Dla \( 0 < k\leq n \)
\( \left\{\begin{array} {c}n \\ k\end{array}\right \} =k\left\{\begin{array} {c}n-1 \\ k\end{array}\right \}+\left\{\begin{array} {c}n-1 \\ k-1\end{array} \right\}. \)
Dowód
Niech, jak zwykle, \( \vert X\vert=n \) i niech \( x\in X \) będzie ustalonym elementem. Znów, podziały zbioru \( X \) na \( k \) bloków można podzielić na dwa typy:
Każdy podział pierwszego typu jest jednoznacznie wyznaczony przez \( (n-1) \)-elementowego zbioru \( X-{\{ {x} \} } \) na \( k-1 \) bloków. Jest ich więc dokładnie \( \left\{\begin{array} {c}n-1 \\ k-1\end{array} \right\} \). W drugim przypadku pozostałe elementy dzielone są wciąż na \( k \) bloków. Można taki podział wykonać na \( \left\{\begin{array} {c}n-1 \\ k\end{array} \right\} \) sposobów. Element \( x \) może rozszerzyć każdy taki podział zbioru math>X</math> do podziału zbioru \( X \) na \( k \) sposobów wchodząc do któregoś z \( k \) bloków. Zatem jest dokładnie \( k\left\{\begin{array} {c}n-1 \\ k\end{array} \right\} \) podziałów drugiego typu.
Obserwacja 6.15 pozwala na szybką konstrukcję Trójkąta Stirlinga dla podziałów.
Kilka wykładów wcześniej wskazaliśmy liczbę funkcji, liczbę injekcji i liczbę bijekcji między zbiorami skończonymi. Przemilczeliśmy liczbę surjekcji, nie mając jeszcze wtedy wystarczających narzędzi do ich zliczenia. Zauważmy jednak, że każda surjekcja \( X \longrightarrow Y \) wyznacza podział zbioru \( X \) na \( \vert Y\vert \) bloków. Nie dziwi więc następujący związek z liczbami Stirlinga dla podziałów.
Obserwacja 6.16
Dla skończonych zbiorów \( X,Y \) liczba surjekcji \( X\longrightarrow Y \) wynosi \( \vert Y\vert!\cdot\left\{\begin{array} {c}\vert X\vert \\ \vert Y\vert\end{array} \right\} \).
Dowód
Niech \( Y={\{ {y_0,\ldots,y_{m-1}} \} } \). Jak już zauważyliśmy, surjekcja postaci \( f:X \longrightarrow Y \) wyznacza pewien podział zbioru \( X \) dodatkowo poetykietowany elementami zbioru \( X \) na \( m=\vert Y\vert \) bloków \( f^{-1}({\{ {y_0} \} }), \ldots, f^{-1}({\{ {y_{m-1}} \} }) \). Nieetykietowanych podziałów jest oczywiście \( \left\{\begin{array} {c}\vert X\vert \\ \vert Y\vert\end{array} \right\} \). Ponieważ każdy podział może być poetykietowany na \( \vert Y\vert! \) sposobów, możemy zakończyć dowód.
Obserwacja 6.17
Dla \( n,k\in\mathbb{N} \)
\( \displaystyle \left\{\begin{array} {c}n \\ k+1\end{array} \right\}=\frac{1}{(k+1)!}\sum_{0 < i_0 < \ldots < i_{k-1} < n}{n\choose i_{k-1}}{i_{k-1}\choose i_{k-2}}\ldots{i_1\choose i_0}. \)
Dowód
Niech \( \vert X\vert=n \). Pojedynczy składnik \( {n\choose i_{k-1}}{i_{k-1}\choose i_{k-2}}\ldots{i_1\choose i_0} \) rozważanej sumy to liczba wyborów ciągu zbiorów \( X ⊋
A_{k-1} ⊋ \ldots ⊋ A_1 ⊋ A_{0} \), odpowiednio \( i_{k-1}>\ldots>i_1>i_0 \) elementowych. Rzeczywiście \( A_{i_{k-1}}⊊
X \) możemy wybrać na \( {n\choose i_{k-1}} \) sposobów, \( A_{i_k-2} ⊊
A_{i_k-1} \) na \( {i_{k-1}}\choose i_{k-2} \) sposobów itd. Każdy taki ciąg zbiorów odpowiada jednoznacznie ciągowi \( k+1 \) bloków \( \langle B_0,\ldots,B_k \rangle \), gdzie \( B_0=A_0, B_1=A_1-A_0,\ldots,B_{k-1}=A_{k-1}-A_{k-2},B_k=X-A_{k-1} \). W podziale nie jest jednak istotne uporządkowanie bloków \( B_0,\ldots,B_k \), co oznacza, że powinniśmy przejść od ciągu \( \langle B_0,\ldots,B_k \rangle \) do rodziny bloków \( {\{ {B_0,\ldots,B_k} \} } \), wydzielając tym samym każdy składnik sumy przez \( (k+1)! \). Tak wydzielona suma to nic innego jak liczba podziałów zbioru \( n \)-elementowego na \( k+1 \) bloków, czyli \( \left\{\begin{array} {c}n \\ k+1\end{array}\right \} \).
Przykład
\( \begin{align*} \left\{\begin{array} {c}n \\ 3\end{array} \right\} & =\frac{1}{3!}\sum_{0 < j < i < n}{n\choose i}{i\choose j} =\frac{1}{6}\sum_{0 < i < n}{n\choose i}\sum_{0 < j < i}{i\choose j} \\ & =\frac{1}{6}\sum_{0 < i < n}{n\choose i}(2^i-2) =\frac{1}{6}\sum_{0 < i < n}{n\choose i}2^i-\frac{1}{3}\sum_{0 < i < n}{n\choose i} \\ & =\frac{1}{6}(3^n-1-2^n)-\frac{1}{3}(2^n-2) =\frac{3^{n-1}+1}{2}-2^{n-1} \end{align*} \)
W Trójkącie Pascala \( n \)-ty wiersz sumuje się do
liczby podzbiorów zbioru \( n \)-elementowego, czyli do \( 2^n \). W Trójkąta Stirlinga dla cykli \( n \)-ty wiersz sumuje się do liczby permutacji zbioru \( n \)-elementowego, czyli do \( n! \). Zajmiemy się teraz sumą \( n \)-tego wiersza Trójkąta Stirlinga dla podziałów. Oczywiście suma taka to liczba wszystkich podziałów zbioru \( n \) elementowego, lub inaczej liczby wszystkich relacji równoważności na zbiorze \( n \)-elementowym.
Liczba Bella \( B_n \)
to liczba podziałów zbioru \( n \)-elementowego, czyli
\( \displaystyle B_n=\sum_{i=0}^n\left\{\begin{array} {c}n \\ i\end{array} \right\}. \)
Lista kilku pierwszych liczb Bella:
\( \begin{array} {|c||c|c|c|c|c|c|c|c|c|c|c|c} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \ldots \\ \hline B_n & 1 & 1 & 2 & 5 & 15 & 52 & 203 & 877 & 4140 & 21147 & 115975 & \ldots \\ \hline \end{array} \)
Liczby Bella spełniają piękną zależność rekurencyjną:
Obserwacja 6.18
\( \displaystyle B_{n+1}=\sum_{i=0}^n{n\choose i}B_i. \)
Dowód
Wybierzmy i ustalmy w \( (n+1) \)-elementowym zbiorze \( X \) pewien element \( x\in X \). Policzmy teraz ile jest podziałów zbioru \( X \) takich, że blok zawierający \( x \) ma dokładnie \( i+1 \) elementów. Oczywiście pozostałe \( i \) elementów tego bloku może zostać wybranych ze zbioru \( X-{x} \) na \( {n\choose i} \) sposobów. Każdy taki blok możemy rozbudować do podziału zbioru \( X \) poprzez podzielenie pozostałych \( n-i \) na bloki. Podział taki jest oczywiście możliwy na \( B_{n-i} \) sposobów, skąd sumując po wszystkich możliwych wartościach \( i \) otrzymujemy
\( \displaystyle B_{n+1}=\sum_{i=0}^n{n\choose i}B_{n-i}=\sum_{i=0}^n{n\choose i}B_i. \)
Przestrzeń wektorowa \( \mathbb{R}[x] \) wszystkich wielomianów jednej zmiennej rzeczywistej \( x \) ma naturalną bazę złożoną z jednomianów
\( 1,x,x^2,x^3,\ldots \)
W różnicowym odpowiedniku Twierdzenia Taylora widzieliśmy (bez dowodu), że każdy wielomian \( p(x) \) można przedstawić jako kombinację liniową \( \displaystyle p(x)=\sum_{i=0}^k\frac{(\Delta^i p)(0)}{i!}x^{\underline{i}} \) dolnych silni \( x^{\underline{i}} \). Pokażemy teraz, że rzeczywiście zarówno dolne silnie
\( 1,x^{\underline{1}},x^{\underline{2}},x^{\underline{3}},\ldots \)
jak i górne silnie
\( 1,x^{\overline{1}},x^{\overline{2}},x^{\overline{3}},\ldots \)
stanowią bazy dla przestrzeni wielomianów \( \mathbb{R}[x] \), oraz że współczynniki przejścia między tymi trzeba bazami są ściśle powiązane z liczbami Stirlinga.
W dalszych rozważaniach rezygnujemy z ograniczeń na indeksy sumowania. Zakładamy jedynie, że przebiegają one liczby całkowite pamiętając, że \( \left[\begin{array} {c}n \\ k\end{array}\right ] \) i \( \left\{\begin{array} {c}n \\ k\end{array} \right\} \) zerują się dla \( k < 0 \) oraz \( k>n \).
Obserwacja 6.19
Dla \( x\in\mathbb{R} \) oraz \( n\in\mathbb{N} \)
\( \displaystyle x^{\overline{n}}=\sum_i\left[\begin{array} {c}n \\ i\end{array} \right]x^i. \)
Dowód
Dla dowodu indukcyjnego zauważmy najpierw, że przy \( n=0 \) mamy \( x^{\overline{0}}=1=\left[\begin{array} {c}0 \\ 0\end{array} \right] \). W kroku indukcyjnym korzystamy tym razem z faktu, że \( x^{\overline{n}}=x\cdot x^{\overline{n-1}}+(n-1)x^{\overline{n-1}} \), dostając
\( \begin{align*} x^{\overline{n}} & =x\sum_i\left[\begin{array} {c}n-1 \\ i\end{array} \right]x^i+(n-1)\sum_i\left[\begin{array} {c}n-1 \\ i\end{array} \right]x^i \\ & =\sum_i\left[\begin{array} {c}n-1 \\ i-1\end{array} \right]x^i+\sum_i(n-1)\left[\begin{array} {c}n-1 \\ i\end{array} \right]x^i \\ & =\sum_i\left(\left[\begin{array} {c}n-1 \\ i-1\end{array} \right]+(n-1)\left[\begin{array} {c}n-1 \\ i\end{array} \right]\right)x^i \\ & =\sum_i\left[\begin{array} {c}n \\ i\end{array} \right]x^i. \end{align*} \)
Obserwacja 6.20
Dla \( x\in\mathbb{R} \) oraz \( n\in\mathbb{N} \)
\( \displaystyle x^n=\sum_i\left\{\begin{array} {c}n \\ i \end{array} \right\} x^\underline{i}. \)
Dowód
Zaprezentujemy dwa dowody. Pierwszy - indukcyjny - pracuje dla dowolnego \( x\in\mathbb{R} \), a drugi - kombinatoryczny - w oczywisty sposób jedynie dla \( x\in\mathbb{N} \).
Dla dowodu indukcyjnego zauważmy najpierw, że przy \( n=0 \) mamy \( x^0=1=\left\{\begin{array} {c}0 \\ 0\end{array} \right\} \). W kroku indukcyjnym korzystamy z faktu, że \( x\cdot x^{\underline{i}}=x^{\underline{i+1}}+ix^{\underline{i}} \) dostając:
\( \begin{align*} x^n=x\cdot x^{n-1} & =x\sum_i \left\{\begin{array} {c}n-1 \\ i\end{array} \right\}x^{\underline{i}} \\ & =\sum_i \left\{\begin{array} {c}n-1 \\ i\end{array} \right\}\left(x^{\underline{i+1}}+ix^{\underline{i}}\right) \\ & =\sum_i \left\{\begin{array} {c}n-1 \\ i-1\end{array} \right\}x^{\underline{i}}+\sum_i \left\{\begin{array} {c}n-1 \\ i\end{array} \right\}ix^{\underline{i}} \\ & =\sum_i \left(i\left\{\begin{array} {c}n-1 \\ i\end{array} \right\}+\left\{\begin{array} {c}n-1 \\ i-1\end{array} \right\}\right)x^{\underline{i}}. \end{align*} \)
Dla dowodu kombinatorycznego załóżmy, że \( x\in\mathbb{N}-{\{ {0} \} } \) i niech \( X \) będzie zbiorem \( x \)-elementowym. Oczywiście \( x^n \) to liczba funkcji postaci \( \mathbb{Z}_n \longrightarrow X \). Każda taka funkcja przyjmuje \( i=1,2,\ldots,x \) wartości. Policzmy więc ile funkcji \( \mathbb{Z}_n \longrightarrow X \) przyjmuje dokładnie \( i \) wartości. Ciąg \( i \) różnych wartości ze zbioru \( x \)-elementowego można wybrać na \( x(x-1)\cdot\ldots\cdot(x-i+1)=x^{\underline{i}} \) sposobów. Z każdym takim \( i \)-elementowym ciągiem możemy stowarzyszyć jakiś podział zbioru \( \mathbb{Z}_n \) na \( i \) bloków, tzn. kolejnym blokom tego podziału (uporządkowanym najpierw według najmniejszych elementów w blokach) przyporządkowujemy \( i \)-tą wartość wybranego ciągu. Tym sposobem mamy \( \left\{\begin{array} {c}n \\ i\end{array} \right\}n^{\underline{i}} \) funkcji \( \mathbb{Z}_n \longrightarrow X \) przyjmujących dokładnie \( i \) wartości. Sumując po wszystkich możliwych \( i \) otrzymujemy żądaną równość.
Wskazaliśmy współczynniki przejścia z bazy górnych silni w jednomiany oraz z jednomianów w dolne silnie. Nierówności
\( x^{\underline{n}} < x^n < x^{\overline{n}} \)
zachodzące dla \( x>n>1 \), sugerują, że niektóre współczynniki przejścia z górnych silni do jednomianów oraz z jednomianów do dolnych silni muszą być ujemne. Wskazując te współczynniki wykorzystamy prosty fakt:
\( \begin{align*} (-x)^{\overline{n}} & =(-x)(-x+1)\cdot\ldots\cdot(-x+n-1) \\ & =(-1)^nx(x-1)(x-2)\cdot\ldots\cdot(x-n+1) \\ & =(-1)^nx^{\underline{n}}. \end{align*} \)
Obserwacja 6.21
Dla \( x\in\mathbb{R} \) oraz \( n\in\mathbb{N} \)
\( \begin{align*} x^n & =\sum_i\left\{\begin{array} {c}n \\ i\end{array} \right\}(-1)^{n-i}x^{\overline{i}}, \\ x^{\underline{n}} & =\sum_i\left[\begin{array} {c}n \\ i\end{array} \right](-1)^{n-i}x^i. \end{align*} \)
Dowód
Udowodnimy jedynie pierwszą równość, pozostawiając analogiczny dowód dla drugiej jako ćwiczenie.
\( \begin{align*} x^n=(-1)^n(-x)^n & =(-1)^n\sum_i\left\{\begin{array} {c}n \\ i\end{array} \right\}(-x)^{\underline{i}} \\ & =(-1)^n\sum_i\left\{\begin{array} {c}n \\ i\end{array} \right\}(-1)^ix^{\overline{i}} \\ & =\sum_i\left\{\begin{array} {c}n \\ i\end{array} \right\}(-1)^{n-i}x^{\overline{i}}. \end{align*} \)
Używając trzech powyższych obserwacji zauważmy, że przechodząc od jednomianów do górnych silni i z powrotem, a także niezależnie, od jednomianów do dolnych silni i z powrotem, otrzymujemy następujące zależności:
Obserwacja 6.22
Dla \( m,n\in\mathbb{N} \)
\( \begin{align*} \sum_i (-1)^{m-i}\left\{\begin{array} {c}m \\ i\end{array} \right\}\left[\begin{array} {c}i \\ n\end{array} \right] & = \left\{ \begin{array} {ll} 0, & \mbox {dla} & m\neq n, \\ 1, & \mbox {dla} & m=n, \end{array} \right.\ \\ \sum_i (-1)^{m-i}\left[\begin{array} {c}m \\ i\end{array} \right]\left\{\begin{array} {c}i \\ n\end{array}\right\} & = \left\{ \begin{array} {ll} 0, & \mbox {dla} & m\neq n, \\ 1, & \mbox {dla} & m= n. \end{array} \right . \end{align*} \)
Rozważaliśmy wiele różnych sposobów podziału obiektów na różne kategorie. Czasem kolejność kategorii odgrywała rolę, a czasem nie. Czasem kolejność obiektów danej kategorii odgrywała rolę, a czasem nie. Interesowała nas zawsze liczba konfiguracji podziałowych powstałych w wyniku takich podziałów obiektów na kategorie. Liczba ta zależy oczywiście od tego czy obiekty, bądź kategorie, są rozróżnialne.
Obiekty są rozróżnialne jeśli zamiana miejscami dwu obiektów z różnych kategorii daje nową konfigurację.
Kategorie są rozróżnialne jeśli wzajemna wymiana wszystkich obiektów między dwiema kategoriami prowadzi do nowej konfiguracji.
Zobaczymy, że im mniej rozróżnialności, tym zliczanie staje się trudniejsze.
Często poza całkowitą liczbą konfiguracji istotna jest także liczba konfiguracji z wyłącznie niepustymi kategoriami. Gdy więc \( n \) obiektów klasyfikujemy w \( k \) kategorii pytamy o liczbę konfiguracji (klasyfikacji) o co najwyżej \( k \) kategoriach oraz o dokładnie \( k \) kategoriach.
Większość wariantów klasyfikacji \( n \) obiektów na \( k \) kategorii już przeanalizowaliśmy. Podsumujmy zatem:
Klasyfikacja rozróżnialnych obiektów na rozróżnialne kategorie to po prostu funkcja ze zbioru obiektów w zbiór kategorii. Liczba funkcji ze zbioru \( n \)-elementowego w zbiór \( k \)-elementowy wynosi \( k^n \).
Klasyfikacja na dokładnie \( k \) kategorie to funkcja surjektywna. Zgodnie z Obserwacją 6.16, liczba takich klasyfikacji to, \( k!\left\{\begin{array} {c}n \\ k\end{array}\right\} \).
Nierozróżnialność kategorii oznacza, że nie jest ważna nazwa kategorii (tzn. wartość funkcji dla danego obiektu), a jedynie jej zawartość. Mamy więc do czynienia z podziałem zbioru obiektów na co najwyżej \( k \) bloków. Liczba takich konfiguracji to suma liczb Stirlinga dla podziałów \( \displaystyle \sum_{i=1}^{k}\left\{\begin{array} {c}n \\ i\end{array}\right \} \).
Oczywiście gdy wszystkie kategorie są niepuste, to zbiór obiektów jest podzielony na dokładnie \( k \) bloków. Liczba takich konfiguracji to \( \left\{\begin{array} {c}n \\ k\end{array}\right \} \).
Nierozróżnialność obiektów skutkuje tym, że ważna jest jedynie ich liczba w danej kategorii. A zatem konfiguracja to podział liczby \( n \) na sumę \( n=x_0+\ldots+x_{k-1} \) liczb naturalnych \( x_i \). Liczba rozwiązań takiego równania została policzona w jednym z przykładów wykładu o współczynnikach dwumianowych i wynosi \( {n+k-1\choose k-1} \).
I znów, gdy kategorii, czyli składników w rozkładzie \( n=x_0+\ldots+x_{k-1} \), ma być dokładnie \( k \), zliczamy jedynie rozwiązania spełniające dodatkowo \( x_0,\ldots,x_{k-1}\geq 1 \). Zgodnie z innym przykładem analizowanym w wykładzie o współczynnikach dwumianowych liczba takich rozwiązań to \( {n-1\choose k-1} \).
To jedyny jeszcze nie analizowany przez nas przypadek. Załóżmy najpierw, że wszystkie kategorie są niepuste. Ponieważ są one nierozróżnialne, możemy dodatkowo założyć, że w rozkładzie liczby \( n \) na sumę \( n=x_0+\ldots+x_{k-1} \) zachodzi \( x_0\leq x_1 \leq \ldots \leq x_{k-1} \). Liczba \( P(n,k) \) takich rozkładów będzie przedmiotem ostatniej części wykładu. Jednak już teraz możemy powiedzieć, że nie jest znana żadna zwarta postać tych liczb. Co więcej, nawet aby otrzymać ciekawe zależności rekurencyjne dla liczb podziałów, potrzebne jest nowe, silne narzędzie: funkcje tworzące.
Oczywiście, gdy dopuszczamy puste kategorie liczba konfiguracji jest sumą \( \displaystyle \sum_{i=1}^k P(n,k) \).