Matematyka dyskretna 1/Wykład 6: Permutacje i podziały

Permutacje

Rozważając permutacje zbiorów $n$-elementowych wystarczy ograniczyć się do permutacji zbioru $\mathbb {Z} _{n}$. Każdy inny taki zbiór różni się bowiem od $\mathbb {Z} _{n}$ jedynie nazwami elementów.

Poznaliśmy już algorytm rozkładu permutacji na rozłączne cykle. Przystąpmy do klasyfikacji permutacji względem struktury takiego rozkładu. Przypomnijmy, że rozkład permutacji na cykle jest jednoznaczny z dokładnością do kolejności, tzn. jeśli $\sigma _{1}\circ \ldots \circ \sigma _{k}=\pi _{1}\circ \ldots \circ \pi _{l}$ są dwoma rozkładami tej samej permutacji na cykle to $k=l$ i ${\left\{{\sigma _{1},\ldots ,\sigma _{k}}\right\}\ }={\left\{{\pi _{1},\ldots ,\pi _{k}}\right\}\ }$.

Pierwszym ważnym niezmiennikiem dla permutacji $\pi \in S_{n}$ jest:

Liczba cykli permutacji $\pi \in S_{n}$ zdefiniowana jako liczba cykli w jamimkolwiek rozkładzie $\pi$ na cykle.

Jednoznaczność rozkładu na cykle pozwala nam zdefiniować również drugi ważny niezmiennik.

Typ permutacji $\pi \in S_{n}$ to wektor $(\alpha _{1},\ldots ,\alpha _{n})$, gdzie $\alpha _{i}$ jest liczbą $i$-elementowych cykli w rozkładzie $\pi$. Zazwyczaj typ permutacji zapisujemy jako $[1^{\alpha _{1}}2^{\alpha _{2}}\ldots n^{\alpha _{n}}]$, przy czym często pomijamy te wartości, dla których $\alpha _{i}=0$.

Przykład

Dla permutacji $\pi \in S_{7}$ zadanej przez

${\begin{array}{c|c|c|c|c|c|c|c}n&0&1&2&3&4&5&6\\\hline \pi (n)&3&6&2&4&0&5&1\end{array}}$

mamy:

• $\pi =(0,3,4)(1,6)(2)(4)=(0,3,4)(1,6)$,

• $\pi$ jest typu $[1^{2}2^{1}3^{1}]$.

Z samej definicji typu permutacji natychmiast wynika:

Obserwacja

Dla $\pi \in S_{n}$ typu $(\alpha _{1},\ldots ,\alpha _{n})$ zachodzi

• $\alpha _{1}+\ldots +\alpha _{n}=c(\pi )$,

• $\alpha _{1}+2\alpha _{2}+\ldots +n\alpha _{n}=n$.

Obserwacja

Liczba permutacji w $S_{n}$ typu $(\alpha _{1},\ldots ,\alpha _{n})$ to

${\frac {n!}{1^{\alpha _{1}}2^{\alpha _{2}}\ldots n^{\alpha _{n}}\alpha _{1}!\ldots \alpha _{n}!}}.$

Dowód

Potraktujmy permutację typu $(\alpha _{1},\ldots ,\alpha _{n})$, jako uzupełnienie elementami z $\mathbb {Z} _{n}$ następującego wzorca:

$\underbrace {(\bullet )\ldots (\bullet )} _{\alpha _{1}\ razy}\underbrace {(\bullet \bullet )\ldots (\bullet \bullet )} _{\alpha _{2}\ razy}\ldots \ldots \underbrace {(\bullet \ldots \bullet )} _{\alpha _{n}\ razy\ (\alpha _{n}\leq 1)}.$

W miejsce $k$ kropek możemy wstawić $k$-elementów na $k!$ sposobów. Jednak w ten sposób otrzymamy wielokrotnie te same permutacje. Każdy cykl $i$-elementowy możemy zadać na $i$ sposobów (rozpoczynając od różnych elementów). Dodatkowo, zwróćmy uwagę, że w naszym wzorcu dopuszczamy różną kolejność cykli o tej samej długości. $\alpha _{i}$ takich samych cykli $i$-elementowych może być wybranych na $\alpha _{i}!$ sposobów. Podsumowując, aby otrzymać liczbę permutacji typu $(\alpha _{1},\ldots ,\alpha _{n})$ musimy, dla wszystkich $i\in {\left\{{1,\ldots ,n}\right\}\ }$, podzielić $n!$ przez długość każdego cyklu z osobna, tzn. dla każdego cyklu długości $i$ podzielić przez $i$, oraz przez silnię liczby $i$-elementowych cykli. Zatem szukana liczba to ${\frac {n!}{1^{\alpha _{1}}2^{\alpha _{2}}\ldots n^{\alpha _{n}}\alpha _{1}!\ldots \alpha _{n}!}}$.

Przykład

Lista typów wszystkich permutacji z $S_{3}$:

${\begin{array}{|c|c|c|c|c|c|}\hline n&0&1&2&{\textrm {rozkladnacykle}}&{\textrm {typ}}\\\hline \pi _{0}&0&1&2&(0)(1)(2)&[1^{3}]\\\pi _{1}&1&0&2&(0,1)(2)&[1^{1}2^{1}]\\\pi _{2}&0&2&1&(0)(12)&[1^{1}2^{1}]\\\pi _{3}&1&2&0&(0,1,2)&[3^{1}]\\\pi _{4}&2&0&1&(0,2,1)&[3^{1}]\\\pi _{5}&2&1&0&(0,2)(1)&[1^{1}2^{1}]\\\hline \end{array}}$

Liczba permutacji z $S_{3}$ o kolejnych typach:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array} {|c|l|} \hline \hbox{\rm typ}&\hbox{\rm liczba permutacji}\\ \hline 1^3&\frac{3!}{1^3\cdot3!}=1\\ 1^1 2^1&\frac{3!}{1^1\cdot2^1\cdot1!\cdot1!}=3\\ 3^1&\frac{3!}{3^1\cdot1!}=2\\ \hline \end{array} }

