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)(5)=(0,3,4)(1,6)$,
• $\pi$ jest typu $[1^{2}2^{1}3^{1}]$.

Z samej definicji typu permutacji natychmiast wynika:

Obserwacja 6.1

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 6.2

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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (\alpha_1,\ldots,\alpha_n)} , jako uzupełnienie elementami z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathbb{Z}_n} następującego wzorca:

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \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\leqslant 1)}}

W miejsce Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle k} kropek możemy wstawić Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle k} -elementów na Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle k!} sposobów. Jednak w ten sposób otrzymamy wielokrotnie te same permutacje. Każdy cykl Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i} -elementowy możemy zadać na Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 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. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \alpha_i} takich samych cykli Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i} -elementowych może być wybranych na Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \alpha_i!} sposobów. Podsumowując, aby otrzymać liczbę permutacji typu Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \alpha_1,\ldots,\alpha_n)} musimy, dla wszystkich Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i\in{\left\{ {1,\ldots,n} \right\} }} , podzielić Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n!} przez długość każdego cyklu z osobna, tzn. dla każdego cyklu długości Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i} podzielić przez Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i} , oraz przez silnię liczby Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle i} -elementowych cykli. Zatem szukana liczba to Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle S_3} :

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{array} {|c|c|c|c|c|c|} \hline n&0&1&2&\text{rozklad na cykle}&\text{typ}\\ \hline \pi_0&0&1&2&(0)(1)(2)&[1^3]\\ \pi_1&1&0&2&(0,1)(2)&[1^12^1]\\ \pi_2&0&2&1&(0)(12)&[1^12^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^12^1]\\ \hline \end{array} }

Liczba permutacji z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle S_3} o kolejnych typach:

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \begin{array} {|c|l|} \hline \text{typ}&\text{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 6.3

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

MD1-5-1.swf

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.

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^{1}]$,
• $\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 6.4

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 6.5

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.

MD1-5-2.swf

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

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 6.6

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

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

MD1-5-3.swf

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

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 6.7

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 6.6 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 6.7 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 ${\mathsf {sgn}}(\pi )=(-1)^{r}$, gdzie $r$ jest liczbą transpozycji, na które można rozłożyć $\pi$.

Obserwacja 6.8

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

• ${\mathsf {sgn}}(id_{\mathbb {Z} _{n}})=1$,
• ${\mathsf {sgn}}(\sigma \pi )={\mathsf {sgn}}(\pi )\cdot {\mathsf {sgn}}(\sigma )$,
• ${\mathsf {sgn}}(\pi )={\mathsf {sgn}}(\pi ^{-1})$,

Dowód

Identyczność jest złożeniem zera transpozycji. Drugi punkt wynika natychmiast z Obserwacji 6.6. Dla dowodu trzeciego odnotujmy tylko, że ${\mathsf {sgn}}(\pi )\cdot {\mathsf {sgn}}(\pi ^{-1})={\mathsf {sgn}}(\pi \pi ^{-1})={\mathsf {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_"?

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 6.5 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 6.9

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 ${\mathsf {sgn}}(\tau \pi )={\mathsf {sgn}}(\tau ){\mathsf {sgn}}(\pi )=(-1)\cdot 1=-1$. Pozostaje pokazać, że dowolna nieparzysta permutacja $\rho$ jest na liście $\tau \pi _{0},\tau \pi _{1},\ldots ,\tau \pi _{k-1}$. Ponieważ ${\mathsf {sgn}}(\tau ^{-1}\rho )={\mathsf {sgn}}(\tau ^{-1}){\mathsf {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$.

MD1-5-5.swf

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

• 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 6.10

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 6.11

Dla $0<k\leqslant 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]$.

MD1-5-6.swf

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

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

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

$\underbrace {\{\bullet ,\ldots ,\bullet \}\{\bullet ,\ldots ,\bullet \}\ldots \{\bullet ,\ldots ,\bullet \}} _{k\ zbiorow\ 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$.

MD1-5-7.swf

Przykład

Lista podziałów $\mathbb {Z} _{4}$ na dwa bloki:

${\begin{array}{cc}{\left\{{0,1,2}\right\}}{\left\{{3}\right\}}&{\left\{{0,1}\right\}}{\left\{{2,3}\right\}}\\{\left\{{0,1,3}\right\}}{\left\{{2}\right\}}&{\left\{{0,2}\right\}}{\left\{{1,3}\right\}}\\{\left\{{0,2,3}\right\}}{\left\{{1}\right\}}&{\left\{{0,3}\right\}}{\left\{{1,2}\right\}}\\{\left\{{1,2,3}\right\}}{\left\{{0}\right\}}\end{array}}$

• Mamy $7$ podziałów zbioru $\mathbb {Z} _{4}$ na dwa bloki,

zatem $\left\{{\begin{array}{c}4\\2\end{array}}\right\}=7$.

Obserwacja 6.14

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

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

MD1-5-8.swf

Dowód

Niech, jak zwykle, $\left\vert X\right\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:

• ${\left\{{x}\right\}}$ stanowi blok jednoelementowy,
• $x$ jest w bloku co najmniej dwuelementowym.

Każdy podział pierwszego typu jest jednoznacznie wyznaczony przez $(n-1)$-elementowego zbioru $X-{\left\{{x}\right\}}$ 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 $\left\vert Y\right\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 $\left\vert Y\right\vert !\cdot \left\{{\begin{array}{c}\left\vert X\right\vert \\\left\vert Y\right\vert \end{array}}\right\}$.

Dowód

Niech $Y={\left\{{y_{0},\ldots ,y_{m-1}}\right\}}$. Jak już zauważyliśmy, surjekcja postaci $f:X\longrightarrow Y$ wyznacza pewien podział zbioru $X$ dodatkowo poetykietowany elementami zbioru $X$ na $m=\left\vert Y\right\vert$ bloków $f^{-1}({\left\{{y_{0}}\right\}}),\ldots ,f^{-1}({\left\{{y_{m-1}}\right\}})$. Nieetykietowanych podziałów jest oczywiście $\left\{{\begin{array}{c}\left\vert X\right\vert \\\left\vert Y\right\vert \end{array}}\right\}$. Ponieważ każdy podział może być poetykietowany na $\left\vert Y\right\vert !$ sposobów, możemy zakończyć dowód.

Obserwacja 6.17

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

$\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 $\left\vert X\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 $\left\{{\begin{array}{c}n\\k+1\end{array}}\right\}$.

Przykład

${\begin{aligned}\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{aligned}}$

Liczby Bella

Eric Temple Bell (1883-1960)
Zobacz biografię

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

$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

$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

$B_{n+1}=\sum _{i=0}^{n}{n \choose i}B_{n-i}=\sum _{i=0}^{n}{n \choose i}B_{i}$.

Bazy przestrzeni wielomianów

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

$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{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}.\end{aligned}}$

Obserwacja 6.20

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

$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{aligned}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\}(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}}.\end{aligned}}$

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$