Jak zobaczymy za chwilę, typ permutacji jest zachowywany przez pewną bardzo ważną operację algebraiczną.

Permutacja sprzężona do permutacji $\pi ,\rho \in S_{n}$ to każda permutacja postaci $\sigma \pi \sigma ^{-1}$, gdzie $\sigma \in S_{n}$.

Oczywiście, jeśli $\sigma \pi \sigma ^{-1}=\rho$ to $\pi =\sigma ^{-1}\rho \sigma$. Zatem dwuargumentowa relacja sprzężenia jest symetryczna. Łatwo udowodnić (jako ćwiczenie), że relacja ta jest również zwrotna i przechodnia oraz, że jedyną permutacją sprzeżoną do permutacji identycznościowej $id$ jest ona sama.

Obserwacja

Permutacje $\pi ,\rho \in S_{n}$ mają ten sam typ wtedy i tylko wtedy, gdy są sprzężone.

Dowód

Załóżmy najpierw, że $\pi$ i $\rho$ są sprzężone, czyli że $\sigma \pi \sigma ^{-1}=\rho$ dla pewnego $\sigma$. Rozważmy jakiś cykl $(x_{0},\ldots ,x_{k-1})$ permutacji $\pi$. Wtedy $(\sigma (x_{0}),\ldots ,\sigma (x_{k-1}))$ jest cyklem permutacji $\rho$. Istotnie, dla $i=0,\ldots ,k-1$ mamy:

$\rho (\sigma (x_{i}))=\sigma \pi \sigma ^{-1}\sigma (x_{i})=\sigma \pi (x_{i})=\sigma (x_{i+1}),$

i podobnie:

$\rho (\sigma (x_{k-1})=\sigma \pi \sigma ^{-1}\sigma (x_{k-1})=\sigma \pi (x_{k-1})=\sigma (x_{0}).$

Każdy zatem cykl permutacji $\pi$ wyznacza jednoznacznie cykl permutacji $\rho$ o tej samej liczności. Tym samym $\pi$ i $\rho$ są tego samego typu.

Rysunek: 5.1 Szkic na kartce.

Dla dowodu w drugą stronę załóżmy, że $\pi$ i $\rho$ mają ten sam typ. Wtedy możemy określić bijekcję przyporządkowującą każdemu cyklowi permutacji $\pi$ pewien cykl $\rho$ o tej samej długości. Po rozkładzie obu permutacji $\pi ,\rho$ na rozłączne cykle i nasza bijekcja między cyklami przyporzadkowuje cyklowi $(x_{0},\ldots ,x_{k-1})$ cykl $(y_{0},\ldots ,y_{k-1})$, definiujemy $\sigma \in S_{n}$ kładąc $\sigma (x_{i})=y_{i}$. Łatwo sprawdzić, że wtedy $\sigma \pi \sigma ^{-1}=\rho$.

Transpozycja to permutacja w $S_{n}$ (dla $n\leqslant 2$) typu $[1^{n-2}2^{1}]$. Innymi słowy, transpozycja dokonuje tylko jednego przestawienia dwóch elementów ze zbioru $n$-elementowego.

Przykład

Dla permutacji $\pi \in S_{7}$ zadanej przez

${\begin{array}{|c||c|c|c|c|c|c|c|}\hline n&0&1&2&3&4&5&6\\\hline \pi (n)&0&1&5&3&4&2&6\\\hline \end{array}}$

mamy:

• $\pi =(0)(1)(25)(3)(4)(6)=(25),$

• $\pi$ ma typ $[1^{5}2^{2}]$,

• $\pi$ jest transpozycją.

Waga transpozycji wynika z faktu, że dowolna permutacja jest złożeniem transpozycji. Ponieważ, dowolna permutacja jest rozkładalna na cykle wystarczy pokazać, że każdy cykl jest złożeniem transpozycji.

Obserwacja

Dowolny cykl z $S_{n}$ jest złożeniem $n-1$ transpozycji.

Dowód

Cykl $\pi =(x_{0},\ldots ,x_{n-1})$ można przedstawić tabelką:

${\begin{array}{|c||c|c|c|c|c|c|}\hline n&x_{0}&x_{1}&x_{2}&\ldots &x_{n-2}&x_{n-1}\\\hline \pi (n)&x_{1}&x_{2}&x_{3}&\ldots &x_{n-1}&x_{0}\\\hline \end{array}}$

Zauważmy, że $\pi$ jest następującym złożeniem transpozycji

$(x_{0},x_{n-1})(x_{0},x_{n-2})\ldots (x_{0},x_{2})(x_{0},x_{1}).$

Rzeczywiście $x_{0}$ przejdzie:

• w pierwszej transpozycji $(x_{0},x_{1})$ w $x_{1}$,

• a następne transpozycje już go nie przesuną.

Podobnie $x_{1}$ przejdzie

• pierwszą transpozycją $(x_{0},x_{1})$ w $x_{0}$,

• drugą $(x_{0},x_{2})$ w $x_{2}$,

• a następne transpozycje już go nie przesuną.

Ogólnie, $x_{i}$ (dla $i\in {\left\{{1,\ldots ,n-2}\right\}\ }$)

• pozostanie na swoim miejscu przez pierwsze $i-1$ transpozycji
  

$(x_{0},x_{1}),(x_{0},x_{2}),\ldots ,(x_{0},x_{i-1})$,

• przejdzie $i$-tą transpozycją w $x_{0}$,

• przejdzie $(i+1)$-szą transpozycją w $x_{i+1}$,

• po czym zostanie już nienaruszone.

Natomiast $x_{n-1}$ zostanie przesunięte dopiero ostatnią transpozycją i przyjmie wartość $x_{0}$.

Wniosek

Dowolna permutacja jest złożeniem transpozycji. W szczególności każda permutacja typu $[1^{\alpha _{1}}2^{\alpha _{2}}\ldots n^{\alpha _{n}}]$ ma rozkład na co najwyżej $\alpha _{2}+2\alpha _{3}+\ldots (n-1)\alpha _{n}$ transpozycji.

Przykład

Dla permutacji $\pi \in S_{7}$ zadanej przez

${\begin{array}{|c||c|c|c|c|c|c|c|}\hline n&0&1&2&3&4&5&6\\\hline \pi (n)&2&3&5&4&6&0&1\\\hline \end{array}}$

mamy

• $\pi =(0,2,5)(1,3,4,6)$,

• $(1,3,4,6)=(1,6)(1,4)(1,3)$,

• $(0,2,5)=(0,5)(0,2)$,

• $\pi =(0,5)(0,2)(1,6)(1,4)(1,3)=(1,6)(1,4)(1,3)(0,5)(0,2)$.

Rysunek: 5.2 Szkic na kartce.

Zauważmy, że składanie transpozycji na rozłącznych zbiorach dwuelementowych jest przemienne. Na ogół jednak, ponieważ transpozycje nie działają na zbiorach rozłącznych, to nie możemy ich dowolnie przestawiać. W naszym przykładzie transpozycje generujące dwa różne cykle są parami rozłączne, więc ich kolejność jest bez znaczenia. Między innymi dlatego istnieje wiele rozkładów na transpozycje. Ale nie tylko dlatego -- mamy bowiem również $\pi =(1,6)(2,5)(0,2)(3,6)(0,5)(4,6)(2,5)$.

Nie mamy zatem jednoznaczności rozkładu na transpozycje, tak jak to miało miejsce przy rozkładzie na cykle. Nawet liczba transpozycji nie musi być ta sama w różnych rozkładach na transpozycje. Zobaczymy jednak, że nie zmienia się parzystość liczby transpozycji w rozkładzie.

Obserwacja

Jeśli $\pi ,\tau \in S_{n}$ i $\tau$ jest transpozycją, to

$c(\tau \pi )=c(\pi )\pm 1=c(\pi \tau ).$

Dowód

Udowodnimy tylko pierwszą równość. Załóżmy, że $\tau =(a,b)$ tzn., $\tau (a)=b$, $\tau (b)=a$ i $\tau (x)=x$ dla wszystkich pozostałych elementów $x\in \mathbb {Z} _{n}$. Rozumowanie dzielimy na dwa przypadki:

• $a$ i $b$ są w tym samym cyklu $(a,x,\ldots ,y,b,w,\ldots ,z)$ permutacji $\pi$.

Rysunek: 5.3 Szkic na kartce.

Wtedy $\tau \pi =(a,x,\ldots ,y)(b,w,\ldots ,z)\ldots$, gdzie ostatni wielokropek oznacza pozostałe cykle permutacji $\pi$. Zatem w tym przypadku mamy $c(\tau \pi )=c(\pi )+1$.

• $a$ i $b$ są w różnych cyklach permutacji $\pi =(a,x\ldots ,y)(b,\ldots ,z)\ldots$.

Wtedy $\tau \pi =(a,x,\ldots ,y,b,\ldots ,z)\ldots$. Mamy więc $c(\tau \pi )=c(\pi )-1$.

Obserwacja

Jeśli permutacja jest przedstawialna jako złożenia $r$ i $r'$ transpozycji, to liczby $r$ i $r'$ albo są obie parzyste albo obie nieparzyste.

Dowód

Niech $\tau _{r-1}\ldots \tau _{0}=\tau _{r'-1}'\ldots \tau _{0}'$ będą dwoma rozkładami tej samej permutacji $\pi \in S_{n}$ na transpozycje. Na mocy Obserwacji Uzupelnic obserwacja - zachowanie c po zlozeniu z transpozycja| mamy:

$c(\tau _{r-1}\ldots \tau _{0})=c(\tau _{r-2}\ldots \tau _{0})\pm 1=c(\tau _{r-3}\ldots \tau _{0})\pm 1\pm 1=\ldots =c(\tau _{0})\underbrace {\pm 1\pm 1\ldots \pm 1} _{r-1\ razy}$

Niech $t$ opisuje iloć dodawań jedynki w powyższej formule. Wtedy $r-1-t$ to liczba odejmowań jedynki. Transpozycja $\tau _{0}$ ma $1$ cykl $2$-elementowy i $n-2$ cykli $1$-elementowych, czyli $c(\tau _{0})=1+(n-2)=n-1$. Zatem

$c(\pi )=c(\tau _{r-1}\ldots \tau _{0})=n-1+t-(r-1-t)=n-r+2t$

dla pewnego $t$. Analogicznie

$c(\pi )=c(\tau '_{r'-1}\ldots \tau '_{0})=n-1+t'-(r'-1-t')=n-r'+2t'$

dla pewnego $t'$. Porównując obydwa wyniki otrzymujemy

$r-r'=2a-2a',$

czyli różnica $r-r'$ jest zawsze parzysta.

Obserwacja Uzupelnic obserwacja - jednoznaczna parzystosc permutacji| pozwala zdefiniować parzystość permutacji.

Permutacja parzysta to permutacja będąca złożeniem parzystej liczby transpozycji.

Permutacja nieparzysta to permutacja będąca złożeniem nieparzystej liczby transpozycji.

Znak permutacji $\pi$ to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf sgn}(\pi)=(-1)^r} , gdzie $r$ jest liczbą transpozycji, na które można rozłożyć $\pi$.

Obserwacja

Dla dowolnych $\pi ,\sigma \in S_{n}$

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf sgn}(id_{\mathbb{Z}_n})=1} ,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf sgn}(\sigma\pi)=\mbox{\sf sgn}(\pi)\cdot\mbox{\sf sgn}(\sigma)} ,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf sgn}(\pi)=\mbox{\sf sgn}(\pi^{-1})} ,

Dowód

Identyczność jest złożeniem zera transpozycji. Drugi punkt wynika natychmiast z Obserwacji Uzupelnic obserwacja - zachowanie c po zlozeniu z transpozycja|. Dla dowodu trzeciego odnotujmy tylko, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf sgn}(\pi)\cdot\mbox{\sf sgn}(\pi^{-1}) =\mbox{\sf sgn}(\pi\pi^{-1})=\mbox{\sf sgn}(id_{\mathbb{Z}_n})=1} .

Przykład

Dla relaksu rozważmy łamigłówkę logiczną rozgrywaną na kwadracie $3\times 3$. Wszystkie pola, poza prawym dolnym, wypełnione są kwadratowymi klockami z różnymi literami B,O,R,L,Y,M,E,P. Prawe dolne pole jest puste -- oznaczamy go przez "". Celem gry jest ułożenie napisu "PROBLEMY". Dopuszczalnym ruchem jest przesunięcie klocka sąsiadującego z pustym polem na to właśnie pole. Czy z pozycji "BORLYMEP" można ułożyć napis "PROBLEMY"?

Rysunek: 5.4 Szkic na kartce

Zauważmy, że pozycja startowa i końcowa mają puste pole "" w tym samym miejscu. To oznacza, że wykonując roszadę bloków musimy wykonać tyle samo przesunięć do góry co w dół i tyle samo przesunięć w prawo co w lewo. To z kolei oznacza, że potencjalna ilość ruchów wiodących do rozwiązania musi być parzysta. Tłumacząc nasz problem na język permutacji odnotujmy, że:

• mamy dokonać permutacji $\pi \in S_{9}$:

${\begin{array}{ccccccccc}B&O&R&L&Y&M&E&P&\_\\\downarrow &\downarrow &\downarrow &\downarrow &\downarrow &\downarrow &\downarrow &\downarrow &\downarrow \\P&R&O&B&L&E&M&Y&\_\end{array}}$

• każdy ruch zgodny z regułami gry to jakaś transpozycja wybranych klocków,

przy czym nie wszystkie transpozycje są dopuszczalne.

Zauważmy, że

• rozwiązanie musi być wykonane przy pomocy parzystej liczby ruchów,

zatem każda permutacja dokonująca żądanej rearanżacji klocków jest parzysta

• $\pi =(B,P,Y,L)(O,R)(M,E)(\_)$,

• Wniosek Uzupelnic wniosek - permutacja jest zlozeniem ilus tam transpozycji|

daje wtedy jednak, że $\pi$ jest złożeniem $3+1+1=5$ transpozycji, czyli $\pi$ jest permutacją nieparzystą.

Ponieważ nie można złożyć nieparzystej permutacji z parzystej liczby transpozycji, nasza łamigłówka nie jest możliwa do rozwiązania.

Obserwacja

Dla $n\geqslant 2$ w $S_{n}$ jest dokładnie tyle samo permutacji parzystych co nieparzystych.

Dowód

Niech $n\geqslant 2$ i $\pi _{0},\ldots ,\pi _{k-1}$ będzie listą wszystkich parzystych permutacji w $S_{n}$. Ponadto, rozważmy transpozycję $\tau =(01)(2)\ldots (n)$. Wtedy oczywiście permutacje $\tau \pi _{0},\tau \pi _{1},\ldots ,\tau \pi _{k-1}$ są parami różne, gdyż jeśli $\tau \pi _{i}=\tau \pi _{j}$ to $\pi _{i}=\tau ^{-1}\tau \pi =\tau ^{-1}\tau \pi _{j}=\pi _{j}$. Ponadto dowolna $\tau \pi$ jest nieparzysta, bo Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf sgn}(\tau\pi)=\mbox{\sf sgn}(\tau)\mbox{\sf sgn}(\pi)=(-1)\cdot1=-1. } Pozostaje pokazać, że dowolna nieparzysta permutacja $\rho$ jest na liście $\tau \pi _{0},\tau \pi _{1},\ldots ,\tau \pi _{k-1}$. Ponieważ Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf sgn}(\tau^{-1}\rho)=\mbox{\sf sgn}(\tau^{-1})\mbox{\sf sgn}(\rho)=(-1)\cdot(-1)=1, } to $\tau ^{-1}\rho$ jest permutacją parzystą, a zatem jest postaci $\pi _{i}$ dla pewnego $i$. To zaś oznacza, że

$\rho =\tau \tau ^{-1}\rho =\tau \pi _{i},$

czyli $\rho$ jest na liście $\tau \pi _{0},\tau \pi _{1},\ldots ,\tau \pi _{k-1}$. Uzyskana bijekcja $\pi _{i}\mapsto \tau \pi _{i}$ dowodzi naszej obserwacji.

Podziały

Liczby Stirlinga

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

Rysunek: 5.5 Szkic na kartce.

• Mamy $11$ permutacji $\mathbb {Z} _{4}$ złożonych z dwóch cykli,

zatem $\left[{\begin{array}{c}4\\2\end{array}}\right]=11$.

Obserwacja

Dla $n\in \mathbb {N}$

• $\left[{\begin{array}{c}n\\0\end{array}}\right]=0$, dla $n>0$

• $\left[{\begin{array}{c}n\\1\end{array}}\right]=(n-1)!$,

• $\left[{\begin{array}{c}n\\n-1\end{array}}\right]={n \choose 2}$,

• $\left[{\begin{array}{c}n\\n\end{array}}\right]=1$,

• $\left[{\begin{array}{c}n\\k\end{array}}\right]=0$, dla $k>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 \choose 2}$, 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

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:

• $x$ stanowi jednoelementowy cykl,

• $x$ jest w cyklu co najmniej $2$-elementowym.

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-{\left\{{x}\right\}\ }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]$.

Rysunek: 5.6 Szkic na kartce

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

Dla $n\in \mathbb {N}$

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

Dla $n\in \mathbb {N}$

$\sum _{i=0}^{n}i\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ć $\sum _{i=1}^{n}i\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. $\sum _{\sigma \in S_{n}}c(\sigma )$.

• Permutacji o $i$ cyklach jest dokładnie $\left[{\begin{array}{c}n\\i\end{array}}\right]$.

W sumie permutacje o $i$ cyklach mają więc $i\cdot \left[{\begin{array}{c}n\\i\end{array}}\right]$ cykli, czyli $\sum _{\sigma \in S_{n}}c(\sigma )=\sum _{i=1}^{n}i\left[{\begin{array}{c}n\\i\end{array}}\right]$.

• Zliczymy najpierw $i$-elementowe cykle

zbudowane z elementów zbioru $n$-elementowego. Każdy taki cykl jest wyznaczony przez wypełnienie wzorca $(\underbrace {\bullet ,\ldots ,\bullet } _{i\ pozycji})$, ale z dokładnością do przesunięcia. Wypełnień jest oczywiście tyle, ile injekcji postaci $\mathbb {Z} _{i}\longrightarrow \mathbb {Z} _{n}$, 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:

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

• kolejności cykli,

• przesunięć cyklicznych w każdym z $k$ cykli.

Jeśli zupełnie zaniedbamy kolejność elementów w cyklach, dostaniemy wzorzec:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \underbrace{{\left\{ {\bullet,\ldots,\bullet} \right\}\ }{\left\{ {\bullet,\ldots,\bullet} \right\}\ } \ldots {\left\{ {\bullet,\ldots,\bullet} \right\}\ }}_{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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\{\begin{array} {c}n\\ k\end{array} \right\}\$ (często nazywana liczbą Stirlinga drugiego rodzaju) to liczba podziałów zbioru } nParser nie mógł rozpoznać (błąd składni): {\displaystyle -elementowego na dokładnie } kParser nie mógł rozpoznać (błąd składni): {\displaystyle bloki. Znów przyjmujemy, że } {c}0
0 1$oraz$ {c}n
k 0$dla$k<0Parser nie mógł rozpoznać (błąd składni): {\displaystyle . {{przyklad||| Lista podziałów } {Z}_4$nadwabloki:$ {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} }

Parser nie mógł rozpoznać (nieznana funkcja „\medskip”): {\displaystyle \medskip\noindent\textit{Rysunek:} 5.7 Szkic na kartce.\medskip * Mamy } 7Parser nie mógł rozpoznać (błąd składni): {\displaystyle podziałów zbioru } {Z}_4$nadwabloki,zatem$ {c}4
2 7Parser nie mógł rozpoznać (błąd składni): {\displaystyle . }} {{obserwacja||| Dla } n,k{N}$*$ {c}n
k [ {c}n
k ]$,*$ {c}n
0 0$,dla$n>0$,*$ {c}n
1 1$,dla$n>0$,*$ {c}n
2 2^{n-1}-1$,dla$n>0$,*$ {c}n
n-1 {n}$,*$ {c}n
n 1$,*$ {c}n
k 0$,dla$k>nParser nie mógł rozpoznać (błąd składni): {\displaystyle . }} {{dowod||| 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 } 0Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } =n$iniech$x XParser nie mógł rozpoznać (błąd składni): {\displaystyle . 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$xParser nie mógł rozpoznać (błąd składni): {\displaystyle może stanowić blok z dowolnym podzbiorem pozostałego } (n-1)$-elementowegozbioru$X-{ {x} }Parser nie mógł rozpoznać (błąd składni): {\displaystyle poza podzbiorem pełnym, gdyż wtedy drugi blok byłby pusty. Zatem jest dokładnie } 2^{n-1}-1Parser nie mógł rozpoznać (błąd składni): {\displaystyle możliwości wyboru bloku dla } xParser nie mógł rozpoznać (błąd składni): {\displaystyle , i tym samym tyleż jest podziałów } XParser nie mógł rozpoznać (błąd składni): {\displaystyle . 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||| Dla } 0<k n

{c}n
k

=k {c}n-1
k {c}n-1
k-1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle }} {{dowod||| Niech, jak zwykle, } =n$iniech$x XParser nie mógł rozpoznać (błąd składni): {\displaystyle będzie ustalonym elementem. Znów, podziały zbioru } X$na$kParser nie mógł rozpoznać (błąd składni): {\displaystyle bloków można podzielić na dwa typy: * } { {x} }$stanowiblokjednoelementowy,*$xParser nie mógł rozpoznać (błąd składni): {\displaystyle jest w bloku co najmniej dwuelementowym. Każdy podział pierwszego typu jest jednoznacznie wyznaczony przez } (n-1)$-elementowegozbioru$X-{ {x} }$na$k-1Parser nie mógł rozpoznać (błąd składni): {\displaystyle bloków. Jest ich więc dokładnie } {c}n-1
k-1 .

W drugim przypadku pozostałe elementy dzielone są wciąż na $k$ bloków. Można taki podział wykonać na Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\{\begin{array} {c}n-1\\ k\end{array} \right\}\$ sposobów. Element } xParser nie mógł rozpoznać (błąd składni): {\displaystyle może rozszerzyć każdy taki podział zbioru } XParser nie mógł rozpoznać (błąd składni): {\displaystyle do podziału zbioru } X$na$kParser nie mógł rozpoznać (błąd składni): {\displaystyle sposobów wchodząc do któregoś z } kParser nie mógł rozpoznać (błąd składni): {\displaystyle bloków. Zatem jest dokładnie } k {c}n-1
k podziałów drugiego typu. }}

Obserwacja Uzupelnic obserwacja - rekursja Stirlinga dla podzialow| pozwala na szybką konstrukcję Trójkąta Stirlinga dla podziałów.

Rysunek: Rys. 5.8 Szkic na kartce.

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertY\right\vert} bloków. Nie dziwi więc następujący związek z liczbami Stirlinga dla podziałów.

Obserwacja

Dla skończonych zbiorów $X,Y$ liczba surjekcji $X\longrightarrow Y$

wynosi Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertY\right\vert!\cdot\left\{\begin{array} {c}\left\vertX\right\vert\\ \left\vertY\right\vert\end{array} \right\}\$. }} {{dowod||| Niech } Y={ {y_0,...,y_{m-1

}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Jak już zauważyliśmy, surjekcja postaci } f:X YParser nie mógł rozpoznać (błąd składni): {\displaystyle wyznacza pewien podział zbioru } X$dodatkowopoetykietowanyelementamizbioru$X$na$m=Parser nie mógł rozpoznać (błąd składni): {\displaystyle bloków } f^{-1}({ {y_0} }), ..., f^{-1}({ {y_{m-1}} })Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Nieetykietowanych podziałów jest oczywiście } {c}
.

Ponieważ każdy podział może być poetykietowany na Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertY\right\vert!} sposobów, możemy zakończyć dowód. }}

Obserwacja

Dla $n,k\in \mathbb {N}$

Parser nie mógł rozpoznać (błąd składni): {\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertX\right\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\supsetneq A_{k-1}\supsetneq \ldots \supsetneq A_{1}\supsetneq A_{0}$, odpowiednio $i_{k-1}>\ldots >i_{1}>i_{0}$ elementowych. Rzeczywiście $A_{i_{k-1}}\subsetneq X$ możemy wybrać na ${n \choose i_{k-1}}$ sposobów, $A_{i_{k}-2}\subsetneq 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 $\left\langle B_{0},\ldots ,B_{k}\right\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 $\left\langle B_{0},\ldots ,B_{k}\right\rangle$ do rodziny bloków ${\left\{{B_{0},\ldots ,B_{k}}\right\}\ }$, 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\{\begin{array} {c}n\\ k+1\end{array} \right\}\$. }} {{przyklad||| }

{c}n
3

&=&{1}{3!}_{0<j<i<n}{n i}{i j} ={1}{6}_{0<i<n}{n i}_{0<j<i}{i j}
&=&{1}{6}_{0<i<n}{n i}(2^i-2) ={1}{6}_{0<i<n}{n i}2^i-{1}{3}_{0<i<n}{n i}
&=&{1}{6}(3^n-1-2^n)-{1}{3}(2^n-2) ={3^{n-1}+1}{2}-2^{n-1}

Parser nie mógł rozpoznać (błąd składni): {\displaystyle }} ===Liczby Bella=== W Trójkącie Pascala } nParser nie mógł rozpoznać (błąd składni): {\displaystyle -ty wiersz sumuje się do liczby podzbiorów zbioru } n$-elementowego,czylido$2^nParser nie mógł rozpoznać (błąd składni): {\displaystyle . W Trójkąta Stirlinga dla cykli } nParser nie mógł rozpoznać (błąd składni): {\displaystyle -ty wiersz sumuje się do liczby permutacji zbioru } n$-elementowego,czylido$n!Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Zajmiemy się teraz sumą } nParser nie mógł rozpoznać (błąd składni): {\displaystyle -tego wiersza Trójkąta Stirlinga dla podziałów. Oczywiście suma taka to liczba wszystkich podziałów zbioru } nParser nie mógł rozpoznać (błąd składni): {\displaystyle elementowego, lub inaczej liczby wszystkich relacji równoważności na zbiorze } nParser nie mógł rozpoznać (nieznana funkcja „\noindent”): {\displaystyle -elementowym. \noindent \textbf{\underline{Liczba Bella}} } B_nParser nie mógł rozpoznać (nieznana funkcja „\marginpar”): {\displaystyle \marginpar{{\scriptsize (nazwana na cześć Erica Temple Bella szkockiego matematyka i autora powieści science-fiction), notka, foto}\bigskip\hrule} to liczba podziałów zbioru } n$-elementowego,czyli$

B_n=_{i=0}^n {c}n
i

$ListakilkupierwszychliczbBella:$

{|c||c|c|c|c|c|c|c|c|c|c|c|c}

---

n&0&1&2&3&4&5&6&7&8&9&10&...

---

B_n&1&1&2&5&15&52&203&877&4140&21147&115975&...

---

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Liczby Bella spełniają piękną zależność rekurencyjną: {{obserwacja||| }

B_{n+1}=_{i=0}^n{n i}B_i.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle }} {{dowod||| Wybierzmy i ustalmy w } (n+1)$-elementowymzbiorze$X$pewienelement$x XParser nie mógł rozpoznać (błąd składni): {\displaystyle . Policzmy teraz ile jest podziałów zbioru } XParser nie mógł rozpoznać (błąd składni): {\displaystyle takich, że blok zawierający } xParser nie mógł rozpoznać (błąd składni): {\displaystyle ma dokładnie } i+1Parser nie mógł rozpoznać (błąd składni): {\displaystyle elementów. Oczywiście pozostałe } iParser nie mógł rozpoznać (błąd składni): {\displaystyle elementów tego bloku może zostać wybranych ze zbioru } X-{x}$na${n i}Parser nie mógł rozpoznać (błąd składni): {\displaystyle sposobów. Każdy taki blok możemy rozbudować do podziału zbioru } XParser nie mógł rozpoznać (błąd składni): {\displaystyle poprzez podzielenie pozostałych } n-iParser nie mógł rozpoznać (błąd składni): {\displaystyle na bloki. Podział taki jest oczywiście możliwy na } B_{n-i}Parser nie mógł rozpoznać (błąd składni): {\displaystyle sposobów, skąd sumując po wszystkich możliwych wartościach } i$otrzymujemy$

B_{n+1}=_{i=0}^n{n i}B_{n-i}=_{i=0}^n{n i}B_i.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle }} ===Bazy przestrzeni wielomianów=== Przestrzeń wektorowa } {R}[x]Parser nie mógł rozpoznać (błąd składni): {\displaystyle wszystkich wielomianów jednej zmiennej rzeczywistej } xParser nie mógł rozpoznać (błąd składni): {\displaystyle ma naturalną bazę złożoną z jednomianów }

1,x,x^2,x^3,...

Parser nie mógł rozpoznać (błąd składni): {\displaystyle W \underline{różnicowym odpowiedniku Twierdzenia Taylora} widzieliśmy (bez dowodu), że każdy wielomian } p(x)Parser nie mógł rozpoznać (błąd składni): {\displaystyle można przedstawić jako kombinację liniową } p(x)=_{i=0}^k{(^i p)(0)}{i!}x^{i}$dolnychsilni$x^{i}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Pokażemy teraz, że rzeczywiście zarówno dolne silnie }

1,x^{1},x^{2},x^{3},...

Parser nie mógł rozpoznać (błąd składni): {\displaystyle jak i górne silnie }

1,x^Szablon:1,x^Szablon:2,x^Szablon:3,...

Parser nie mógł rozpoznać (błąd składni): {\displaystyle stanowią bazy dla przestrzeni wielomianów } {R}[x]Parser nie mógł rozpoznać (błąd składni): {\displaystyle , 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 } [ {c}n
k ]$i$ {c}n
k

zerują się dla $k<0$ oraz $k>n$.

Obserwacja

Dla $x\in \mathbb {R}$ oraz $n\in \mathbb {N}$

$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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned 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. \endaligned}

Obserwacja

Dla $x\in \mathbb {R}$ oraz $n\in \mathbb {N}$

Parser nie mógł rozpoznać (nieznana funkcja „\x”): {\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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle x^0=1=\left\{\begin{array} {c}0\\ 0\end{array} \right\}\$. W kroku indukcyjnym korzystamy z faktu, że } x x^{i}=x^{i+1}+ix^{i}Parser nie mógł rozpoznać (błąd składni): {\displaystyle dostając: }

x^n=x x^{n-1}

&=&x_i {c}n-1
i ^{i}

&=&_i {c}n-1
i Parser nie mógł rozpoznać (błąd składni): {\displaystyle x^{\underline{i+1}}+ix^{\underline{i}})\\ &=&\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}}. \endaligned}

Dla dowodu kombinatorycznego załóżmy, że $x\in \mathbb {N} -{\left\{{0}\right\}\ }$ 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 Parser nie mógł rozpoznać (nieznana funkcja „\n”): {\displaystyle \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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned (-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}}. \endaligned}

Obserwacja

Dla $x\in \mathbb {R}$ oraz $n\in \mathbb {N}$

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned x^n&=&\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}} -1)^{n-i}x^Szablon:I,

x^{n}&=&_i[ {c}n
i ](-1)^{n-i}x^i.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle }} {{dowod||| Udowodnimy jedynie pierwszą równość, pozostawiając analogiczny dowód dla drugiej jako ćwiczenie. } x^n=(-1)^n(-x)^n

&=&(-1)^n_i {c}n
i Parser nie mógł rozpoznać (błąd składni): {\displaystyle -x)^{\underline{i}}\\ &=&(-1)^n\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}} -1)^ix^Szablon:I

&=&_i {c}n
i Parser nie mógł rozpoznać (nieznana funkcja „\endaligned”): {\displaystyle -1)^{n-i}x^{\overline{i}}. \endaligned}

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

Dla $m,n\in \mathbb {N}$

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \sum_i (-1)^{m-i}\left\{\begin{array} {c}m\\ i\end{array} \right\}\\fStirlingDlaCykli{i}{n} &=& \left\{ \begin{array} {ll} 0,& \mbox{\rm dla \ } m\neq n, \\ 1,& \mbox{\rm 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{\rm dla \ } m\neq n, \\ 1,& \mbox{\rm dla \ } m= n. \end{array} \right. \endaligned}

Klasyfikacja podziałów

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:

• obiekty rozróżnialne, kategorie rozróżnialne:

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ą Uzupelnic obserwacja - liczba surjekcji|, liczba takich klasyfikacji to, Parser nie mógł rozpoznać (błąd składni): {\displaystyle k!\left\{\begin{array} {c}n\\ k\end{array} \right\}\$. * \textbf{obiekty rozróżnialne, kategorie nierozróżnialne:} 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 } kParser nie mógł rozpoznać (błąd składni): {\displaystyle bloków. Liczba takich konfiguracji to suma liczb Stirlinga dla podziałów } _{i=1}^{k} {c}n
i .

Oczywiście gdy wszystkie kategorie są niepuste, to zbiór obiektów jest podzielony na dokładnie $k$ bloków.

Liczba takich konfiguracji to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\{\begin{array} {c}n\\ k\end{array} \right\}\$. * \textbf{obiekty nierozróżnialne, kategorie rozróżnialne:} Nierozróżnialność obiektów skutkuje tym, że ważna jest jedynie ich liczba w danej kategorii. A zatem konfiguracja to podział liczby } n Parser nie mógł rozpoznać (błąd składni): {\displaystyle na sumę } n=x_0+...+x_{k-1}$liczbnaturalnych$x_iParser nie mógł rozpoznać (błąd składni): {\displaystyle . 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 k-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . I znów, gdy kategorii, czyli składników w rozkładzie } n=x_0+...+x_{k-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle , ma być dokładnie } kParser nie mógł rozpoznać (błąd składni): {\displaystyle , zliczamy jedynie rozwiązania spełniające dodatkowo } x_0,...,x_{k-1} 1Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Zgodnie z innym przykładem analizowanym w wykładzie o współczynnikach dwumianowych liczba takich rozwiązań to } {n-1 k-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . * \textbf{obiekty nierozróżnialne, kategorie nierozróżnialne:} 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 } nParser nie mógł rozpoznać (błąd składni): {\displaystyle na sumę } n=x_0+...+x_{k-1}$zachodzi$x_0 x_1 ... x_{k-1}$.Liczba$P(n,k)Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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ą } _{i=1}^k P(n,k)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . ==Podziały liczby== \textbf{\underline{Podział liczby}} } n$na$kParser nie mógł rozpoznać (błąd składni): {\displaystyle składników to przedstawienie } n$wpostacisumy$a_0+...+a_{k-1}=n,

$gdzie$a_0 a_1 ... a_{k-1} 1Parser nie mógł rozpoznać (nieznana funkcja „\noindent”): {\displaystyle . \noindent \textbf{\underline{Liczbę podziałów}} } n$na$kParser nie mógł rozpoznać (błąd składni): {\displaystyle składników oznaczamy przez } P(n,k)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . {{przyklad||| Lista podziałów } 7$na$4Parser nie mógł rozpoznać (błąd składni): {\displaystyle składniki: }

1+1+1+4, 1+1+2+3, 1+2+2+2.

$*$P(7,4)=3Parser nie mógł rozpoznać (błąd składni): {\displaystyle . }} {{obserwacja||| Dla } n,k{N}-{ {0} }$*$P(n,1)=1$,*$P(n,2)= {n}{2}$,*$P(n,n)=1$,*$P(n,k)=0$,dla$n<k$*${1}{k!}{n-1 k-1} P(n,k){n-1 k-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . }} {{dowod||| Uzasadnimy jedynie ostatni punkt. Dla dowodu ograniczenia górnego liczby } P(n,k)Parser nie mógł rozpoznać (błąd składni): {\displaystyle zauważmy, że interesujące nas podziały liczby } nParser nie mógł rozpoznać (błąd składni): {\displaystyle są rozwiązaniami równania } n=x_0+...+x_{k-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle , a tych, jak już wiemy, jest dokładnie } {n-1 k-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Z drugiej strony dowolny podział liczby } nParser nie mógł rozpoznać (błąd składni): {\displaystyle generuje co najwyżej } k!Parser nie mógł rozpoznać (błąd składni): {\displaystyle rozwiązań równania } n=x_0+...+x_{k-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle (generuje dokładnie } k!Parser nie mógł rozpoznać (błąd składni): {\displaystyle , jeśli składniki podziału są parami różne) i wszystkie rozwiązania mogą zostać w ten sposób osiągnięte. To oczywiście daje ograniczenie dolne. }} Ograniczenie górne dla } P(n,k)Parser nie mógł rozpoznać (błąd składni): {\displaystyle można poprawić: {{obserwacja||| }

P(n,k) {1}{k!}{n+{k}-1 k-1}.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle }} {{dowod||| Dla podziału } n=a_0+...+a_{k-1}$definiujemy$

b_i=a_i+(k-1-i),dla $0\leq i\leq k-1$.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Zauważmy, że wszystkie liczby } b_iParser nie mógł rozpoznać (błąd składni): {\displaystyle są różne oraz }

b_0+...+b_{k-1}=n+{k(k-1)}{2}.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle A zatem podziały liczby } n$na$kParser nie mógł rozpoznać (błąd składni): {\displaystyle składników stoją w bijektywnej odpowiedniości z podziałami liczby } n+{k 2}$na$kParser nie mógł rozpoznać (błąd składni): {\displaystyle parami różnych składników. Każdy podział } n+{k}$na$kParser nie mógł rozpoznać (błąd składni): {\displaystyle parami różnych składników generuje dokładnie } k!Parser nie mógł rozpoznać (błąd składni): {\displaystyle rozwiązań równania }

x_0+...+x_{k-1}=n+{k 2},

$gdzie$x_i>0Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Wiemy zaś, że to ostatnie równanie posiada co najwyżej } {n+{k}-1 k-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle rozwiązań. A zatem ciągów } b_i Parser nie mógł rozpoznać (błąd składni): {\displaystyle , a tym samym podziałów } n$na$kParser nie mógł rozpoznać (błąd składni): {\displaystyle składników, jest co najwyżej } {1}{k!}{n+{k}-1 k-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . }} Ostatnia obserwacja pozwala na opisanie granicznego zachowania liczb } P(n,k)$przyustalonym$kParser nie mógł rozpoznać (błąd składni): {\displaystyle . {{wniosek||| Dla dowolnego } k

_{n}{P(n,k)}{n^{k-1 ={1}{k!(k-1)!}.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle }} Dość skutecznym narzędziem do badania podziałów liczb naturalnych są tzw. diagramy Ferrersa. \noindent \textbf{\underline{Diagram Ferrersa}} dla podziału } n=a_0+...+a_{k-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle składa się z } k$wierszyoodpowiednio$a_{i-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle elementach. {{przyklad||| }

2+5+6+6+9=28.

Parser nie mógł rozpoznać (nieznana funkcja „\medskip”): {\displaystyle \medskip\noindent\textit{Rysunek:} 6.3 Szkic na kartce.\medskip }

1+3+3+3=10.

Parser nie mógł rozpoznać (nieznana funkcja „\medskip”): {\displaystyle \medskip\noindent\textit{Rysunek:} 6.4 Szkic na kartce.\medskip }} Użyteczność diagramów Ferrersa ilustrują dowody kilku nastepnych obserwacji. {{obserwacja||| Liczba } P(n,k)Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest równa liczbie podziałów liczby } nParser nie mógł rozpoznać (błąd składni): {\displaystyle (na dowolną liczbę składników) o największym składniku równym } kParser nie mógł rozpoznać (błąd składni): {\displaystyle . }} {{dowod||| Odwracając o } 90Parser nie mógł rozpoznać (błąd składni): {\displaystyle stopni diagram podziału liczby } n$na$kParser nie mógł rozpoznać (błąd składni): {\displaystyle składników otrzymamy diagram podziału liczby } nParser nie mógł rozpoznać (błąd składni): {\displaystyle , którego największy składnik równy jest } kParser nie mógł rozpoznać (błąd składni): {\displaystyle . Oczywiście jest to odwzorowanie bijektywne, gdyż odwracając z powrotem o } 90Parser nie mógł rozpoznać (błąd składni): {\displaystyle stopni otrzymamy ten wyjściowy diagram. \medskip\noindent\textit{Rysunek:} 6.5 Szkic na kartce.\medskip }} {{obserwacja||| Liczba } P(n+k,k)Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest równa liczbie podziałów } nParser nie mógł rozpoznać (błąd składni): {\displaystyle na co najwyżej } kParser nie mógł rozpoznać (błąd składni): {\displaystyle składników. }} {{dowod||| Wycinając ostatnią kolumnę w diagramie podziału liczby } n+k$na$kParser nie mógł rozpoznać (błąd składni): {\displaystyle składników otrzymamy podział liczby } nParser nie mógł rozpoznać (błąd składni): {\displaystyle na co najwyżej } kParser nie mógł rozpoznać (błąd składni): {\displaystyle składników. Łatwo zauważyc, że jest to odwzorowanie bijektywne. \medskip\noindent\textit{Rysunek:} 6.6 Szkic na kartce.\medskip }}}