Matematyka dyskretna 1/Wykład 6: Permutacje i podziały: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
 
(Nie pokazano 65 wersji utworzonych przez 8 użytkowników)
Linia 1: Linia 1:
 
==Permutacje==
 
==Permutacje==
  
Rozważając permutacje zbiorów <math>n</math>-elementowych wystarczy ograniczyć się do  
+
Rozważając permutacje zbiorów <math>n</math>-elementowych, wystarczy ograniczyć się do permutacji zbioru  <math>\mathbb{Z}_n</math>. Każdy inny taki zbiór różni się bowiem od <math>\mathbb{Z}_n</math> jedynie nazwami elementów.
permutacji zbioru  <math>\mathbb{Z}_n</math>.  
 
Każdy inny taki zbiór różni się bowiem od <math>\mathbb{Z}_n</math>  
 
jedynie nazwami elementów.
 
  
Poznaliśmy już algorytm rozkładu permutacji na rozłączne cykle.  
+
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 <math>\sigma_1 \circ \ldots \circ \sigma_k = \pi_1 \circ \ldots \circ \pi_l</math> są dwoma rozkładami tej samej permutacji na cykle to <math>k=l</math> i <math>{\left\{ {\sigma_1,\ldots,\sigma_k} \right\} } = {\left\{ {\pi_1,\ldots,\pi_k} \right\} }</math>.
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 <math>\sigma_1 \circ \ldots \circ \sigma_k = \pi_1 \circ \ldots \circ \pi_l</math>  
 
są dwoma rozkładami tej samej permutacji na cykle to <math>k=l</math> i  
 
<math>{\left\{ {\sigma_1,\ldots,\sigma_k} \right\}\ } = {\left\{ {\pi_1,\ldots,\pi_k} \right\}\ }</math>.
 
  
 
Pierwszym ważnym niezmiennikiem dla permutacji <math>\pi\in S_n</math> jest:
 
Pierwszym ważnym niezmiennikiem dla permutacji <math>\pi\in S_n</math> jest:
  
'''Liczba cykli''' permutacji <math>\pi\in S_n</math> zdefiniowana jako  
+
{{kotwica|lcykli|'''Liczba cykli'''}} permutacji <math>\pi\in S_n</math> zdefiniowana jako liczba cykli w jamimkolwiek rozkładzie <math>\pi</math> na cykle.
liczba cykli w jamimkolwiek rozkładzie <math>\pi</math> na cykle.
 
  
 
Jednoznaczność rozkładu na cykle pozwala nam zdefiniować również drugi ważny niezmiennik.
 
Jednoznaczność rozkładu na cykle pozwala nam zdefiniować również drugi ważny niezmiennik.
  
'''Typ permutacji'''  
+
{{kotwica|typperm|'''Typ permutacji'''}} <math>\pi\in S_n</math> to wektor <math>(\alpha_1,\ldots,\alpha_n)</math>, gdzie <math>\alpha_i</math> jest liczbą <math>i</math>-elementowych cykli w rozkładzie <math>\pi</math>. Zazwyczaj typ permutacji zapisujemy jako <math>[1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}]</math>, przy czym często pomijamy te wartości, dla których <math>\alpha_i=0</math>.
<math>\pi\in S_n</math> to wektor <math>(\alpha_1,\ldots,\alpha_n)</math>,  
 
gdzie <math>\alpha_i</math> jest liczbą <math>i</math>-elementowych cykli w rozkładzie <math>\pi</math>.  
 
Zazwyczaj typ permutacji zapisujemy jako  
 
<math>[1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}]</math>,  
 
przy czym często pomijamy te wartości, dla których <math>\alpha_i=0</math>.
 
  
 
{{przyklad|||
 
{{przyklad|||
 
Dla permutacji <math>\pi\in S_7</math> zadanej przez
 
Dla permutacji <math>\pi\in S_7</math> zadanej przez
 +
  
 
<center><math>\begin{array} {c|c|c|c|c|c|c|c}
 
<center><math>\begin{array} {c|c|c|c|c|c|c|c}
Linia 37: Linia 23:
 
\end{array}  
 
\end{array}  
 
</math></center>
 
</math></center>
 +
  
 
mamy:
 
mamy:
 
+
* <math>\pi=(0,3,4)(1,6)(2)(5)=(0,3,4)(1,6)</math>,
* <math>\pi=(0,3,4)(1,6)(2)(4)=(0,3,4)(1,6)</math>,
 
 
 
 
* <math>\pi</math> jest typu <math>[1^22^13^1]</math>.
 
* <math>\pi</math> jest typu <math>[1^22^13^1]</math>.
  
Linia 48: Linia 33:
 
Z samej definicji typu permutacji natychmiast wynika:
 
Z samej definicji typu permutacji natychmiast wynika:
  
{{obserwacja|||
+
{{obserwacja|6.1|obs 6.1|
 
 
 
Dla <math>\pi\in S_n</math> typu <math>(\alpha_1,\ldots,\alpha_n)</math> zachodzi
 
Dla <math>\pi\in S_n</math> typu <math>(\alpha_1,\ldots,\alpha_n)</math> zachodzi
 
 
* <math>\alpha_1+\ldots+\alpha_n=c(\pi)</math>,
 
* <math>\alpha_1+\ldots+\alpha_n=c(\pi)</math>,
 
 
* <math>\alpha_1+2\alpha_2+\ldots+n\alpha_n=n</math>.
 
* <math>\alpha_1+2\alpha_2+\ldots+n\alpha_n=n</math>.
  
 
}}
 
}}
  
{{obserwacja|||
+
{{obserwacja|6.2|obs 6.2|
 +
Liczba permutacji w <math>S_n</math> typu <math>(\alpha_1,\ldots,\alpha_n)</math> to
  
Liczba permutacji w <math>S_n</math> typu <math>(\alpha_1,\ldots,\alpha_n)</math> to
 
  
 
<center><math>\frac{n!}{1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}\alpha_1!\ldots\alpha_n!}.
 
<center><math>\frac{n!}{1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}\alpha_1!\ldots\alpha_n!}.
 
</math></center>
 
</math></center>
 +
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 +
Potraktujmy permutację typu <math>(\alpha_1,\ldots,\alpha_n)</math>, jako uzupełnienie elementami z <math>\mathbb{Z}_n</math> następującego wzorca:
  
Potraktujmy permutację typu <math>(\alpha_1,\ldots,\alpha_n)</math>,
 
jako uzupełnienie elementami z <math>\mathbb{Z}_n</math> następującego wzorca:
 
  
 
<center><math>\underbrace{(\bullet)\ldots(\bullet)}_{\alpha_1\ razy}
 
<center><math>\underbrace{(\bullet)\ldots(\bullet)}_{\alpha_1\ razy}
 
\underbrace{(\bullet\bullet)\ldots(\bullet\bullet)}_{\alpha_2\ razy}\ldots\ldots
 
\underbrace{(\bullet\bullet)\ldots(\bullet\bullet)}_{\alpha_2\ razy}\ldots\ldots
\underbrace{(\bullet\ldots\bullet)}_{\alpha_n\ razy\ (\alpha_n\leq 1)}.
+
\underbrace{(\bullet\ldots\bullet)}_{\alpha_n\ razy\ (\alpha_n\leqslant 1)}.
 
</math></center>
 
</math></center>
  
W miejsce <math>k</math> kropek możemy wstawić <math>k</math>-elementów na <math>k!</math> sposobów.  
+
 
Jednak w ten sposób otrzymamy wielokrotnie te same permutacje.  
+
W miejsce <math>k</math> kropek możemy wstawić <math>k</math>-elementów na <math>k!</math> sposobów. Jednak w ten sposób otrzymamy wielokrotnie te same permutacje. Każdy cykl <math>i</math>-elementowy możemy zadać na <math>i</math> 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. <math>\alpha_i</math> takich samych cykli <math>i</math>-elementowych może być wybranych na <math>\alpha_i!</math> sposobów. Podsumowując, aby otrzymać liczbę permutacji typu <math> \alpha_1,\ldots,\alpha_n)</math> musimy, dla wszystkich <math>i\in{\left\{ {1,\ldots,n} \right\} }</math>, podzielić <math>n!</math> przez długość każdego cyklu z osobna, tzn. dla każdego cyklu długości <math>i</math> podzielić przez <math>i</math>, oraz przez silnię liczby <math>i</math>-elementowych cykli. Zatem szukana liczba to <math>\frac{n!}{1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}\alpha_1!\ldots\alpha_n!}</math>.
Każdy cykl <math>i</math>-elementowy możemy zadać na <math>i</math> 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.  
 
<math>\alpha_i</math> takich samych cykli <math>i</math>-elementowych  
 
może być wybranych na <math>\alpha_i!</math> sposobów.  
 
Podsumowując, aby otrzymać liczbę permutacji typu <math>(\alpha_1,\ldots,\alpha_n)</math>  
 
musimy, dla wszystkich <math>i\in{\left\{ {1,\ldots,n} \right\}\ }</math>,  
 
podzielić <math>n!</math> przez długość każdego cyklu z osobna,  
 
tzn. dla każdego cyklu długości <math>i</math> podzielić przez <math>i</math>,  
 
oraz przez silnię liczby <math>i</math>-elementowych cykli.  
 
Zatem szukana liczba to  
 
<math>\frac{n!}{1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}\alpha_1!\ldots\alpha_n!}</math>.
 
 
}}
 
}}
  
 
{{przyklad|||
 
{{przyklad|||
 +
Lista typów wszystkich permutacji z <math>S_3</math>:
  
Lista typów wszystkich permutacji z <math>S_3</math>:
 
  
 
<center><math>\begin{array} {|c|c|c|c|c|c|}
 
<center><math>\begin{array} {|c|c|c|c|c|c|}
 
\hline
 
\hline
n&0&1&2&\textrm{rozklad na cykle}&\textrm{typ}\\
+
n&0&1&2&\text{rozklad na cykle}&\text{typ}\\
 
\hline
 
\hline
 
\pi_0&0&1&2&(0)(1)(2)&[1^3]\\
 
\pi_0&0&1&2&(0)(1)(2)&[1^3]\\
Linia 111: Linia 80:
 
\end{array}  
 
\end{array}  
 
</math></center>
 
</math></center>
 +
  
 
Liczba permutacji z <math>S_3</math> o kolejnych typach:
 
Liczba permutacji z <math>S_3</math> o kolejnych typach:
 +
  
 
<center><math>\begin{array} {|c|l|}
 
<center><math>\begin{array} {|c|l|}
 
\hline
 
\hline
\hbox{\rm typ}&\hbox{\rm liczba permutacji}\\
+
\text{typ}&\text{liczba permutacji}\\
 
\hline
 
\hline
 
1^3&\frac{3!}{1^3\cdot3!}=1\\
 
1^3&\frac{3!}{1^3\cdot3!}=1\\
Linia 124: Linia 95:
 
\end{array}  
 
\end{array}  
 
</math></center>
 
</math></center>
 +
  
 
}}
 
}}
  
Jak zobaczymy za chwilę, typ permutacji jest zachowywany  
+
Jak zobaczymy za chwilę, typ permutacji jest zachowywany przez pewną bardzo ważną operację algebraiczną.  
przez pewną bardzo ważną operację algebraiczną.
 
 
 
'''Permutacja sprzężona''' do permutacji <math>\pi,\rho\in S_n</math>
 
to każda permutacja postaci <math>\sigma\pi\sigma^{-1}</math>, gdzie <math>\sigma\in S_n</math>.
 
  
Oczywiście, jeśli <math>\sigma\pi\sigma^{-1}=\rho</math> to <math>\pi=\sigma^{-1}\rho\sigma</math>.
+
{{kotwica|permsprzez|'''Permutacja sprzężona'''}} do permutacji <math>\pi,\rho\in S_n</math> to każda permutacja postaci <math>\sigma\pi\sigma^{-1}</math>, gdzie <math>\sigma\in S_n</math>.
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
 
<math>id</math> jest ona sama.
 
  
{{obserwacja|||
+
Oczywiście, jeśli <math>\sigma\pi\sigma^{-1}=\rho</math> to <math>\pi=\sigma^{-1}\rho\sigma</math>. 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 <math>id</math> jest ona sama.
  
 +
{{obserwacja|6.3|obs 6.3|
 
Permutacje <math>\pi,\rho\in S_n</math> mają ten sam typ wtedy i tylko wtedy, gdy są sprzężone.
 
Permutacje <math>\pi,\rho\in S_n</math> mają ten sam typ wtedy i tylko wtedy, gdy są sprzężone.
 
}}
 
}}
 +
 +
[[File:MD1-5-1.svg|300x250px|thumb|right|MD1-5-1.swf]]
  
 
{{dowod|||
 
{{dowod|||
 +
Załóżmy najpierw, że <math>\pi</math> i <math>\rho</math> są sprzężone, czyli że <math>\sigma\pi\sigma^{-1}=\rho</math> dla pewnego <math>\sigma</math>. Rozważmy jakiś cykl <math>(x_0,\ldots,x_{k-1})</math> permutacji <math>\pi</math>. Wtedy <math>(\sigma(x_0),\ldots,\sigma(x_{k-1}))</math>  jest cyklem permutacji <math>\rho</math>. Istotnie, dla <math>i = 0,\ldots,k-1</math> mamy:
 +
  
Załóżmy najpierw, że <math>\pi</math> i <math>\rho</math> są sprzężone,
+
<center>
czyli że <math>\sigma\pi\sigma^{-1}=\rho</math> dla pewnego <math>\sigma</math>.
+
<math>\rho(\sigma(x_i))=\sigma\pi\sigma^{-1}\sigma(x_i)=\sigma\pi(x_i)=\sigma(x_{i+1}),
Rozważmy jakiś cykl <math>(x_0,\ldots,x_{k-1})</math> permutacji <math>\pi</math>.
+
</math>
Wtedy <math>(\sigma(x_0),\ldots,\sigma(x_{k-1}))</math> jest cyklem permutacji <math>\rho</math>.
+
</center>
Istotnie, dla <math>i = 0,\ldots,k-1</math> mamy:
 
  
<center><math>\rho(\sigma(x_i))=\sigma\pi\sigma^{-1}\sigma(x_i)=\sigma\pi(x_i)=\sigma(x_{i+1}),
 
</math></center>
 
  
 
i podobnie:
 
i podobnie:
  
<center><math>\rho(\sigma(x_{k-1})=\sigma\pi\sigma^{-1}\sigma(x_{k-1})=\sigma\pi(x_{k-1})=\sigma(x_0).
 
</math></center>
 
  
Każdy zatem cykl permutacji <math>\pi</math>  
+
<center>
wyznacza jednoznacznie cykl permutacji <math>\rho</math> o tej samej liczności.
+
<math>\rho(\sigma(x_{k-1})=\sigma\pi\sigma^{-1}\sigma(x_{k-1})=\sigma\pi(x_{k-1})=\sigma(x_0).
Tym samym <math>\pi</math> i <math>\rho</math> są tego samego typu.
+
</math>
 +
</center>
 +
 
  
''Rysunek:'' 5.1 Szkic na kartce.
+
Każdy zatem cykl permutacji <math>\pi</math> wyznacza jednoznacznie cykl permutacji <math>\rho</math> o tej samej liczności. Tym samym <math>\pi</math> i <math>\rho</math> są tego samego typu.
  
Dla dowodu w drugą stronę załóżmy, że <math>\pi</math> i <math>\rho</math> mają ten sam typ.  
+
Dla dowodu w drugą stronę załóżmy, że <math>\pi</math> i <math>\rho</math> mają ten sam typ. Wtedy możemy określić bijekcję przyporządkowującą każdemu cyklowi permutacji <math>\pi</math> pewien cykl <math>\rho</math> o tej samej długości. Po rozkładzie obu permutacji <math>\pi,\rho</math> na rozłączne cykle i nasza bijekcja między cyklami przyporzadkowuje cyklowi <math>(x_0,\ldots,x_{k-1})</math> cykl <math>(y_0,\ldots,y_{k-1})</math>, definiujemy <math>\sigma \in S_n</math> kładąc <math>\sigma(x_i)=y_i</math>. Łatwo sprawdzić, że wtedy <math>\sigma\pi\sigma^{-1}=\rho</math>.
Wtedy możemy określić bijekcję  
 
przyporządkowującą każdemu cyklowi permutacji <math>\pi</math>  
 
pewien cykl <math>\rho</math> o tej samej długości.  
 
Po rozkładzie obu permutacji <math>\pi,\rho</math> na rozłączne cykle  
 
i nasza bijekcja między cyklami przyporzadkowuje cyklowi
 
<math>(x_0,\ldots,x_{k-1})</math> cykl <math>(y_0,\ldots,y_{k-1})</math>,  
 
definiujemy <math>\sigma \in S_n</math> kładąc <math>\sigma(x_i)=y_i</math>.  
 
Łatwo sprawdzić, że wtedy <math>\sigma\pi\sigma^{-1}=\rho</math>.
 
 
}}
 
}}
  
'''Transpozycja''' to permutacja w <math>S_n</math> (dla <math>n\leqslant2</math>) typu <math>[1^{n-2}2^1]</math>.  
+
{{kotwica|transpozycja|'''Transpozycja'''}} to permutacja w <math>S_n</math> (dla <math>n\leqslant2</math>) typu <math>[1^{n-2}2^1]</math>. Innymi słowy, transpozycja dokonuje tylko jednego przestawienia dwóch elementów ze zbioru <math>n</math>-elementowego.
Innymi słowy, transpozycja dokonuje tylko  
 
jednego przestawienia dwóch elementów ze zbioru <math>n</math>-elementowego.
 
  
 
{{przyklad|||
 
{{przyklad|||
 +
Dla permutacji <math>\pi\in S_7</math> zadanej przez
  
Dla permutacji <math>\pi\in S_7</math> zadanej przez
 
  
<center><math>\begin{array} {|c||c|c|c|c|c|c|c|}
+
<center>
 +
<math>\begin{array} {|c||c|c|c|c|c|c|c|}
 
\hline
 
\hline
 
n&0&1&2&3&4&5&6\\
 
n&0&1&2&3&4&5&6\\
Linia 192: Linia 150:
 
\hline
 
\hline
 
\end{array}  
 
\end{array}  
</math></center>
+
</math>
 +
</center>
 +
 
  
 
mamy:
 
mamy:
  
 
* <math>\pi=(0)(1)(25)(3)(4)(6)=(25),</math>
 
* <math>\pi=(0)(1)(25)(3)(4)(6)=(25),</math>
 
+
* <math>\pi</math> ma typ <math>[1^52^1]</math>,
* <math>\pi</math> ma typ <math>[1^52^2]</math>,
 
 
 
 
* <math>\pi</math> jest transpozycją.
 
* <math>\pi</math> jest transpozycją.
  
 
}}
 
}}
  
Waga transpozycji wynika z faktu, że dowolna permutacja jest złożeniem transpozycji.  
+
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.
Ponieważ, dowolna permutacja jest rozkładalna na cykle wystarczy pokazać,  
 
że każdy cykl jest złożeniem transpozycji.
 
 
 
{{obserwacja|||
 
  
 +
{{obserwacja|6.4|obs 6.4|
 
Dowolny cykl z <math>S_n</math> jest złożeniem <math>n-1</math> transpozycji.
 
Dowolny cykl z <math>S_n</math> jest złożeniem <math>n-1</math> transpozycji.
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 +
Cykl <math>\pi=(x_0,\ldots,x_{n-1})</math> można przedstawić tabelką:
  
Cykl <math>\pi=(x_0,\ldots,x_{n-1})</math> można przedstawić tabelką:
 
  
 
<center><math>\begin{array} {|c||c|c|c|c|c|c|}
 
<center><math>\begin{array} {|c||c|c|c|c|c|c|}
Linia 225: Linia 180:
 
\end{array}  
 
\end{array}  
 
</math></center>
 
</math></center>
 +
  
 
Zauważmy, że <math>\pi</math> jest następującym złożeniem transpozycji
 
Zauważmy, że <math>\pi</math> jest następującym złożeniem transpozycji
 +
  
 
<center><math>(x_0,x_{n-1})(x_0,x_{n-2})\ldots(x_0,x_2)(x_0,x_1).
 
<center><math>(x_0,x_{n-1})(x_0,x_{n-2})\ldots(x_0,x_2)(x_0,x_1).
 
</math></center>
 
</math></center>
 +
  
 
Rzeczywiście <math>x_0</math> przejdzie:
 
Rzeczywiście <math>x_0</math> przejdzie:
 
 
* w pierwszej transpozycji <math>(x_0,x_1)</math> w <math>x_1</math>,
 
* w pierwszej transpozycji <math>(x_0,x_1)</math> w <math>x_1</math>,
 
 
* a następne transpozycje już go nie przesuną.  
 
* a następne transpozycje już go nie przesuną.  
  
 
Podobnie <math>x_1</math> przejdzie  
 
Podobnie <math>x_1</math> przejdzie  
 
 
* pierwszą transpozycją <math>(x_0,x_1)</math> w <math>x_0</math>,  
 
* pierwszą transpozycją <math>(x_0,x_1)</math> w <math>x_0</math>,  
 
 
* drugą <math>(x_0,x_2)</math> w <math>x_2</math>,
 
* drugą <math>(x_0,x_2)</math> w <math>x_2</math>,
 
 
* a następne transpozycje już go nie przesuną.  
 
* a następne transpozycje już go nie przesuną.  
  
Ogólnie, <math>x_i</math> (dla <math>i\in{\left\{ {1,\ldots,n-2} \right\}\ }</math>)  
+
Ogólnie, <math>x_i</math> (dla <math>i\in{\left\{ {1,\ldots,n-2} \right\} }</math>)  
 
 
 
* pozostanie na swoim miejscu przez pierwsze <math>i-1</math> transpozycji <br>
 
* pozostanie na swoim miejscu przez pierwsze <math>i-1</math> transpozycji <br>
 
<math>(x_0,x_1),(x_0,x_2),\ldots,(x_0,x_{i-1})</math>,
 
<math>(x_0,x_1),(x_0,x_2),\ldots,(x_0,x_{i-1})</math>,
 
 
* przejdzie <math>i</math>-tą transpozycją w <math>x_0</math>,  
 
* przejdzie <math>i</math>-tą transpozycją w <math>x_0</math>,  
 
 
* przejdzie <math>(i+1)</math>-szą transpozycją w <math>x_{i+1}</math>,
 
* przejdzie <math>(i+1)</math>-szą transpozycją w <math>x_{i+1}</math>,
 
 
* po czym zostanie już nienaruszone.
 
* po czym zostanie już nienaruszone.
  
Natomiast <math>x_{n-1}</math> zostanie przesunięte dopiero ostatnią transpozycją i
+
Natomiast <math>x_{n-1}</math> zostanie przesunięte dopiero ostatnią transpozycją i przyjmie wartość <math>x_0</math>.
przyjmie wartość <math>x_0</math>.
 
 
}}
 
}}
  
{{wniosek|||
+
{{wniosek|6.5|wn 6.5|
 +
Dowolna permutacja jest złożeniem transpozycji. W szczególności każda permutacja typu <math>[1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}]</math> ma rozkład na co najwyżej <math>\alpha_2+2\alpha_3+\ldots(n-1)\alpha_n</math> transpozycji.
 +
}}
  
Dowolna permutacja jest złożeniem transpozycji.
+
[[File:MD1-5-2.svg|250x250px|thumb|right|MD1-5-2.swf]]
W szczególności każda permutacja typu
 
<math>[1^{\alpha_1}2^{\alpha_2}\ldots n^{\alpha_n}]</math> ma rozkład na co najwyżej
 
<math>\alpha_2+2\alpha_3+\ldots(n-1)\alpha_n</math> transpozycji.
 
}}
 
  
 
{{przyklad|||
 
{{przyklad|||
 +
Dla permutacji <math>\pi\in S_7</math> zadanej przez
  
Dla permutacji <math>\pi\in S_7</math> zadanej przez
 
  
<center><math>\begin{array} {|c||c|c|c|c|c|c|c|}
+
<center>
 +
<math>\begin{array} {|c||c|c|c|c|c|c|c|}
 
\hline
 
\hline
 
n&0&1&2&3&4&5&6\\
 
n&0&1&2&3&4&5&6\\
Linia 279: Linia 226:
 
\hline
 
\hline
 
\end{array}  
 
\end{array}  
</math></center>
+
</math>
 +
</center>
 +
 
  
 
mamy
 
mamy
 
 
* <math>\pi=(0,2,5)(1,3,4,6)</math>,
 
* <math>\pi=(0,2,5)(1,3,4,6)</math>,
 
 
* <math>(1,3,4,6)=(1,6)(1,4)(1,3)</math>,
 
* <math>(1,3,4,6)=(1,6)(1,4)(1,3)</math>,
 
 
* <math>(0,2,5)=(0,5)(0,2)</math>,
 
* <math>(0,2,5)=(0,5)(0,2)</math>,
 
 
* <math>\pi=(0,5)(0,2)(1,6)(1,4)(1,3)=(1,6)(1,4)(1,3)(0,5)(0,2)</math>.
 
* <math>\pi=(0,5)(0,2)(1,6)(1,4)(1,3)=(1,6)(1,4)(1,3)(0,5)(0,2)</math>.
 
''Rysunek:'' 5.2 Szkic na kartce.
 
  
 
Zauważmy, że składanie transpozycji na rozłącznych zbiorach dwuelementowych  
 
Zauważmy, że składanie transpozycji na rozłącznych zbiorach dwuelementowych  
jest przemienne.  
+
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,  
Na ogół jednak, ponieważ transpozycje nie działają na zbiorach rozłącznych,  
+
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ż
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ż
 
 
<math>\pi=(1,6)(2,5)(0,2)(3,6)(0,5)(4,6)(2,5)</math>.
 
<math>\pi=(1,6)(2,5)(0,2)(3,6)(0,5)(4,6)(2,5)</math>.
 
}}
 
}}
  
Nie mamy zatem jednoznaczności rozkładu na transpozycje,  
+
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.
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|||
+
{{obserwacja|6.6|obs 6.6|
 +
Jeśli <math>\pi,\tau \in S_n</math> i <math>\tau</math> jest transpozycją, to
  
Jeśli <math>\pi,\tau \in S_n</math> i <math>\tau</math> jest transpozycją, to
 
  
 
<center><math>c(\tau\pi)=c(\pi)\pm 1=c(\pi\tau).
 
<center><math>c(\tau\pi)=c(\pi)\pm 1=c(\pi\tau).
 
</math></center>
 
</math></center>
 +
  
 
}}
 
}}
 +
 +
[[File:MD1-5-3.svg|250x250px|thumb|right|MD1-5-3.swf]]
  
 
{{dowod|||
 
{{dowod|||
Udowodnimy tylko pierwszą równość.  
+
Udowodnimy tylko pierwszą równość. Załóżmy, że <math>\tau=(a,b)</math> tzn., <math>\tau(a)=b</math>, <math>\tau(b)=a</math> i <math>\tau(x)=x</math> dla wszystkich pozostałych elementów <math>x \in\mathbb{Z}_n</math>.
Załóżmy, że <math>\tau=(a,b)</math> tzn., <math>\tau(a)=b</math>, <math>\tau(b)=a</math>  
 
i <math>\tau(x)=x</math> dla wszystkich pozostałych elementów <math>x \in\mathbb{Z}_n</math>.
 
 
Rozumowanie dzielimy na dwa przypadki:
 
Rozumowanie dzielimy na dwa przypadki:
 
 
* <math>a</math> i <math>b</math> są w tym samym cyklu <math>(a,x,\ldots,y,b,w,\ldots,z)</math> permutacji <math>\pi</math>.
 
* <math>a</math> i <math>b</math> są w tym samym cyklu <math>(a,x,\ldots,y,b,w,\ldots,z)</math> permutacji <math>\pi</math>.
  
''Rysunek:'' 5.3 Szkic na kartce.
+
Wtedy <math>\tau\pi=(a,x,\ldots,y)(b,w,\ldots,z)\ldots</math>, gdzie ostatni wielokropek oznacza pozostałe cykle permutacji <math>\pi</math>. Zatem w tym przypadku mamy <math>c(\tau\pi)=c(\pi)+1</math>.
 
 
Wtedy <math>\tau\pi=(a,x,\ldots,y)(b,w,\ldots,z)\ldots</math>,  
 
gdzie ostatni wielokropek oznacza pozostałe cykle permutacji <math>\pi</math>.  
 
Zatem w tym przypadku mamy <math>c(\tau\pi)=c(\pi)+1</math>.
 
 
 
 
* <math>a</math> i <math>b</math> są w różnych cyklach permutacji <math>\pi=(a,x\ldots,y)(b,\ldots,z)\ldots</math>.
 
* <math>a</math> i <math>b</math> są w różnych cyklach permutacji <math>\pi=(a,x\ldots,y)(b,\ldots,z)\ldots</math>.
  
Linia 338: Linia 268:
 
}}
 
}}
  
{{obserwacja|||
+
{{obserwacja|6.7|obs 6.7|
 
+
Jeśli permutacja jest przedstawialna jako złożenia <math>r</math> i <math>r'</math> transpozycji, to liczby <math>r</math> i <math>r'</math> albo  są obie parzyste albo obie nieparzyste.
Jeśli permutacja jest przedstawialna jako złożenia <math>r</math> i <math>r'</math> transpozycji,
 
to liczby <math>r</math> i <math>r'</math> albo  są obie parzyste albo obie nieparzyste.
 
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 +
Niech <math>\tau_{r-1}\ldots\tau_0=\tau_{r'-1}'\ldots\tau_0'</math> będą dwoma
 +
rozkładami tej samej permutacji <math>\pi \in S_n</math> na transpozycje. Na mocy [[#obs_6.6|Obserwacji 6.6]] mamy:
  
Niech <math>\tau_{r-1}\ldots\tau_0=\tau_{r'-1}'\ldots\tau_0'</math> będą dwoma
 
rozkładami tej samej permutacji <math>\pi \in S_n</math> na transpozycje.
 
Na mocy Obserwacji [[##obserwacja - zachowanie c po zlozeniu z transpozycja|Uzupelnic obserwacja - zachowanie c po zlozeniu z transpozycja|]] mamy:
 
  
 
<center><math>c(\tau_{r-1}\ldots\tau_0)  
 
<center><math>c(\tau_{r-1}\ldots\tau_0)  
Linia 357: Linia 284:
 
</math></center>
 
</math></center>
  
Niech <math>t</math> opisuje iloć dodawań jedynki w powyższej formule.
+
 
Wtedy <math>r-1-t</math> to liczba odejmowań jedynki.  
+
Niech <math>t</math> opisuje iloć dodawań jedynki w powyższej formule. Wtedy <math>r-1-t</math> to liczba odejmowań jedynki. Transpozycja <math>\tau_0</math> ma <math>1</math> cykl <math>2</math>-elementowy i <math>n-2</math> cykli <math>1</math>-elementowych, czyli <math>c(\tau_0)=1+(n-2)=n-1</math>. Zatem
Transpozycja <math>\tau_0</math> ma <math>1</math> cykl <math>2</math>-elementowy i <math>n-2</math> cykli <math>1</math>-elementowych,  
+
 
czyli <math>c(\tau_0)=1+(n-2)=n-1</math>.  
 
Zatem
 
  
 
<center><math>c(\pi)=c(\tau_{r-1}\ldots\tau_0)=n-1+t-(r-1-t)=n-r+2t
 
<center><math>c(\pi)=c(\tau_{r-1}\ldots\tau_0)=n-1+t-(r-1-t)=n-r+2t
 
</math></center>
 
</math></center>
  
dla pewnego <math>t</math>.
+
 
Analogicznie
+
dla pewnego <math>t</math>. Analogicznie
 +
 
  
 
<center><math>c(\pi)=c(\tau'_{r'-1}\ldots\tau'_0)=n-1+t'-(r'-1-t')=n-r'+2t'
 
<center><math>c(\pi)=c(\tau'_{r'-1}\ldots\tau'_0)=n-1+t'-(r'-1-t')=n-r'+2t'
 
</math></center>
 
</math></center>
  
dla pewnego <math>t'</math>.
+
 
Porównując obydwa wyniki otrzymujemy
+
dla pewnego <math>t'</math>. Porównując obydwa wyniki otrzymujemy
 +
 
  
 
<center><math>r-r'=2a-2a',
 
<center><math>r-r'=2a-2a',
 
</math></center>
 
</math></center>
 +
  
 
czyli różnica <math>r-r'</math> jest zawsze parzysta.  
 
czyli różnica <math>r-r'</math> jest zawsze parzysta.  
 
}}
 
}}
  
Obserwacja [[##obserwacja - jednoznaczna parzystosc permutacji|Uzupelnic obserwacja - jednoznaczna parzystosc permutacji|]]  
+
[[#obs_6.7|Obserwacja 6.7]] pozwala zdefiniować parzystość permutacji.  
pozwala zdefiniować parzystość permutacji.
 
 
 
'''Permutacja parzysta'''
 
to permutacja będąca złożeniem parzystej liczby transpozycji.  
 
  
'''Permutacja nieparzysta'''  
+
{{kotwica|permparz|'''Permutacja parzysta'''}} to permutacja będąca złożeniem parzystej liczby transpozycji.  
to permutacja będąca złożeniem nieparzystej liczby transpozycji.  
 
  
'''Znak permutacji''' <math>\pi</math>
+
{{kotwica|permnieparz|'''Permutacja nieparzysta'''}} to permutacja będąca złożeniem nieparzystej liczby transpozycji.  
to <math>\mbox{\sf sgn}(\pi)=(-1)^r</math>,
 
gdzie <math>r</math> jest liczbą transpozycji, na które można rozłożyć <math>\pi</math>.
 
  
{{obserwacja|||
+
{{kotwica|znakperm|'''Znak permutacji'''}} <math>\pi</math> to <math>\mathsf{ sgn}(\pi)=(-1)^r</math>, gdzie <math>r</math> jest liczbą transpozycji, na które można rozłożyć <math>\pi</math>.
  
 +
{{obserwacja|6.8|obs 6.8|
 
Dla dowolnych <math>\pi,\sigma\in S_n</math>
 
Dla dowolnych <math>\pi,\sigma\in S_n</math>
 
+
* <math>\mathsf{ sgn}(id_{\mathbb{Z}_n})=1</math>,
* <math>\mbox{\sf sgn}(id_{\mathbb{Z}_n})=1</math>,
+
* <math>\mathsf{ sgn}(\sigma\pi)=\mathsf{ sgn}(\pi)\cdot\mathsf{ sgn}(\sigma)</math>,
 
+
* <math>\mathsf{ sgn}(\pi)=\mathsf{ sgn}(\pi^{-1})</math>,  
* <math>\mbox{\sf sgn}(\sigma\pi)=\mbox{\sf sgn}(\pi)\cdot\mbox{\sf sgn}(\sigma)</math>,
 
 
 
* <math>\mbox{\sf sgn}(\pi)=\mbox{\sf sgn}(\pi^{-1})</math>,  
 
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 
+
Identyczność jest złożeniem zera transpozycji. Drugi punkt wynika natychmiast z [[#obs_6.6|Obserwacji 6.6]]. Dla dowodu trzeciego odnotujmy tylko, że  
Identyczność jest złożeniem zera transpozycji.
+
<math>\mathsf{ sgn}(\pi)\cdot\mathsf{ sgn}(\pi^{-1}) =\mathsf{ sgn}(\pi\pi^{-1})=\mathsf{ sgn}(id_{\mathbb{Z}_n})=1</math>.
Drugi punkt wynika natychmiast z Obserwacji
 
[[##obserwacja - zachowanie c po zlozeniu z transpozycja|Uzupelnic obserwacja - zachowanie c po zlozeniu z transpozycja|]].  
 
Dla dowodu trzeciego odnotujmy tylko, że  
 
<math>\mbox{\sf sgn}(\pi)\cdot\mbox{\sf sgn}(\pi^{-1})
 
=\mbox{\sf sgn}(\pi\pi^{-1})=\mbox{\sf sgn}(id_{\mathbb{Z}_n})=1</math>.
 
 
}}
 
}}
  
 +
[[File:Rys-5-4.mp4|253x253px|thumb|right]]
 
{{przyklad|||
 
{{przyklad|||
 +
Dla relaksu rozważmy łamigłówkę logiczną rozgrywaną na kwadracie <math>3 \times 3</math>. 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_"?
  
Dla relaksu rozważmy łamigłówkę logiczną rozgrywaną na kwadracie <math>3 \times 3</math>.
+
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:
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 <math>\pi\in S_9</math>:
 
* mamy dokonać permutacji <math>\pi\in S_9</math>:
  
<center><math>\begin{array} {ccccccccc}
+
<center>
 +
<math>\begin{array} {ccccccccc}
 
B&O&R&L&Y&M&E&P&\_\\
 
B&O&R&L&Y&M&E&P&\_\\
 
\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\
 
\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\
 
P&R&O&B&L&E&M&Y&\_
 
P&R&O&B&L&E&M&Y&\_
 
\end{array}  
 
\end{array}  
</math></center>
+
</math>
 +
</center>
  
 
* każdy ruch zgodny z regułami gry to jakaś transpozycja wybranych klocków,  
 
* każdy ruch zgodny z regułami gry to jakaś transpozycja wybranych klocków,  
Linia 449: Linia 352:
  
 
Zauważmy, że
 
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
* rozwiązanie musi być wykonane przy pomocy parzystej liczby ruchów,  
 
zatem każda permutacja dokonująca żądanej rearanżacji klocków jest parzysta
 
 
 
 
* <math>\pi=(B,P,Y,L)(O,R)(M,E)(\_)</math>,
 
* <math>\pi=(B,P,Y,L)(O,R)(M,E)(\_)</math>,
 +
* [[#wn_6.5|Wniosek 6.5]] daje wtedy jednak, że <math>\pi</math> jest złożeniem <math>3+1+1=5</math> transpozycji, czyli <math>\pi</math> jest permutacją nieparzystą.
  
* Wniosek [[##wniosek - permutacja jest zlozeniem ilus tam transpozycji|Uzupelnic wniosek - permutacja jest zlozeniem ilus tam transpozycji|]]
+
Ponieważ nie można złożyć nieparzystej permutacji z parzystej liczby transpozycji, nasza łamigłówka nie jest możliwa do rozwiązania.
daje wtedy jednak, że <math>\pi</math> jest złożeniem <math>3+1+1=5</math> transpozycji,
 
czyli <math>\pi</math> 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|||
+
{{obserwacja|6.9|obs 6.9|
 
 
 
Dla <math>n\geqslant2</math> w <math>S_n</math> jest dokładnie tyle samo permutacji parzystych co nieparzystych.
 
Dla <math>n\geqslant2</math> w <math>S_n</math> jest dokładnie tyle samo permutacji parzystych co nieparzystych.
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 +
Niech <math>n\geqslant2</math> i <math>\pi_0,\ldots,\pi_{k-1}</math> będzie listą wszystkich parzystych permutacji w <math>S_n</math>. Ponadto, rozważmy transpozycję <math>\tau=(01)(2)\ldots(n)</math>. Wtedy oczywiście permutacje <math>\tau\pi_0,\tau\pi_1,\ldots,\tau\pi_{k-1}</math> są parami różne, gdyż jeśli <math>\tau\pi_i=\tau\pi_j</math> to <math>\pi_i=\tau^{-1}\tau\pi=\tau^{-1}\tau\pi_j=\pi_j</math>. Ponadto dowolna <math>\tau\pi</math> jest nieparzysta, bo <math>\mathsf{ sgn}(\tau\pi)=\mathsf{ sgn}(\tau)\mathsf{ sgn}(\pi)=(-1)\cdot1=-1.</math> Pozostaje pokazać, że dowolna nieparzysta permutacja <math>\rho</math> jest na liście <math>\tau\pi_0,\tau\pi_1,\ldots,\tau\pi_{k-1}</math>. Ponieważ
 +
<math>\mathsf{ sgn}(\tau^{-1}\rho)=\mathsf{ sgn}(\tau^{-1})\mathsf{ sgn}(\rho)=(-1)\cdot(-1)=1,</math> to <math>\tau^{-1}\rho</math> jest permutacją parzystą, a zatem jest postaci <math>\pi_i</math> dla pewnego <math>i</math>.
 +
To zaś oznacza, że
  
Niech <math>n\geqslant2</math> i
 
<math>\pi_0,\ldots,\pi_{k-1}</math> będzie listą wszystkich parzystych permutacji w <math>S_n</math>.
 
Ponadto, rozważmy transpozycję <math>\tau=(01)(2)\ldots(n)</math>.
 
Wtedy oczywiście permutacje <math>\tau\pi_0,\tau\pi_1,\ldots,\tau\pi_{k-1}</math> są parami różne,
 
gdyż jeśli <math>\tau\pi_i=\tau\pi_j</math> to
 
<math>\pi_i=\tau^{-1}\tau\pi=\tau^{-1}\tau\pi_j=\pi_j</math>.
 
Ponadto dowolna <math>\tau\pi</math> jest nieparzysta, bo
 
<math>\mbox{\sf sgn}(\tau\pi)=\mbox{\sf sgn}(\tau)\mbox{\sf sgn}(\pi)=(-1)\cdot1=-1.
 
</math>
 
Pozostaje pokazać, że dowolna nieparzysta permutacja <math>\rho</math> jest na liście
 
<math>\tau\pi_0,\tau\pi_1,\ldots,\tau\pi_{k-1}</math>. Ponieważ
 
<math>\mbox{\sf sgn}(\tau^{-1}\rho)=\mbox{\sf sgn}(\tau^{-1})\mbox{\sf sgn}(\rho)=(-1)\cdot(-1)=1,
 
</math>
 
to <math>\tau^{-1}\rho</math> jest permutacją parzystą,
 
a zatem jest postaci <math>\pi_i</math> dla pewnego <math>i</math>.
 
To zaś oznacza, że
 
  
 
<center><math>\rho=\tau\tau^{-1}\rho=\tau\pi_i,
 
<center><math>\rho=\tau\tau^{-1}\rho=\tau\pi_i,
 
</math></center>
 
</math></center>
  
czyli <math>\rho</math> jest na liście <math>\tau\pi_0,\tau\pi_1,\ldots,\tau\pi_{k-1}</math>.  
+
 
Uzyskana bijekcja <math>\pi_i \mapsto \tau\pi_i</math> dowodzi naszej obserwacji.
+
czyli <math>\rho</math> jest na liście <math>\tau\pi_0,\tau\pi_1,\ldots,\tau\pi_{k-1}</math>. Uzyskana bijekcja <math>\pi_i \mapsto \tau\pi_i</math> dowodzi naszej obserwacji.
 
}}
 
}}
  
Linia 498: Linia 380:
 
===Liczby Stirlinga===
 
===Liczby Stirlinga===
  
'''Liczba Stirlinga dla cykli''' <math>\left[\begin{array} {c}n\\ k\end{array} \right]</math>  
+
{{kotwica|lstirlcykl|'''Liczba Stirlinga dla cykli'''}} <math>\left[\begin{array} {c}n\\ k\end{array} \right]</math> (często nazywana liczbą Stirlinga pierwszego rodzaju) to liczba permutacji zbioru <math>n</math>-elementowego złożonych z dokładnie <math>k</math> cykli, czyli takich permutacji <math>\pi \in S_n</math>, że <math>c(\pi)=k</math>. Przyjmujemy, że <math>\left[\begin{array} {c}0\\ 0\end{array} \right]=1</math>, 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ść
(często nazywana liczbą Stirlinga pierwszego rodzaju)  
+
<math>\left[\begin{array} {c}n\\ k\end{array} \right]</math> dla wszystkich <math>k\in\mathbb{Z}</math>. Przyjmujemy, że <math>\left[\begin{array} {c}n\\ k\end{array} \right]=0</math> dla <math>k<0</math>.
to liczba permutacji zbioru <math>n</math>-elementowego złożonych z dokładnie <math>k</math> cykli,  
+
 
czyli takich permutacji <math>\pi \in S_n</math>, że <math>c(\pi)=k</math>.
+
[[File:MD1-5-5.svg|250x250px|thumb|right|MD1-5-5.swf]]
Przyjmujemy, że <math>\left[\begin{array} {c}0\\ 0\end{array} \right]=1</math>,  
 
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ść  
 
<math>\left[\begin{array} {c}n\\ k\end{array} \right]</math> dla wszystkich <math>k\in\mathbb{Z}</math>.  
 
Przyjmujemy, że <math>\left[\begin{array} {c}n\\ k\end{array} \right]=0</math> dla <math>k<0</math>.
 
  
 
{{przyklad|||
 
{{przyklad|||
 
 
Lista permutacji <math>\mathbb{Z}_4</math> złożonych z <math>2</math> cykli:
 
Lista permutacji <math>\mathbb{Z}_4</math> złożonych z <math>2</math> cykli:
  
<center><math>\begin{array} {ccc}
+
<center>
 +
<math>\begin{array} {ccc}
 
(0,1,2)(3)&(0,2,3)(1)&(0,1)(2,3)\\
 
(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,2,1)(3)&(0,3,2)(1)&(0,2)(1,3)\\
Linia 519: Linia 395:
 
(0,3,1)(2)&(1,3,2)(0)
 
(0,3,1)(2)&(1,3,2)(0)
 
\end{array}  
 
\end{array}  
</math></center>
+
</math>
 +
</center>
  
''Rysunek:'' 5.5 Szkic na kartce.
+
* Mamy <math>11</math> permutacji <math>\mathbb{Z}_4</math> złożonych z dwóch cykli, zatem <math>\left[\begin{array} {c}4\\ 2\end{array} \right]=11</math>.
 
 
* Mamy <math>11</math> permutacji <math>\mathbb{Z}_4</math> złożonych z dwóch cykli,  
 
zatem <math>\left[\begin{array} {c}4\\ 2\end{array} \right]=11</math>.
 
  
 
}}
 
}}
  
{{obserwacja|||
+
{{obserwacja|6.10|obs 6.10|
 
Dla <math>n\in\mathbb{N}</math>
 
Dla <math>n\in\mathbb{N}</math>
 
 
* <math>\left[\begin{array} {c}n\\ 0\end{array} \right]=0</math>, dla <math>n>0</math>
 
* <math>\left[\begin{array} {c}n\\ 0\end{array} \right]=0</math>, dla <math>n>0</math>
 
 
* <math>\left[\begin{array} {c}n\\ 1\end{array} \right]=(n-1)!</math>,
 
* <math>\left[\begin{array} {c}n\\ 1\end{array} \right]=(n-1)!</math>,
 
 
* <math>\left[\begin{array} {c}n\\ n-1\end{array} \right]={n\choose2}</math>,
 
* <math>\left[\begin{array} {c}n\\ n-1\end{array} \right]={n\choose2}</math>,
 
 
* <math>\left[\begin{array} {c}n\\ n\end{array} \right]=1</math>,
 
* <math>\left[\begin{array} {c}n\\ n\end{array} \right]=1</math>,
 
 
* <math>\left[\begin{array} {c}n\\ k\end{array} \right]=0</math>, dla <math>k>n</math>
 
* <math>\left[\begin{array} {c}n\\ k\end{array} \right]=0</math>, dla <math>k>n</math>
  
Linia 544: Linia 413:
  
 
{{dowod|||
 
{{dowod|||
 +
Pierwszy punkt jest natychmiastowa konsekwencją faktu, że nie można podzielić niepustego zbioru na <math>0</math> części (cykli).
  
Pierwszy punkt jest natychmiastowa konsekwencją faktu,  
+
Liczba <math>\left[\begin{array} {c}n\\ 1\end{array} \right]</math> opisuje permutacje o jednym cyklu. Każda taka permutacja jest zadana wzorcem
że nie można podzielić niepustego zbioru na <math>0</math> części (cykli).
+
<math>(\underbrace{\bullet,\ldots,\bullet}_{n\ pozycji})</math>. Wzorzec taki może być wypełniony <math>n</math>-elementami na <math>n!</math> sposobów. Ale ten sam cykl ma wiele opisów różniących się jedynie przesunięciem. Zatem każdy <math>n</math>-elementowy cykl może być zapisany według takiego wzorca na <math>n</math> sposobów, czyli liczba cykli na zbiorze <math>n</math>-elementowym to <math>\frac{n!}{n}=(n-1)!</math>, co dowodzi punktu drugiego.
  
Liczba <math>\left[\begin{array} {c}n\\ 1\end{array} \right]</math> opisuje permutacje o jednym cyklu.
+
Liczba <math>\left[\begin{array} {c}n\\ n-1\end{array} \right]</math> opisuje permutacje o <math>n-1</math> cyklach. Permutacja taka musi wiec być typu <math>[1^{n-2}2^1]</math>, 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 <math>2</math>-elementowych, czyli <math>{n\choose2}</math>, co dowodzi punktu trzeciego.
Każda taka permutacja jest zadana wzorcem
 
<math>(\underbrace{\bullet,\ldots,\bullet}_{n\ pozycji})</math>.
 
Wzorzec taki może być wypełniony <math>n</math>-elementami na <math>n!</math> sposobów.  
 
Ale ten sam cykl ma wiele opisów różniących się jedynie przesunięciem.  
 
Zatem każdy <math>n</math>-elementowy cykl może być zapisany według takiego wzorca
 
na <math>n</math> sposobów,  
 
czyli liczba cykli na zbiorze <math>n</math>-elementowym to <math>\frac{n!}{n}=(n-1)!</math>,  
 
co dowodzi punktu drugiego.
 
  
Liczba <math>\left[\begin{array} {c}n\\ n-1\end{array} \right]</math> opisuje permutacje o <math>n-1</math> cyklach.
+
Dla dowodu punktu czwartego zauważmy jedynie, że jedyną permutacją o <math>n</math> cyklach na zbiorze <math>n</math>-elementowym jest identyczność.
Permutacja taka musi wiec być typu <math>[1^{n-2}2^1]</math>, 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 <math>2</math>-elementowych,
 
czyli <math>{n\choose2}</math>, co dowodzi punktu trzeciego.
 
  
Dla dowodu punktu czwartego zauważmy jedynie,
+
Równie łatwo jest stwierdzić, że zbiór <math>n</math>-elementowy nie może być podzielony na więcej niż <math>n</math> niepustych części (mających stanowić cykle).
że jedyną permutacją o <math>n</math> cyklach na zbiorze <math>n</math>-elementowym jest identyczność.
 
 
 
Równie łatwo jest stwierdzić, że zbiór <math>n</math>-elementowy  
 
nie może być podzielony na więcej niż <math>n</math> niepustych części (mających stanowić cykle).
 
 
}}
 
}}
  
Liczby Stirlinga dla cykli, podobnie jak współczynniki dwumianowe,  
+
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.
można generować używając zależności rekurencyjnej.  
 
Na jej podstawie można zbudować Trójkąt Stirlinga dla cykli.
 
  
{{obserwacja|||
+
{{obserwacja|6.11|obs 6.11|
 +
Dla <math>0<k\leqslant n</math>
  
Dla <math>0<k\leq n</math>
 
  
 
<center><math>\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].
 
<center><math>\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].
 
</math></center>
 
</math></center>
 +
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 
+
Niech <math>x</math> będzie wyróżnionym i ustalonym elementem  <math>n</math>-elementowego zbioru <math>X</math>. Permutacje zbioru <math>X</math> o <math>k</math> cyklach można podzielić na dwa typy, w których:
Niech <math>x</math> będzie wyróżnionym i ustalonym elementem  <math>n</math>-elementowego zbioru <math>X</math>.
 
Permutacje zbioru <math>X</math> o <math>k</math> cyklach można podzielić na dwa typy, w których:
 
 
 
 
* <math>x</math> stanowi jednoelementowy cykl,
 
* <math>x</math> stanowi jednoelementowy cykl,
 
 
* <math>x</math> jest w cyklu co najmniej <math>2</math>-elementowym.
 
* <math>x</math> jest w cyklu co najmniej <math>2</math>-elementowym.
  
W pierwszym przypadku pozostałe <math>n-1</math> elementów zbioru <math>X</math>  
+
W pierwszym przypadku pozostałe <math>n-1</math> elementów zbioru <math>X</math> muszą uformować <math>k-1</math> cykli, co jest możliwe na  
muszą uformować <math>k-1</math> cykli, co jest możliwe na  
+
<math>\left[\begin{array} {c}n-1\\ k-1\end{array} \right]</math> sposobów. W drugim przypadku, po usunięciu elementu <math>x</math> permutacje badanego typu wciąż będą mieć <math>k</math> cykli. Jest ich zatem tyle, co permutacji <math>(n-1)</math>-elementowego zbioru o <math>k</math> cyklach, czyli <math>\left[\begin{array} {c}n-1\\ k\end{array} \right]</math>. Element <math>x</math> może rozbudować każdą permutację zbioru <math>X-{\left\{ {x} \right\} }n-1</math> sposobów (wchodząc do cyklu jako następnik jednego z <math>n-1</math> elementów). Zatem permutacji drugiego typu jest dokładnie <math>(n-1)\left[\begin{array} {c}n-1\\ k\end{array} \right]</math>.  
<math>\left[\begin{array} {c}n-1\\ k-1\end{array} \right]</math> sposobów.  
 
W drugim przypadku, po usunięciu elementu <math>x</math> permutacje badanego typu wciąż będą mieć  
 
<math>k</math> cykli.  
 
Jest ich zatem tyle, co permutacji <math>(n-1)</math>-elementowego zbioru o <math>k</math> cyklach,  
 
czyli <math>\left[\begin{array} {c}n-1\\ k\end{array} \right]</math>.  
 
Element <math>x</math> może rozbudować każdą permutację zbioru <math>X-{\left\{ {x} \right\}\ }n-1</math> sposobów (wchodząc do cyklu jako następnik jednego z <math>n-1</math> elementów).  
 
Zatem permutacji drugiego typu jest dokładnie <math>(n-1)\left[\begin{array} {c}n-1\\ k\end{array} \right]</math>.  
 
 
}}
 
}}
  
''Rysunek:'' 5.6 Szkic na kartce
+
[[File:MD1-5-6.svg|350x300px|thumb|right|MD1-5-6.swf]]
  
W Trójkącie Stirlinga dla cykli,  
+
W Trójkącie Stirlinga dla cykli, <math>n</math>-ty wiersz zawiera liczby permutacji zbioru <math>n</math>-elementowego o kolejno <math>0,1,\ldots,n</math> cyklach. Zatem suma wszystkich tych wartości  
<math>n</math>-ty wiersz zawiera liczby permutacji zbioru <math>n</math>-elementowego o kolejno  
+
to liczba wszystkich permutacji zbioru <math>n</math>-elementowego, czyli <math>n!</math>. Dostajemy stąd natychmiast:
<math>0,1,\ldots,n</math> cyklach.  
 
Zatem suma wszystkich tych wartości  
 
to liczba wszystkich permutacji zbioru <math>n</math>-elementowego, czyli <math>n!</math>.
 
Dostajemy stąd natychmiast:
 
  
{{obserwacja|||
+
{{obserwacja|6.12|obs 6.12|
 
Dla <math>n\in\mathbb{N}</math>
 
Dla <math>n\in\mathbb{N}</math>
  
<center><math>\sum_{i=0}^n\left[\begin{array} {c}n\\ i\end{array} \right]=n!
+
 
</math></center>
+
<center>
 +
<math>\displaystyle\sum_{i=0}^n\left[\begin{array} {c}n\\ i\end{array} \right]=n!
 +
</math>
 +
</center>
 +
 
  
 
}}
 
}}
  
Ciekawy jest nastepujacy związek liczb Stirlinga dla cykli  
+
Ciekawy jest nastepujacy związek liczb Stirlinga dla cykli z liczbami harmonicznymi <math>H_n</math>.
z liczbami harmonicznymi <math>H_n</math>.
+
 
 +
{{obserwacja|6.13|obs 6.13|
 +
Dla <math>n\in\mathbb{N}</math>
  
{{obserwacja|||
 
  
Dla <math>n\in\mathbb{N}</math>
+
<center>
 +
<math>\displaystyle \sum_{i=0}^ni\left[\begin{array} {c}n\\ i\end{array} \right]=n!H_n.</math>
 +
</center>
  
<center><math>\sum_{i=0}^ni\left[\begin{array} {c}n\\ i\end{array} \right]=n!H_n.
 
</math></center>
 
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 +
Dla <math>n=0</math> tożsamość jest oczywista, a dla <math>n>0</math> przybiera postać <math>\displaystyle \sum_{i=1}^ni\left[\begin{array} {c}n\\ i\end{array} \right]=n!H_n</math> Pokażemy że obydwie liczby z naszej obserwacji to
 +
sumaryczna liczba cykli we wszystkich permutacjach zbioru <math>n</math>-elementowego, tzn. <math>\displaystyle \sum_{\sigma\in S_n} c(\sigma)</math>.
 +
* Permutacji o <math>i</math> cyklach jest dokładnie <math>\left[\begin{array} {c}n\\ i\end{array} \right]</math>. W sumie permutacje o <math>i</math> cyklach mają więc <math>i\cdot\left[\begin{array} {c}n\\ i\end{array} \right]</math> cykli, czyli <math>\displaystyle \displaystyle \sum_{\sigma\in S_n} c(\sigma)= \sum_{i=1}^ni\left[\begin{array} {c}n\\ i\end{array} \right]</math>.
 +
* Zliczymy najpierw <math>i</math>-elementowe cykle zbudowane z elementów zbioru <math>n</math>-elementowego. Każdy taki cykl jest wyznaczony przez wypełnienie wzorca <math>(\underbrace{\bullet,\ldots,\bullet}_{i\ pozycji})</math>, ale z dokładnością do przesunięcia. Wypełnień jest oczywiście tyle, ile injekcji postaci <math>\mathbb{Z}_i\longrightarrow\mathbb{Z}_n</math>,
 +
czyli <math>n\cdot(n-1\cdot\ldots\cdot(n-i+1))=n^{\underline{i}}</math>. Zatem zliczanych cykli <math>i</math>-elementowych jest dokładnie <math>\frac{n^{\underline{i}}}{i}</math> .
  
Dla <math>n=0</math> tożsamość jest oczywista, a dla <math>n>0</math> przybiera postać
+
Każdy cykl <math>i</math>-elementowy występuje w dokładnie <math>(n-i)!</math> permutacjach zbioru <math>n</math>-elementowego, gdyż tyle jest permutacji pozostałych <math>n-i</math> elementów. Zatem sumaryczna liczba cykli we wszystkich permutacjach zbioru <math>n</math>-elementowego wynosi:
<math>\sum_{i=1}^ni\left[\begin{array} {c}n\\ i\end{array} \right]=n!H_n</math>
 
Pokażemy że obydwie liczby z naszej obserwacji to
 
sumaryczna liczba cykli we wszystkich permutacjach  
 
zbioru <math>n</math>-elementowego, tzn. <math>\sum_{\sigma\in S_n} c(\sigma)</math>.
 
  
* Permutacji o <math>i</math> cyklach jest dokładnie <math>\left[\begin{array} {c}n\\ i\end{array} \right]</math>.
 
W sumie permutacje o <math>i</math> cyklach mają więc <math>i\cdot\left[\begin{array} {c}n\\ i\end{array} \right]</math> cykli,
 
czyli <math>\sum_{\sigma\in S_n} c(\sigma)= \sum_{i=1}^ni\left[\begin{array} {c}n\\ i\end{array} \right]</math>.
 
  
* Zliczymy najpierw <math>i</math>-elementowe cykle
+
<center>
zbudowane z elementów zbioru <math>n</math>-elementowego.
+
<math>\displaystyle \sum_{\sigma\in S_n} c(\sigma)
Każdy taki cykl jest wyznaczony przez wypełnienie wzorca
 
<math>(\underbrace{\bullet,\ldots,\bullet}_{i\ pozycji})</math>,
 
ale z dokładnością do przesunięcia.
 
Wypełnień jest oczywiście tyle, ile injekcji postaci <math>\mathbb{Z}_i\longrightarrow\mathbb{Z}_n</math>,
 
czyli <math>n\cdot(n-1\cdot\ldots\cdot(n-i+1))=n^{\underline{i}}</math>.
 
Zatem zliczanych cykli <math>i</math>-elementowych jest dokładnie <math>\frac{n^{\underline{i}}}{i}</math> .
 
 
 
Każdy cykl <math>i</math>-elementowy występuje w dokładnie
 
<math>(n-i)!</math> permutacjach zbioru <math>n</math>-elementowego, gdyż tyle jest permutacji pozostałych
 
<math>n-i</math> elementów.
 
Zatem sumaryczna liczba cykli we wszystkich permutacjach zbioru <math>n</math>-elementowego
 
wynosi:
 
 
 
<center><math>\sum_{\sigma\in S_n} c(\sigma)
 
 
=\sum_{i=1}^n\frac{n^{\underline{i}}}{i}(n-i)!
 
=\sum_{i=1}^n\frac{n^{\underline{i}}}{i}(n-i)!
 
=\sum_{i=1}^n\frac{n!}{i}=n!H_n.
 
=\sum_{i=1}^n\frac{n!}{i}=n!H_n.
</math></center>
+
</math>
 +
</center>
 +
 
  
 
}}
 
}}
  
 
W liczbach Stirlinga <math>\left[\begin{array} {c}n\\ k\end{array} \right]</math> dla cykli wypełnialiśmy wzorce postaci:
 
W liczbach Stirlinga <math>\left[\begin{array} {c}n\\ k\end{array} \right]</math> dla cykli wypełnialiśmy wzorce postaci:
 +
  
 
<center><math>\underbrace{(\bullet,\ldots,\bullet)(\bullet,\ldots,\bullet) \ldots (\bullet,\ldots,\bullet)}_{k \ cykli, \ w \ sumie \ o \ n \ miejscach}
 
<center><math>\underbrace{(\bullet,\ldots,\bullet)(\bullet,\ldots,\bullet) \ldots (\bullet,\ldots,\bullet)}_{k \ cykli, \ w \ sumie \ o \ n \ miejscach}
 
</math></center>
 
</math></center>
 +
  
 
w sposób injektywny i z dokładnością do:  
 
w sposób injektywny i z dokładnością do:  
 
 
* kolejności cykli,
 
* kolejności cykli,
 +
* przesunięć cyklicznych w każdym z <math>k</math> cykli.
  
* przesunięć cyklicznych w każdym z <math>k</math> cykli.
+
Jeśli zupełnie zaniedbamy kolejność elementów w cyklach, dostaniemy wzorzec:
  
Jeśli zupełnie zaniedbamy kolejność elementów w cyklach,
 
dostaniemy wzorzec:
 
  
<center><math>\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},
+
<center><math>\underbrace{\{\bullet,\ldots,\bullet\} \{\bullet,\ldots,\bullet \} \ldots \{\bullet,\ldots,\bullet\}}_{ k\ zbiorow\ w\ sumie\ o\ n\ miejscach}</math></center>
</math></center>
 
  
czyli podział zbioru <math>n</math>-elementowego na <math>k</math> parami rozłącznych podzbiorów.
 
W podziale, podzbiory takie nazywamy blokami.
 
Przypomnijmy, że podział zbioru <math>X</math> na <math>k</math> bloków
 
wyznacza relację równoważności na zbiorze <math>X</math>
 
o <math>k</math> klasach równoważności.
 
  
'''Liczba Stirlinga dla podziałów''' <math>\left\{\begin{array} {c}n\\ k\end{array} \right\}\$
+
czyli podział zbioru <math>n</math>-elementowego na <math>k</math> parami rozłącznych podzbiorów. W podziale, podzbiory takie nazywamy blokami. Przypomnijmy, że podział zbioru <math>X</math> na <math>k</math> bloków wyznacza relację równoważności na zbiorze <math>X</math> o <math>k</math> klasach równoważności.
(często nazywana liczbą Stirlinga drugiego rodzaju)
 
to liczba podziałów zbioru </math>n<math>-elementowego na dokładnie </math>k<math> bloki.  
 
Znów przyjmujemy, że </math> {c}0<br> 0 1<math> oraz
 
</math> {c}n<br> k 0<math> dla </math>k<0<math>.
 
  
{{przyklad|||
+
{{kotwica|lstirlpodzial|'''Liczba Stirlinga dla podziałów'''}}<math>\left\{\begin{array} {c}n\\ k\end{array} \right\}</math> (często nazywana liczbą Stirlinga drugiego rodzaju) to liczba podziałów zbioru <math>n</math>-elementowego na dokładnie <math>k</math> bloki. Znów przyjmujemy, że <math>\left\{\begin{array} {c}0\\ 0\end{array} \right\}=1</math> oraz <math>\left\{\begin{array} {c}n\\ k\end{array} \right\}=0</math> dla <math>k<0</math>.
Lista podziałów </math>{Z}_4<math> na dwa bloki:
 
  
</math></center> {cc}
+
[[File:MD1-5-7.svg|250x250px|thumb|right|MD1-5-7.swf]]
{ {0,1,2} }{ {3} }&{ {0,1} }{ {2,3} }<br>
 
{ {0,1,3} }{ {2} }&{ {0,2} }{ {1,3} }<br>
 
{ {0,2,3} }{ {1} }&{ {0,3} }{ {1,2} }<br>
 
{ {1,2,3} }{ {0} }
 
  
<center><math>
+
{{przyklad|||
 +
Lista podziałów <math>\mathbb{Z}_4</math> na dwa bloki:
  
\medskip\noindent\textit{Rysunek:} 5.7 Szkic na kartce.\medskip
+
<center>
 +
<math>\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}
 +
</math>
 +
</center>
  
* Mamy </math>7<math> podziałów zbioru </math>{Z}_4<math> na dwa bloki,  
+
* Mamy <math>7</math> podziałów zbioru <math>\mathbb{Z}_4</math> na dwa bloki,
zatem </math> {c}4<br> 2 7<math>.
+
zatem <math>\left\{\begin{array} {c}4\\ 2\end{array} \right\}=7</math>.
  
 
}}
 
}}
  
{{obserwacja|||
+
{{obserwacja|6.14|obs 6.14|
 
+
Dla <math>n,k\in\mathbb{N}</math>
Dla </math>n,k{N}<math>
+
* <math>\left\{\begin{array} {c}n\\ k\end{array} \right\} \leqslant \left[\begin{array} {c}n\\ k\end{array} \right]</math>,
 
+
* <math>\left\{\begin{array} {c}n\\ 0\end{array} \right\}=0</math>, dla <math>n>0</math>,
* </math> {c}n<br> k [ {c}n<br> k ]<math>,
+
* <math>\left\{\begin{array} {c}n\\ 1\end{array} \right\}=1</math>, dla <math>n>0</math>,
 
+
* <math>\left\{\begin{array} {c}n\\ 2\end{array} \right\}=2^{n-1}-1</math>, dla <math>n>0</math>,
* </math> {c}n<br> 0 0<math>, dla </math>n>0<math>,
+
* <math>\left\{\begin{array} {c}n\\ n-1\end{array} \right\}={n\choose2}</math>,
 
+
* <math>\left\{\begin{array} {c}n\\ n\end{array} \right\}=1</math>,
* </math> {c}n<br> 1 1<math>, dla </math>n>0<math>,
+
* <math>\left\{\begin{array} {c}n\\ k\end{array} \right\}=0</math>, dla <math>k>n</math>.
 
 
* </math> {c}n<br> 2 2^{n-1}-1<math>, dla </math>n>0<math>,
 
 
 
* </math> {c}n<br> n-1 {n}<math>,
 
 
 
* </math> {c}n<br> n 1<math>,
 
 
 
* </math> {c}n<br> k 0<math>, dla </math>k>n<math>.
 
  
 
}}
 
}}
  
 
{{dowod|||
 
{{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,
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.
 
ale po zaniedbaniu kolejności elementów.
  
Drugi punkt to stwierdzenie, że niepusty zbiór nie może zostać podzielony na </math>0<math> bloków.
+
Drugi punkt to stwierdzenie, że niepusty zbiór nie może zostać podzielony na <math>0</math> bloków.
  
Trzeci punkt orzeka, że jest tylko jeden podział niepustego zbioru na jeden blok --
+
Trzeci punkt orzeka, że jest tylko jeden podział niepustego zbioru na jeden blok - blok ten musi być całym dzielonym zbiorem.
blok ten musi być całym dzielonym zbiorem.
 
  
Dla dowodu czwartego załóżmy, że </math><nowiki>=</nowiki>n<math> i niech </math>x X<math>.
+
Dla dowodu czwartego załóżmy, że <math>\left\vert X\right\vert=n</math> i niech <math>x\in X</math>. 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 <math>x</math>. Element <math>x</math> może stanowić blok z dowolnym podzbiorem pozostałego <math>(n-1)</math>-elementowego zbioru <math>X-{\left\{ {x} \right\} }</math> poza podzbiorem pełnym, gdyż wtedy drugi blok byłby pusty. Zatem jest dokładnie <math>2^{n-1}-1</math> możliwości wyboru bloku dla <math>x</math>,  
Zauważmy, że podział na dwa bloki jest zdeterminowany jednym z tych bloków  
+
i tym samym tyleż jest podziałów <math>X</math>.
-- drugi to po prostu dopełnienie pierwszego.  
 
Niech więc blokiem determinującym podział, będzie blok zawierający </math>x<math>.  
 
Element </math>x<math> może stanowić blok z dowolnym podzbiorem pozostałego  
 
</math>(n-1)<math>-elementowego zbioru </math>X-{ {x} }<math> poza podzbiorem pełnym,  
 
gdyż wtedy drugi blok byłby pusty.  
 
Zatem jest dokładnie </math>2^{n-1}-1<math> możliwości wyboru bloku dla </math>x<math>,  
 
i tym samym tyleż jest podziałów </math>X<math>.
 
  
Dowody pozostałych trzech własności można przeprowadzić jak  
+
Dowody pozostałych trzech własności można przeprowadzić jak dla liczb Stirlinga dla cykli.
dla liczb Stirlinga dla cykli.
 
 
}}
 
}}
  
Liczby Stirlinga dla podziałów, podobnie jak współczynniki dwumianowe,  
+
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.
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|||
+
{{obserwacja|6.15|obs 6.15|
 +
Dla <math>0<k\leqslant n</math>
  
Dla </math>0<k n</center> {c}n<br> k
 
<nowiki>=</nowiki>k {c}n-1<br> k  {c}n-1<br> k-1
 
<center><math>
 
  
}}
+
<center><math>\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\}.
 +
</math></center>
  
{{dowod|||
 
  
Niech, jak zwykle, </math><nowiki>=</nowiki>n<math> i niech </math>x X<math> będzie ustalonym elementem.
+
}}
Znów, podziały zbioru </math>X<math> na </math>k<math> bloków można podzielić na dwa typy:
 
  
* </math>{ {x} }<math> stanowi blok jednoelementowy,
+
[[File:MD1-5-8.svg|350x300px|thumb|right|MD1-5-8.swf]]
  
* </math>x<math> jest w bloku co najmniej dwuelementowym.
+
{{dowod|||
 +
Niech, jak zwykle, <math>\left\vert X\right\vert=n</math> i niech <math>x\in X</math> będzie ustalonym elementem. Znów, podziały zbioru <math>X</math> na <math>k</math> bloków można podzielić na dwa typy:
 +
* <math>{\left\{ {x} \right\} }</math> stanowi blok jednoelementowy,
 +
* <math>x</math> jest w bloku co najmniej dwuelementowym.
  
 
Każdy podział pierwszego typu jest jednoznacznie wyznaczony przez  
 
Każdy podział pierwszego typu jest jednoznacznie wyznaczony przez  
</math>(n-1)<math>-elementowego zbioru </math>X-{ {x} }<math> na </math>k-1<math> bloków.  
+
<math>(n-1)</math>-elementowego zbioru <math>X-{\left\{ {x} \right\} }</math> na <math>k-1</math> bloków. Jest ich więc dokładnie <math>\left\{\begin{array} {c}n-1\\ k-1\end{array} \right\}</math>. W drugim przypadku pozostałe elementy dzielone są wciąż na <math>k</math> bloków. Można taki podział wykonać na <math>\left\{\begin{array} {c}n-1\\ k\end{array} \right\}</math> sposobów. Element <math>x</math> może rozszerzyć każdy taki podział zbioru math>X</math> do podziału zbioru <math>X</math> na <math>k</math> sposobów wchodząc do któregoś z <math>k</math> bloków. Zatem jest dokładnie <math>k\left\{\begin{array} {c}n-1\\ k\end{array} \right\}</math> podziałów drugiego typu.  
Jest ich więc dokładnie </math> {c}n-1<br> k-1 .  
 
W drugim przypadku pozostałe elementy dzielone są wciąż na <math>k</math> bloków.  
 
Można taki podział wykonać na <math>\left\{\begin{array} {c}n-1\\ k\end{array} \right\}\$ sposobów.  
 
Element </math>x<math> może rozszerzyć każdy taki podział zbioru </math>X<math> do podziału zbioru </math>X<math>  
 
na </math>k<math> sposobów wchodząc do któregoś z </math>k<math> bloków.  
 
Zatem jest dokładnie </math>k {c}n-1<br> podziałów drugiego typu.  
 
 
}}
 
}}
  
Obserwacja [[##obserwacja - rekursja Stirlinga dla podzialow|Uzupelnic obserwacja - rekursja Stirlinga dla podzialow|]]  
+
[[#obs_6.15|Obserwacja 6.15]] pozwala na szybką konstrukcję Trójkąta Stirlinga dla podziałów.
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 <math>X \longrightarrow Y</math> wyznacza podział zbioru <math>X</math> na <math>\left\vert Y\right\vert</math> bloków. Nie dziwi więc następujący związek z liczbami Stirlinga dla podziałów.
  
Kilka wykładów wcześniej wskazaliśmy
+
{{obserwacja|6.16|obs 6.16|
liczbę funkcji,
+
Dla skończonych zbiorów <math>X,Y</math> liczba surjekcji <math>X\longrightarrow Y</math> wynosi <math>\left\vert Y\right\vert!\cdot\left\{\begin{array} {c}\left\vert X\right\vert\\ \left\vert Y\right\vert\end{array} \right\}</math>.
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 <math>X \longrightarrow Y</math> wyznacza podział zbioru <math>X</math>
 
na <math>\left\vertY\right\vert</math> bloków.
 
Nie dziwi więc następujący związek z liczbami Stirlinga dla podziałów.
 
 
 
{{obserwacja|||
 
 
 
Dla skończonych zbiorów <math>X,Y</math> liczba surjekcji <math>X\longrightarrow Y</math>  
 
wynosi <math>\left\vertY\right\vert!\cdot\left\{\begin{array} {c}\left\vertX\right\vert\\ \left\vertY\right\vert\end{array} \right\}\$.
 
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 
+
Niech <math>Y={\left\{ {y_0,\ldots,y_{m-1}} \right\} }</math>. Jak już zauważyliśmy, surjekcja postaci <math>f:X \longrightarrow Y</math> wyznacza pewien podział zbioru <math>X</math> dodatkowo poetykietowany elementami zbioru <math>X</math> na <math>m=\left\vert Y\right\vert</math> bloków <math>f^{-1}({\left\{ {y_0} \right\} }), \ldots, f^{-1}({\left\{ {y_{m-1}} \right\} })</math>. Nieetykietowanych podziałów jest oczywiście <math>\left\{\begin{array} {c}\left\vert X\right\vert\\ \left\vert Y\right\vert\end{array} \right\}</math>. Ponieważ każdy podział może być poetykietowany na <math>\left\vert Y\right\vert!</math> sposobów, możemy zakończyć dowód.
Niech </math>Y<nowiki>=</nowiki>{ {y_0,...,y_{m-1}} }<math>.
 
Jak już zauważyliśmy,  
 
surjekcja postaci </math>f:X Y<math> wyznacza pewien podział zbioru </math>X<math> dodatkowo
 
poetykietowany elementami zbioru </math>X<math>
 
na </math>m<nowiki>=</nowiki><math> bloków </math>f^{-1}({ {y_0} }), ..., f^{-1}({ {y_{m-1}} })<math>.
 
Nieetykietowanych podziałów jest oczywiście </math> {c}<br> .
 
Ponieważ każdy podział może być poetykietowany na <math>\left\vertY\right\vert!</math> sposobów,  
 
możemy zakończyć dowód.
 
 
}}
 
}}
  
{{obserwacja|||
+
{{obserwacja|6.17|obs 6.17|
 +
Dla <math>n,k\in\mathbb{N}</math>
  
Dla <math>n,k\in\mathbb{N}</math>
 
  
<center><math>\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}.
+
<center><math>\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}.
 
</math></center>
 
</math></center>
 +
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 
+
Niech <math>\left\vert X\right\vert=n</math>. Pojedynczy składnik <math>{n\choose i_{k-1}}{i_{k-1}\choose i_{k-2}}\ldots{i_1\choose i_0}</math>
Niech <math>\left\vertX\right\vert=n</math>.
+
rozważanej sumy to liczba wyborów ciągu zbiorów <math>X\supsetneq A_{k-1}\supsetneq\ldots\supsetneq A_1\supsetneq A_{0}</math>, odpowiednio <math>i_{k-1}>\ldots>i_1>i_0</math> elementowych. Rzeczywiście <math>A_{i_{k-1}}\subsetneq X</math> możemy wybrać na <math>{n\choose i_{k-1}}</math> sposobów,  
Pojedynczy składnik <math>{n\choose i_{k-1}}{i_{k-1}\choose i_{k-2}}\ldots{i_1\choose i_0}</math>
+
<math>A_{i_k-2}\subsetneq A_{i_k-1}</math> na <math>{i_{k-1}}\choose i_{k-2}</math> sposobów itd. Każdy taki ciąg zbiorów odpowiada jednoznacznie ciągowi <math>k+1</math> bloków <math>\left\langle B_0,\ldots,B_k \right\rangle</math>, gdzie <math>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}</math>. W podziale nie jest jednak istotne uporządkowanie bloków <math>B_0,\ldots,B_k</math>, co oznacza, że powinniśmy przejść od ciągu <math>\left\langle B_0,\ldots,B_k \right\rangle</math> do rodziny bloków <math>{\left\{ {B_0,\ldots,B_k} \right\} }</math>, wydzielając tym samym każdy składnik sumy przez <math>(k+1)!</math>. Tak wydzielona suma to nic innego jak liczba podziałów zbioru <math>n</math>-elementowego na <math>k+1</math> bloków, czyli <math>\left\{\begin{array} {c}n\\ k+1\end{array} \right\}</math>.
rozważanej sumy to liczba wyborów ciągu zbiorów  
 
<math>X\supsetneq A_{k-1}\supsetneq\ldots\supsetneq A_1\supsetneq A_{0}</math>,  
 
odpowiednio <math>i_{k-1}>\ldots>i_1>i_0</math> elementowych.  
 
Rzeczywiście <math>A_{i_{k-1}}\subsetneq X</math> możemy wybrać na <math>{n\choose i_{k-1}}</math> sposobów,  
 
<math>A_{i_k-2}\subsetneq A_{i_k-1}</math> na <math>{i_{k-1}}\choose i_{k-2}</math> sposobów itd.  
 
Każdy taki ciąg zbiorów odpowiada jednoznacznie ciągowi <math>k+1</math> bloków  
 
<math>\left\langle B_0,\ldots,B_k \right\rangle</math>,  
 
gdzie <math>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}</math>.  
 
W podziale nie jest jednak istotne uporządkowanie bloków <math>B_0,\ldots,B_k</math>,  
 
co oznacza, że powinniśmy przejść od ciągu <math>\left\langle B_0,\ldots,B_k \right\rangle</math>  
 
do rodziny bloków <math>{\left\{ {B_0,\ldots,B_k} \right\}\ }</math>,  
 
wydzielając tym samym każdy składnik sumy przez <math>(k+1)!</math>.
 
Tak wydzielona suma to nic innego jak  
 
liczba podziałów zbioru <math>n</math>-elementowego na <math>k+1</math> bloków,  
 
czyli <math>\left\{\begin{array} {c}n\\ k+1\end{array} \right\}\$.
 
 
}}
 
}}
  
 
{{przyklad|||
 
{{przyklad|||
  
</math></center> {c}n<br> 3  
+
 
&<nowiki>=</nowiki>&{1}{3!}_{0<j<i<n}{n i}{i j}
+
<center><math>\begin{align} \left\{\begin{array} {c}n\\ 3\end{array} \right\}
<nowiki>=</nowiki>{1}{6}_{0<i<n}{n i}_{0<j<i}{i j}<br>
+
&=\frac{1}{3!}\sum_{0<j<i<n}{n\choose i}{i\choose j}
&<nowiki>=</nowiki>&{1}{6}_{0<i<n}{n i}(2^i-2)
+
=\frac{1}{6}\sum_{0<i<n}{n\choose i}\sum_{0<j<i}{i\choose j}\\
<nowiki>=</nowiki>{1}{6}_{0<i<n}{n i}2^i-{1}{3}_{0<i<n}{n i}<br>
+
&=\frac{1}{6}\sum_{0<i<n}{n\choose i}(2^i-2)
&<nowiki>=</nowiki>&{1}{6}(3^n-1-2^n)-{1}{3}(2^n-2)
+
=\frac{1}{6}\sum_{0<i<n}{n\choose i}2^i-\frac{1}{3}\sum_{0<i<n}{n\choose i}\\
<nowiki>=</nowiki>{3^{n-1}+1}{2}-2^{n-1}
+
&=\frac{1}{6}(3^n-1-2^n)-\frac{1}{3}(2^n-2)
<center><math>
+
=\frac{3^{n-1}+1}{2}-2^{n-1}
 +
\end{align}</math></center>
 +
 
  
 
}}
 
}}
Linia 870: Linia 632:
 
===Liczby Bella===
 
===Liczby Bella===
  
W Trójkącie Pascala </math>n<math>-ty wiersz sumuje się do  
+
[[grafika:Bell-portret.jpeg|thumb|right||Eric Temple Bell (1883-1960) <br>[[Biografia Bell|Zobacz biografię]]]]W Trójkącie Pascala <math>n</math>-ty wiersz sumuje się do  
liczby podzbiorów zbioru </math>n<math>-elementowego, czyli do </math>2^n<math>.  
+
liczby podzbiorów zbioru <math>n</math>-elementowego, czyli do <math>2^n</math>.  
W Trójkąta Stirlinga dla cykli </math>n<math>-ty wiersz sumuje się do  
+
W Trójkąta Stirlinga dla cykli <math>n</math>-ty wiersz sumuje się do  
liczby permutacji zbioru </math>n<math>-elementowego, czyli do </math>n!<math>.  
+
liczby permutacji zbioru <math>n</math>-elementowego, czyli do <math>n!</math>.  
Zajmiemy się teraz sumą </math>n<math>-tego wiersza Trójkąta Stirlinga dla podziałów.
+
Zajmiemy się teraz sumą <math>n</math>-tego wiersza Trójkąta Stirlinga dla podziałów.
Oczywiście suma taka to liczba wszystkich podziałów zbioru </math>n<math> elementowego,  
+
Oczywiście suma taka to liczba wszystkich podziałów zbioru <math>n</math> elementowego,  
lub inaczej liczby wszystkich relacji równoważności na zbiorze </math>n<math>-elementowym.
+
lub inaczej liczby wszystkich relacji równoważności na zbiorze <math>n</math>-elementowym.
  
\noindent
 
\textbf{\underline{Liczba Bella}} </math>B_n<math>
 
\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 </math>n<math>-elementowego, czyli
 
  
</math></center>B_n<nowiki>=</nowiki>_{i<nowiki>=</nowiki>0}^n {c}n<br> i
+
{{kotwica|lbella|'''Liczba Bella'''}} <math>B_n</math>  
<center><math>
 
  
Lista kilku pierwszych liczb Bella:
+
to liczba podziałów zbioru <math>n</math>-elementowego, czyli
  
</math></center> {|c||c|c|c|c|c|c|c|c|c|c|c|c}
 
  
<hr>
+
<center>
 +
<math>\displaystyle B_n=\sum_{i=0}^n\left\{\begin{array} {c}n\\ i\end{array} \right\}.
 +
</math>
 +
</center>
  
n&0&1&2&3&4&5&6&7&8&9&10&...<br>
 
  
<hr>
+
Lista kilku pierwszych liczb Bella:
  
B_n&1&1&2&5&15&52&203&877&4140&21147&115975&...<br>
 
  
<hr>
+
<center><math>\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}
 +
</math></center>
  
<center><math>
 
  
 
Liczby Bella spełniają piękną zależność rekurencyjną:
 
Liczby Bella spełniają piękną zależność rekurencyjną:
  
{{obserwacja|||
+
{{obserwacja|6.18|obs 6.18|
 +
 
 +
 
 +
<center><math>\displaystyle B_{n+1}=\sum_{i=0}^n{n\choose i}B_i.
 +
</math></center>
  
</math></center>B_{n+1}<nowiki>=</nowiki>_{i<nowiki>=</nowiki>0}^n{n i}B_i.
 
<center><math>
 
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 +
Wybierzmy i ustalmy w <math>(n+1)</math>-elementowym zbiorze <math>X</math> pewien element <math>x\in X</math>. Policzmy teraz ile jest podziałów zbioru <math>X</math> takich, że blok zawierający <math>x</math> ma dokładnie <math>i+1</math> elementów.
 +
Oczywiście pozostałe <math>i</math> elementów tego bloku może zostać wybranych
 +
ze zbioru <math>X-{x}</math> na <math>{n\choose i}</math> sposobów.
 +
Każdy taki blok możemy rozbudować do podziału zbioru <math>X</math> poprzez podzielenie pozostałych
 +
<math>n-i</math>  na bloki.
 +
Podział taki jest oczywiście możliwy na <math>B_{n-i}</math> sposobów, skąd
 +
sumując po wszystkich możliwych wartościach <math>i</math> otrzymujemy
 +
  
Wybierzmy i ustalmy w </math>(n+1)<math>-elementowym zbiorze </math>X<math> pewien element </math>x X<math>.
+
<center><math>\displaystyle B_{n+1}=\sum_{i=0}^n{n\choose i}B_{n-i}=\sum_{i=0}^n{n\choose i}B_i.</math></center>
Policzmy teraz ile jest podziałów zbioru </math>X<math> takich, że
 
blok zawierający </math>x<math> ma dokładnie </math>i+1<math> elementów.
 
Oczywiście pozostałe </math>i<math> elementów tego bloku może zostać wybranych
 
ze zbioru </math>X-{x}<math> na </math>{n i}<math> sposobów.
 
Każdy taki blok możemy rozbudować do podziału zbioru </math>X<math> poprzez podzielenie pozostałych
 
</math>n-i<math>  na bloki.
 
Podział taki jest oczywiście możliwy na </math>B_{n-i}<math> sposobów, skąd
 
sumując po wszystkich możliwych wartościach </math>i<math> otrzymujemy
 
  
</math></center>B_{n+1}<nowiki>=</nowiki>_{i<nowiki>=</nowiki>0}^n{n i}B_{n-i}<nowiki>=</nowiki>_{i<nowiki>=</nowiki>0}^n{n i}B_i.
 
<center><math>
 
  
 
}}
 
}}
Linia 931: Linia 693:
 
===Bazy przestrzeni wielomianów===
 
===Bazy przestrzeni wielomianów===
  
Przestrzeń wektorowa </math>{R}[x]<math> wszystkich wielomianów jednej zmiennej rzeczywistej </math>x<math>
+
Przestrzeń wektorowa <math>\mathbb{R}[x]</math> wszystkich wielomianów jednej zmiennej rzeczywistej <math>x</math> ma naturalną bazę złożoną z jednomianów
ma naturalną bazę złożoną z jednomianów
 
  
</math></center>1,x,x^2,x^3,...
 
<center><math>
 
  
W \underline{różnicowym odpowiedniku Twierdzenia Taylora}  
+
<center><math>1,x,x^2,x^3,\ldots
widzieliśmy (bez dowodu), że każdy wielomian </math>p(x)<math>  
+
</math></center>
 +
 
 +
 
 +
W {{kotwica|roztwtaylora|różnicowym odpowiedniku Twierdzenia Taylora}}
 +
widzieliśmy (bez dowodu), że każdy wielomian <math>p(x)</math>  
 
można przedstawić jako kombinację liniową  
 
można przedstawić jako kombinację liniową  
</math>p(x)<nowiki>=</nowiki>_{i<nowiki>=</nowiki>0}^k{(^i p)(0)}{i!}x^{i}<math>
+
<math>\displaystyle p(x)=\sum_{i=0}^k\frac{(\Delta^i p)(0)}{i!}x^{\underline{i}}</math>
dolnych silni </math>x^{i}<math>.
+
dolnych silni <math>x^{\underline{i}}</math>.
 
Pokażemy teraz, że rzeczywiście zarówno dolne silnie
 
Pokażemy teraz, że rzeczywiście zarówno dolne silnie
  
</math></center>1,x^{1},x^{2},x^{3},...
+
 
<center><math>
+
<center><math>1,x^{\underline{1}},x^{\underline{2}},x^{\underline{3}},\ldots
 +
</math></center>
 +
 
  
 
jak i górne silnie  
 
jak i górne silnie  
  
</math></center>1,x^{{1}},x^{{2}},x^{{3}},...
 
<center><math>
 
  
stanowią bazy dla przestrzeni wielomianów </math>{R}[x]<math>,   
+
<center><math>1,x^{\overline{1}},x^{\overline{2}},x^{\overline{3}},\ldots
oraz że współczynniki przejścia między tymi trzeba bazami są ściśle powiązane z  
+
</math></center>
liczbami Stirlinga.
+
 
 +
 
 +
stanowią bazy dla przestrzeni wielomianów <math>\mathbb{R}[x]</math>,   
 +
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.
 
W dalszych rozważaniach rezygnujemy z ograniczeń na indeksy sumowania.
 
Zakładamy jedynie, że przebiegają one liczby całkowite pamiętając,  
 
Zakładamy jedynie, że przebiegają one liczby całkowite pamiętając,  
że </math>[ {c}n<br> k ]<math> i </math> {c}n<br>
+
że <math>\left[\begin{array} {c}n\\ k\end{array} \right]</math> i <math>\left\{\begin{array} {c}n\\ k\end{array} \right\}</math>  
 
zerują się dla <math>k<0</math> oraz <math>k>n</math>.
 
zerują się dla <math>k<0</math> oraz <math>k>n</math>.
  
{{obserwacja|||
+
{{obserwacja|6.19|obs 6.19|
 +
Dla <math>x\in\mathbb{R}</math> oraz  <math>n\in\mathbb{N}</math>
  
Dla <math>x\in\mathbb{R}</math> oraz  <math>n\in\mathbb{N}</math>
 
  
<center><math>x^{\overline{n}}=\sum_i\left[\begin{array} {c}n\\ i\end{array} \right]x^i.
+
<center><math>\displaystyle x^{\overline{n}}=\sum_i\left[\begin{array} {c}n\\ i\end{array} \right]x^i.
 
</math></center>
 
</math></center>
 +
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 
 
Dla dowodu indukcyjnego zauważmy najpierw, że przy <math>n=0</math> mamy  
 
Dla dowodu indukcyjnego zauważmy najpierw, że przy <math>n=0</math> mamy  
<math>x^{\overline{0}}=1=\left[\begin{array} {c}0\\ 0\end{array} \right]</math>.  
+
<math>x^{\overline{0}}=1=\left[\begin{array} {c}0\\ 0\end{array} \right]</math>. W kroku indukcyjnym korzystamy tym razem z faktu, że <math>x^{\overline{n}}=x\cdot x^{\overline{n-1}}+(n-1)x^{\overline{n-1}}</math>,
W kroku indukcyjnym korzystamy tym razem z faktu, że  
 
<math>x^{\overline{n}}=x\cdot x^{\overline{n-1}}+(n-1)x^{\overline{n-1}}</math>,
 
 
dostając
 
dostając
  
<center><math>\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\\
+
<center><math>\begin{align} x^{\overline{n}}
&=&\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\\
+
&=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(\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-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[\begin{array} {c}n\\ 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\\
\endaligned</math></center>
+
&=\sum_i\left[\begin{array} {c}n\\ i\end{array} \right]x^i.
 +
\end{align}</math></center>
 +
 
  
 
}}
 
}}
  
{{obserwacja|||
+
{{obserwacja|6.20|obs 6.20|
 +
Dla <math>x\in\mathbb{R}</math> oraz  <math>n\in\mathbb{N}</math>
  
Dla <math>x\in\mathbb{R}</math> oraz  <math>n\in\mathbb{N}</math>
 
  
<center><math>x^n=\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}\x^{\underline{i}}.
+
<center><math>\displaystyle x^n=\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}x^{\underline{i}}.
 
</math></center>
 
</math></center>
 +
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 
+
Zaprezentujemy dwa dowody. Pierwszy - indukcyjny - pracuje dla dowolnego <math>x\in\mathbb{R}</math>, a drugi - kombinatoryczny - w oczywisty sposób jedynie dla <math>x\in\mathbb{N}</math>.
Zaprezentujemy dwa dowody.  
 
Pierwszy -- indukcyjny -- pracuje dla dowolnego <math>x\in\mathbb{R}</math>,  
 
a drugi -- kombinatoryczny -- w oczywisty sposób jedynie dla <math>x\in\mathbb{N}</math>.
 
  
 
Dla dowodu indukcyjnego zauważmy najpierw, że przy <math>n=0</math> mamy  
 
Dla dowodu indukcyjnego zauważmy najpierw, że przy <math>n=0</math> mamy  
<math>x^0=1=\left\{\begin{array} {c}0\\ 0\end{array} \right\}\$.  
+
<math>x^0=1=\left\{\begin{array} {c}0\\ 0\end{array} \right\}</math>.  
 
W kroku indukcyjnym korzystamy z faktu, że  
 
W kroku indukcyjnym korzystamy z faktu, że  
</math>x x^{i}<nowiki>=</nowiki>x^{i+1}+ix^{i}<math>
+
<math>x\cdot x^{\underline{i}}=x^{\underline{i+1}}+ix^{\underline{i}}</math>
 
dostając:  
 
dostając:  
  
</math></center> x^n<nowiki>=</nowiki>x x^{n-1}
 
&<nowiki>=</nowiki>&x_i  {c}n-1<br> i ^{i}<br>
 
&<nowiki>=</nowiki>&_i  {c}n-1<br> i <math>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</math></center>
 
  
Dla dowodu kombinatorycznego załóżmy, że <math>x\in\mathbb{N}-{\left\{ {0} \right\}\ }</math>
+
<center><math>\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\}(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{align}</math></center>
 +
 
 +
 
 +
Dla dowodu kombinatorycznego załóżmy, że <math>x\in\mathbb{N}-{\left\{ {0} \right\} }</math>
 
i niech <math>X</math> będzie zbiorem <math>x</math>-elementowym.
 
i niech <math>X</math> będzie zbiorem <math>x</math>-elementowym.
 
Oczywiście <math>x^n</math> to liczba funkcji postaci <math>\mathbb{Z}_n \longrightarrow X</math>.
 
Oczywiście <math>x^n</math> to liczba funkcji postaci <math>\mathbb{Z}_n \longrightarrow X</math>.
Linia 1026: Linia 792:
 
(uporządkowanym najpierw według najmniejszych elementów w blokach)  
 
(uporządkowanym najpierw według najmniejszych elementów w blokach)  
 
przyporządkowujemy <math>i</math>-tą wartość wybranego ciągu.  
 
przyporządkowujemy <math>i</math>-tą wartość wybranego ciągu.  
Tym sposobem mamy <math>\left\{\begin{array} {c}n\\ i\end{array} \right\}\n^{\underline{i}}</math> funkcji  
+
Tym sposobem mamy <math>\left\{\begin{array} {c}n\\ i\end{array} \right\}n^{\underline{i}}</math> funkcji  
 
<math>\mathbb{Z}_n \longrightarrow X</math> przyjmujących dokładnie <math>i</math> wartości.  
 
<math>\mathbb{Z}_n \longrightarrow X</math> przyjmujących dokładnie <math>i</math> wartości.  
 
Sumując po wszystkich możliwych <math>i</math> otrzymujemy żądaną równość.
 
Sumując po wszystkich możliwych <math>i</math> otrzymujemy żądaną równość.
Linia 1032: Linia 798:
  
 
Wskazaliśmy współczynniki przejścia z bazy górnych silni w jednomiany  
 
Wskazaliśmy współczynniki przejścia z bazy górnych silni w jednomiany  
oraz z jednomianów w dolne silnie.  
+
oraz z jednomianów w dolne silnie. Nierówności
Nierówności
+
 
  
 
<center><math>x^{\underline{n}}<x^n<x^{\overline{n}}
 
<center><math>x^{\underline{n}}<x^n<x^{\overline{n}}
 
</math></center>
 
</math></center>
 +
  
 
zachodzące dla <math>x>n>1</math>,  
 
zachodzące dla <math>x>n>1</math>,  
Linia 1043: Linia 810:
 
Wskazując te współczynniki wykorzystamy prosty fakt:
 
Wskazując te współczynniki wykorzystamy prosty fakt:
  
<center><math>\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</math></center>
 
  
{{obserwacja|||
+
<center><math>\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}</math></center>
  
 +
 +
{{obserwacja|6.21|obs 6.21|
 
Dla <math>x\in\mathbb{R}</math> oraz  <math>n\in\mathbb{N}</math>
 
Dla <math>x\in\mathbb{R}</math> oraz  <math>n\in\mathbb{N}</math>
  
<center><math>\aligned x^n&=&\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}</math>-1)^{n-i}x^{{i}},<br>
+
 
x^{n}&<nowiki>=</nowiki>&_i[ {c}n<br> i ](-1)^{n-i}x^i.
+
<center><math>\begin{align} x^n&=\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}(-1)^{n-i}x^{\overline{i}},\\
<center><math>
+
x^{\underline{n}}&=\sum_i\left[\begin{array} {c}n\\ i\end{array} \right](-1)^{n-i}x^i.
 +
\end{align}</math></center>
 +
 
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 
 
Udowodnimy jedynie pierwszą równość,  
 
Udowodnimy jedynie pierwszą równość,  
 
pozostawiając analogiczny dowód dla drugiej jako ćwiczenie.
 
pozostawiając analogiczny dowód dla drugiej jako ćwiczenie.
  
</math></center> x^n<nowiki>=</nowiki>(-1)^n(-x)^n
+
 
&<nowiki>=</nowiki>&(-1)^n_i {c}n<br> i <math>-x)^{\underline{i}}\\
+
<center><math>\begin{align} x^n=(-1)^n(-x)^n
&=&(-1)^n\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}</math>-1)^ix^{{i}}<br>
+
&=(-1)^n\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}(-x)^{\underline{i}}\\
&<nowiki>=</nowiki>&_i {c}n<br> i <math>-1)^{n-i}x^{\overline{i}}.
+
&=(-1)^n\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}(-1)^ix^{\overline{i}}\\
\endaligned</math></center>
+
&=\sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}(-1)^{n-i}x^{\overline{i}}.
 +
\end{align}</math></center>
 +
 
  
 
}}
 
}}
Linia 1077: Linia 848:
 
otrzymujemy następujące zależności:
 
otrzymujemy następujące zależności:
  
{{obserwacja|||
+
{{obserwacja|6.22|obs 6.22|
 +
Dla <math>m,n\in\mathbb{N}</math>
  
Dla <math>m,n\in\mathbb{N}</math>
 
  
<center><math>\aligned \sum_i (-1)^{m-i}\left\{\begin{array} {c}m\\ i\end{array} \right\}\\fStirlingDlaCykli{i}{n}
+
<center><math>\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\{
+
\left\{ \begin{array} {ll}
\begin{array} {ll}
+
0,& \mbox{ dla } m\neq n,
0,& \mbox{\rm dla \ } m\neq n,
 
 
\\  
 
\\  
1,& \mbox{\rm dla \ } m=n,
+
1,& \mbox{ dla } m=n,
 
\end{array}  
 
\end{array}  
 
\right.
 
\right.
 
\\
 
\\
\sum_i (-1)^{m-i}\left[\begin{array} {c}m\\ i\end{array} \right]\left\{\begin{array} {c}i\\ 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\{
 
\left\{
 
\begin{array} {ll}
 
\begin{array} {ll}
0,& \mbox{\rm dla \ } m\neq n,
+
0,& \mbox{ dla } m\neq n,
 
\\  
 
\\  
1,& \mbox{\rm dla \ } m= n.
+
1,& \mbox{ dla } m= n.
 
\end{array}  
 
\end{array}  
 
\right.
 
\right.
\endaligned</math></center>
+
\end{align}</math></center>
 +
 
  
 
}}
 
}}
Linia 1113: Linia 884:
 
Liczba ta zależy oczywiście od tego czy obiekty, bądź kategorie, są rozróżnialne.
 
Liczba ta zależy oczywiście od tego czy obiekty, bądź kategorie, są rozróżnialne.
  
'''Obiekty są rozróżnialne'''  
+
{{kotwica|obiektyrozroz|'''Obiekty są rozróżnialne'''}} jeśli zamiana miejscami dwu obiektów z różnych kategorii daje nową konfigurację.  
jeśli zamiana miejscami dwu obiektów z różnych kategorii daje nową konfigurację.  
 
  
'''Kategorie są rozróżnialne'''  
+
{{kotwica|kategrozroz|'''Kategorie są rozróżnialne'''}} jeśli wzajemna wymiana wszystkich obiektów między dwiema kategoriami prowadzi do nowej konfiguracji.  
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.
 
Zobaczymy, że im mniej rozróżnialności, tym zliczanie staje się trudniejsze.
Linia 1130: Linia 898:
 
Większość wariantów klasyfikacji <math>n</math> obiektów na <math>k</math> kategorii już przeanalizowaliśmy.  
 
Większość wariantów klasyfikacji <math>n</math> obiektów na <math>k</math> kategorii już przeanalizowaliśmy.  
 
Podsumujmy zatem:
 
Podsumujmy zatem:
 
 
* '''obiekty rozróżnialne, kategorie rozróżnialne:'''
 
* '''obiekty rozróżnialne, kategorie rozróżnialne:'''
  
Linia 1138: Linia 905:
  
 
Klasyfikacja na dokładnie <math>k</math> kategorie to funkcja surjektywna.  
 
Klasyfikacja na dokładnie <math>k</math> kategorie to funkcja surjektywna.  
Zgodnie z Obserwacją [[##obserwacja - liczba surjekcji|Uzupelnic obserwacja - liczba surjekcji|]],
+
Zgodnie z [[#obs_6.16|Obserwacją 6.16]],
 
liczba takich klasyfikacji to,  
 
liczba takich klasyfikacji to,  
<math>k!\left\{\begin{array} {c}n\\ k\end{array} \right\}\$.
+
<math>k!\left\{\begin{array} {c}n\\ k\end{array} \right\}</math>.
  
* \textbf{obiekty rozróżnialne, kategorie nierozróżnialne:}
+
* '''obiekty rozróżnialne, kategorie nierozróżnialne:'''
  
 
Nierozróżnialność kategorii oznacza, że nie jest ważna nazwa kategorii
 
Nierozróżnialność kategorii oznacza, że nie jest ważna nazwa kategorii
 
(tzn. wartość funkcji dla danego obiektu), a jedynie jej zawartość.  
 
(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 </math>k<math> bloków.
+
Mamy więc do czynienia z podziałem zbioru obiektów na co najwyżej <math>k</math> bloków.
 
Liczba takich konfiguracji to suma liczb Stirlinga dla podziałów  
 
Liczba takich konfiguracji to suma liczb Stirlinga dla podziałów  
</math>_{i<nowiki>=</nowiki>1}^{k} {c}n<br> i .
+
<math>\displaystyle \sum_{i=1}^{k}\left\{\begin{array} {c}n\\ i\end{array} \right\}</math>.
  
 
Oczywiście gdy wszystkie kategorie są niepuste,  
 
Oczywiście gdy wszystkie kategorie są niepuste,  
 
to zbiór obiektów jest podzielony na dokładnie <math>k</math> bloków.  
 
to zbiór obiektów jest podzielony na dokładnie <math>k</math> bloków.  
Liczba takich konfiguracji to <math>\left\{\begin{array} {c}n\\ k\end{array} \right\}\$.
+
Liczba takich konfiguracji to <math>\left\{\begin{array} {c}n\\ k\end{array} \right\}</math>.
  
* \textbf{obiekty nierozróżnialne, kategorie rozróżnialne:}
+
* '''obiekty nierozróżnialne, kategorie rozróżnialne:'''
  
 
Nierozróżnialność obiektów skutkuje tym,  
 
Nierozróżnialność obiektów skutkuje tym,  
 
że ważna jest jedynie ich liczba w danej kategorii.
 
że ważna jest jedynie ich liczba w danej kategorii.
A zatem konfiguracja to podział liczby </math>n <math> na sumę </math>n<nowiki>=</nowiki>x_0+...+x_{k-1}<math>
+
A zatem konfiguracja to podział liczby <math>n </math> na sumę <math>n=x_0+\ldots+x_{k-1}</math>
liczb naturalnych </math>x_i<math>.  
+
liczb naturalnych <math>x_i</math>.  
 
Liczba rozwiązań takiego równania została policzona w jednym z przykładów wykładu  
 
Liczba rozwiązań takiego równania została policzona w jednym z przykładów wykładu  
 
o współczynnikach dwumianowych i wynosi   
 
o współczynnikach dwumianowych i wynosi   
</math>{n+k-1 k-1}<math>.
+
<math>{n+k-1\choose k-1}</math>.
  
I znów, gdy kategorii, czyli składników w rozkładzie </math>n<nowiki>=</nowiki>x_0+...+x_{k-1}<math>,  
+
I znów, gdy kategorii, czyli składników w rozkładzie <math>n=x_0+\ldots+x_{k-1}</math>,  
ma być dokładnie </math>k<math>, zliczamy jedynie rozwiązania spełniające dodatkowo  
+
ma być dokładnie <math>k</math>, zliczamy jedynie rozwiązania spełniające dodatkowo  
</math>x_0,...,x_{k-1} 1<math>.  
+
<math>x_0,\ldots,x_{k-1}\geqslant 1</math>.  
 
Zgodnie z innym przykładem analizowanym w wykładzie o współczynnikach dwumianowych  
 
Zgodnie z innym przykładem analizowanym w wykładzie o współczynnikach dwumianowych  
liczba takich rozwiązań to </math>{n-1 k-1}<math>.
+
liczba takich rozwiązań to <math>{n-1\choose k-1}</math>.
  
* \textbf{obiekty nierozróżnialne, kategorie nierozróżnialne:}
+
* '''obiekty nierozróżnialne, kategorie nierozróżnialne:'''
  
 
To jedyny jeszcze nie analizowany przez nas przypadek.
 
To jedyny jeszcze nie analizowany przez nas przypadek.
 
Załóżmy najpierw, że wszystkie kategorie są niepuste.  
 
Załóżmy najpierw, że wszystkie kategorie są niepuste.  
 
Ponieważ są one nierozróżnialne, możemy dodatkowo założyć,  
 
Ponieważ są one nierozróżnialne, możemy dodatkowo założyć,  
że w rozkładzie liczby </math>n<math> na sumę </math>n<nowiki>=</nowiki>x_0+...+x_{k-1}<math>  
+
że w rozkładzie liczby <math>n</math> na sumę <math>n=x_0+\ldots+x_{k-1}</math>  
zachodzi </math>x_0 x_1 ...  x_{k-1}<math>.
+
zachodzi <math>x_0\leqslant x_1 \leqslant \ldots \leqslant x_{k-1}</math>.
Liczba </math>P(n,k)<math> takich rozkładów
+
Liczba <math>P(n,k)</math> takich rozkładów
 
będzie przedmiotem ostatniej części wykładu.
 
będzie przedmiotem ostatniej części wykładu.
 
Jednak już teraz możemy powiedzieć,  
 
Jednak już teraz możemy powiedzieć,  
Linia 1185: Linia 952:
  
 
Oczywiście, gdy dopuszczamy puste kategorie liczba konfiguracji  
 
Oczywiście, gdy dopuszczamy puste kategorie liczba konfiguracji  
jest sumą </math>_{i<nowiki>=</nowiki>1}^k P(n,k)<math>.
+
jest sumą <math>\displaystyle \sum_{i=1}^k P(n,k)</math>.
  
 
==Podziały liczby==
 
==Podziały liczby==
  
\textbf{\underline{Podział liczby}} </math>n<math> na </math>k<math> składników to przedstawienie </math>n<math> w postaci sumy  
+
{{kotwica|podziall|'''Podział liczby'''}} <math>n</math> na <math>k</math> składników to przedstawienie <math>n</math> w postaci sumy  
 +
 
  
</math></center>a_0+...+a_{k-1}<nowiki>=</nowiki>n,
+
<center><math>a_0+\ldots+a_{k-1}=n,
<center><math>
+
</math></center>
  
gdzie </math>a_0  a_1  ...  a_{k-1} 1<math>.
 
  
\noindent
+
gdzie <math>a_0 \leqslant a_1 \leqslant \ldots \leqslant a_{k-1}\leqslant 1</math>.
\textbf{\underline{Liczbę podziałów}} </math>n<math> na </math>k<math> składników oznaczamy przez  
+
 
</math>P(n,k)<math>.
+
{{kotwica|lpodzialow|'''Liczbę podziałów'''}} <math>n</math> na <math>k</math> składników oznaczamy przez  
 +
<math>P(n,k)</math>.
  
 
{{przyklad|||
 
{{przyklad|||
 +
Lista podziałów <math>7</math> na <math>4</math> składniki:
  
Lista podziałów </math>7<math> na </math>4<math> składniki:
 
  
</math></center>1+1+1+4, 1+1+2+3, 1+2+2+2.
+
<center><math>1+1+1+4,\qquad 1+1+2+3,\qquad 1+2+2+2.
<center><math>
+
</math></center>
 +
 
  
* </math>P(7,4)<nowiki>=</nowiki>3<math>.
+
* <math>P(7,4)=3</math>.
  
 
}}
 
}}
  
{{obserwacja|||
+
{{obserwacja|6.23|obs 6.23|
 
 
Dla </math>n,k{N}-{ {0} }<math>
 
  
* </math>P(n,1)<nowiki>=</nowiki>1<math>,
+
Dla <math>n,k\in\mathbb{N}-{\left\{ {0} \right\} }</math>
 +
* <math>P(n,1)=1</math>,
  
* </math>P(n,2)<nowiki>=</nowiki> {n}{2}<math>,
+
* <math>P(n,2)=\left\lfloor \frac{n}{2}\right\rfloor</math>,
  
* </math>P(n,n)<nowiki>=</nowiki>1<math>,
+
* <math>P(n,n)=1</math>,
  
* </math>P(n,k)<nowiki>=</nowiki>0<math>, dla </math>n<k<math>
+
* <math>P(n,k)=0</math>, dla <math>n<k</math>
  
* </math>{1}{k!}{n-1 k-1} P(n,k){n-1 k-1}<math>.
+
* <math>\frac{1}{k!}{n-1\choose k-1}\leqslant P(n,k)\leqslant{n-1\choose k-1}</math>.
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 
 
Uzasadnimy jedynie ostatni punkt.
 
Uzasadnimy jedynie ostatni punkt.
Dla dowodu ograniczenia górnego liczby </math>P(n,k)<math>
+
Dla dowodu ograniczenia górnego liczby <math>P(n,k)</math>
zauważmy, że interesujące nas podziały liczby </math>n<math>  
+
zauważmy, że interesujące nas podziały liczby <math>n</math>  
są rozwiązaniami równania </math>n<nowiki>=</nowiki>x_0+...+x_{k-1}<math>,  
+
są rozwiązaniami równania <math>n=x_0+\ldots+x_{k-1}</math>,  
a tych, jak już wiemy, jest dokładnie </math>{n-1 k-1}<math>.
+
a tych, jak już wiemy, jest dokładnie <math>{n-1\choose k-1}</math>.
  
Z drugiej strony dowolny podział liczby </math>n<math> generuje co najwyżej </math>k!<math> rozwiązań  
+
Z drugiej strony dowolny podział liczby <math>n</math> generuje co najwyżej <math>k!</math> rozwiązań  
równania </math>n<nowiki>=</nowiki>x_0+...+x_{k-1}<math>  
+
równania <math>n=x_0+\ldots+x_{k-1}</math>  
(generuje dokładnie </math>k!<math>, jeśli składniki podziału są parami różne)
+
(generuje dokładnie <math>k!</math>, jeśli składniki podziału są parami różne)
 
i wszystkie rozwiązania mogą zostać w ten sposób osiągnięte.
 
i wszystkie rozwiązania mogą zostać w ten sposób osiągnięte.
 
To oczywiście daje ograniczenie dolne.
 
To oczywiście daje ograniczenie dolne.
 
}}
 
}}
  
Ograniczenie górne dla </math>P(n,k)<math> można poprawić:
+
Ograniczenie górne dla <math>P(n,k)</math> można poprawić:
 +
 
 +
{{obserwacja|6.24|obs 6.24|
 +
 
  
{{obserwacja|||
+
<center><math>P(n,k) \leqslant \frac{1}{k!}{n+{k\choose2}-1\choose k-1}.
 +
</math></center>
  
</math></center>P(n,k)  {1}{k!}{n+{k}-1 k-1}.
 
<center><math>
 
  
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 +
Dla podziału <math>n=a_0+\ldots+a_{k-1}</math> definiujemy
 +
  
Dla podziału </math>n<nowiki>=</nowiki>a_0+...+a_{k-1}<math> definiujemy
+
<center><math>b_i=a_i+(k-1-i),\qquad\mbox{ dla }{0}\leqslant{i}\leqslant{k-1}.
 +
</math></center>
  
</math></center>b_i<nowiki>=</nowiki>a_i+(k-1-i),dla <math>0\leq i\leq k-1</math>.
 
<center><math>
 
  
Zauważmy, że wszystkie liczby </math>b_i<math> są różne oraz
+
Zauważmy, że wszystkie liczby <math>b_i</math> są różne oraz
  
</math></center>b_0+...+b_{k-1}<nowiki>=</nowiki>n+{k(k-1)}{2}.
 
<center><math>
 
  
A zatem podziały liczby </math>n<math> na </math>k<math> składników  
+
<center><math>b_0+\ldots+b_{k-1}=n+\frac{k(k-1)}{2}.
 +
</math></center>
 +
 
 +
 
 +
A zatem podziały liczby <math>n</math> na <math>k</math> składników  
 
stoją w bijektywnej odpowiedniości z podziałami liczby  
 
stoją w bijektywnej odpowiedniości z podziałami liczby  
</math>n+{k 2}<math> na </math>k<math> parami różnych składników.  
+
<math>n+{k\choose 2}</math> na <math>k</math> parami różnych składników.  
Każdy podział </math>n+{k}<math> na </math>k<math> parami różnych składników  
+
Każdy podział <math>n+{k\choose2}</math> na <math>k</math> parami różnych składników  
generuje dokładnie </math>k!<math> rozwiązań równania
+
generuje dokładnie <math>k!</math> rozwiązań równania
 +
 
  
</math></center>x_0+...+x_{k-1}<nowiki>=</nowiki>n+{k 2},
+
<center><math>x_0+\ldots+x_{k-1}=n+{k\choose 2},
<center><math>
+
</math></center>
  
gdzie </math>x_i>0<math>.  
+
 
 +
gdzie <math>x_i>0</math>.  
 
Wiemy zaś, że to ostatnie równanie posiada co najwyżej  
 
Wiemy zaś, że to ostatnie równanie posiada co najwyżej  
</math>{n+{k}-1 k-1}<math> rozwiązań.  
+
<math>{n+{k\choose2}-1\choose k-1}</math> rozwiązań.  
A zatem ciągów </math> b_i <math>, a tym samym podziałów </math>n<math> na </math>k<math> składników,   
+
A zatem ciągów <math>\left\langle b_i \right\rangle</math>, a tym samym podziałów <math>n</math> na <math>k</math> składników,   
jest co najwyżej </math>{1}{k!}{n+{k}-1 k-1}<math>.  
+
jest co najwyżej <math>\frac{1}{k!}{n+{k\choose2}-1\choose k-1}</math>.  
 
}}
 
}}
  
 
Ostatnia obserwacja pozwala na opisanie granicznego zachowania liczb  
 
Ostatnia obserwacja pozwala na opisanie granicznego zachowania liczb  
</math>P(n,k)<math> przy ustalonym </math>k<math>.
+
<math>P(n,k)</math> przy ustalonym <math>k</math>.
 +
 
 +
{{wniosek|6.25|wn 6.25|
 +
Dla dowolnego <math>k</math>
 +
 
 +
 
 +
<center><math>\displaystyle \lim_{n\rightarrow\infty}\frac{P(n,k)}{n^{k-1}}=\frac{1}{k!(k-1)!}.
 +
</math></center>
  
{{wniosek|||
 
Dla dowolnego </math>k</center>_{n}{P(n,k)}{n^{k-1}}<nowiki>=</nowiki>{1}{k!(k-1)!}.
 
<center><math>
 
  
 
}}
 
}}
Linia 1291: Linia 1069:
 
są tzw. diagramy Ferrersa.  
 
są tzw. diagramy Ferrersa.  
  
\noindent
+
{{kotwica|diagramfer|'''Diagram Ferrersa'''}} dla podziału <math>n=a_0+\ldots+a_{k-1}</math>  
\textbf{\underline{Diagram Ferrersa}} dla podziału </math>n<nowiki>=</nowiki>a_0+...+a_{k-1}<math>  
+
składa się z <math>k</math> wierszy o odpowiednio <math>a_{i-1}</math> elementach.
składa się z </math>k<math> wierszy o odpowiednio </math>a_{i-1}<math> elementach.
+
 
 +
[[File:SW 6.3.svg|250x100px|thumb|left|SW 6.3.swf]]
 +
 
 +
[[File:SW 6.4.svg|250x100px|thumb|right|SW 6.4.swf]]
  
 
{{przyklad|||
 
{{przyklad|||
  
</math></center>2+5+6+6+9<nowiki>=</nowiki>28.
+
<center>
<center><math>
+
<math>2+5+6+6+9=28.
 +
</math>
 +
</center>
  
\medskip\noindent\textit{Rysunek:} 6.3 Szkic na kartce.\medskip
+
<center>
 
+
<math>1+3+3+3=10.
</math></center>1+3+3+3<nowiki>=</nowiki>10.
+
</math>
<center><math>
+
</center>
  
\medskip\noindent\textit{Rysunek:} 6.4 Szkic na kartce.\medskip
 
 
}}
 
}}
  
 
Użyteczność diagramów Ferrersa ilustrują dowody kilku nastepnych obserwacji.
 
Użyteczność diagramów Ferrersa ilustrują dowody kilku nastepnych obserwacji.
  
{{obserwacja|||
+
{{obserwacja|6.26|obs 6.26|
 +
Liczba <math>P(n,k)</math>
 +
jest równa liczbie podziałów liczby <math>n</math>
 +
(na dowolną liczbę składników) o największym składniku równym <math>k</math>.
 +
}}
 +
 
 +
[[File:MD1-SW 6.5.mp4|250x250px|thumb|left|MD1-SW 6.5.swf]]
  
Liczba </math>P(n,k)<math>
+
[[File:MD1-SW 6.6.mp4|250x250px|thumb|right|MD1-SW 6.6.swf]]
jest równa liczbie podziałów liczby </math>n<math>
 
(na dowolną liczbę składników) o największym składniku równym </math>k<math>.
 
}}
 
  
 
{{dowod|||
 
{{dowod|||
 
+
Odwracając o <math>90</math> stopni diagram podziału liczby <math>n</math> na <math>k</math> składników
Odwracając o </math>90<math> stopni diagram podziału liczby </math>n<math> na </math>k<math> składników
+
otrzymamy diagram podziału liczby <math>n</math>,  
otrzymamy diagram podziału liczby </math>n<math>,  
+
którego największy składnik równy jest <math>k</math>.  
którego największy składnik równy jest </math>k<math>.  
 
 
Oczywiście jest to odwzorowanie bijektywne,  
 
Oczywiście jest to odwzorowanie bijektywne,  
gdyż odwracając z powrotem o </math>90<math> stopni otrzymamy ten wyjściowy diagram.
+
gdyż odwracając z powrotem o <math>90</math> stopni otrzymamy ten wyjściowy diagram.
  
\medskip\noindent\textit{Rysunek:} 6.5 Szkic na kartce.\medskip
 
 
}}
 
}}
  
{{obserwacja|||
+
{{obserwacja|6.27|obs 6.27|
 
+
Liczba <math>P(n+k,k)</math> jest równa liczbie podziałów <math>n</math> na co najwyżej <math>k</math> składników.
Liczba </math>P(n+k,k)<math> jest równa  
 
liczbie podziałów </math>n<math> na co najwyżej </math>k<math> składników.
 
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
 
+
Wycinając ostatnią kolumnę w diagramie podziału liczby <math>n+k</math> na <math>k</math> składników
Wycinając ostatnią kolumnę w diagramie podziału liczby </math>n+k<math> na </math>k<math> składników
+
otrzymamy podział liczby <math>n</math> na co najwyżej <math>k</math> składników.  
otrzymamy podział liczby </math>n<math> na co najwyżej </math>k<math> składników.  
 
 
Łatwo zauważyc, że jest to odwzorowanie bijektywne.
 
Łatwo zauważyc, że jest to odwzorowanie bijektywne.
  
\medskip\noindent\textit{Rysunek:} 6.6 Szkic na kartce.\medskip
+
}}
}}</math>
 

Aktualna wersja na dzień 11:15, 19 paź 2021

Permutacje

Rozważając permutacje zbiorów -elementowych, wystarczy ograniczyć się do permutacji zbioru . Każdy inny taki zbiór różni się bowiem od 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 są dwoma rozkładami tej samej permutacji na cykle to i .

Pierwszym ważnym niezmiennikiem dla permutacji jest:

Liczba cykli permutacji zdefiniowana jako liczba cykli w jamimkolwiek rozkładzie na cykle.

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

Typ permutacji to wektor , gdzie jest liczbą -elementowych cykli w rozkładzie . Zazwyczaj typ permutacji zapisujemy jako , przy czym często pomijamy te wartości, dla których .

Przykład

Dla permutacji zadanej przez



mamy:

  • ,
  • jest typu .

Z samej definicji typu permutacji natychmiast wynika:

Obserwacja 6.1

Dla typu zachodzi

  • ,
  • .

Obserwacja 6.2

Liczba permutacji w typu to



Dowód

Potraktujmy permutację typu , jako uzupełnienie elementami z następującego wzorca:



W miejsce kropek możemy wstawić -elementów na sposobów. Jednak w ten sposób otrzymamy wielokrotnie te same permutacje. Każdy cykl -elementowy możemy zadać na 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. takich samych cykli -elementowych może być wybranych na sposobów. Podsumowując, aby otrzymać liczbę permutacji typu musimy, dla wszystkich , podzielić przez długość każdego cyklu z osobna, tzn. dla każdego cyklu długości podzielić przez , oraz przez silnię liczby -elementowych cykli. Zatem szukana liczba to .

End of proof.gif

Przykład

Lista typów wszystkich permutacji z :



Liczba permutacji z o kolejnych typach:



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

Permutacja sprzężona do permutacji to każda permutacja postaci , gdzie .

Oczywiście, jeśli to . 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 jest ona sama.

Obserwacja 6.3

Permutacje mają ten sam typ wtedy i tylko wtedy, gdy są sprzężone.

MD1-5-1.swf

Dowód

Załóżmy najpierw, że i są sprzężone, czyli że dla pewnego . Rozważmy jakiś cykl permutacji . Wtedy jest cyklem permutacji . Istotnie, dla mamy:



i podobnie:



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

Dla dowodu w drugą stronę załóżmy, że i mają ten sam typ. Wtedy możemy określić bijekcję przyporządkowującą każdemu cyklowi permutacji pewien cykl o tej samej długości. Po rozkładzie obu permutacji na rozłączne cykle i nasza bijekcja między cyklami przyporzadkowuje cyklowi cykl , definiujemy kładąc . Łatwo sprawdzić, że wtedy .

End of proof.gif

Transpozycja to permutacja w (dla ) typu . Innymi słowy, transpozycja dokonuje tylko jednego przestawienia dwóch elementów ze zbioru -elementowego.

Przykład

Dla permutacji zadanej przez



mamy:

  • ma typ ,
  • 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 jest złożeniem transpozycji.

Dowód

Cykl można przedstawić tabelką:



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



Rzeczywiście przejdzie:

  • w pierwszej transpozycji w ,
  • a następne transpozycje już go nie przesuną.

Podobnie przejdzie

  • pierwszą transpozycją w ,
  • drugą w ,
  • a następne transpozycje już go nie przesuną.

Ogólnie, (dla )

  • pozostanie na swoim miejscu przez pierwsze transpozycji

,

  • przejdzie -tą transpozycją w ,
  • przejdzie -szą transpozycją w ,
  • po czym zostanie już nienaruszone.

Natomiast zostanie przesunięte dopiero ostatnią transpozycją i przyjmie wartość .

End of proof.gif

Wniosek 6.5

Dowolna permutacja jest złożeniem transpozycji. W szczególności każda permutacja typu ma rozkład na co najwyżej transpozycji.

MD1-5-2.swf

Przykład

Dla permutacji zadanej przez



mamy

  • ,
  • ,
  • ,
  • .

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

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 i jest transpozycją, to



MD1-5-3.swf

Dowód

Udowodnimy tylko pierwszą równość. Załóżmy, że tzn., , i dla wszystkich pozostałych elementów . Rozumowanie dzielimy na dwa przypadki:

  • i są w tym samym cyklu permutacji .

Wtedy , gdzie ostatni wielokropek oznacza pozostałe cykle permutacji . Zatem w tym przypadku mamy .

  • i są w różnych cyklach permutacji .

Wtedy . Mamy więc .

End of proof.gif

Obserwacja 6.7

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

Dowód

Niech będą dwoma rozkładami tej samej permutacji na transpozycje. Na mocy Obserwacji 6.6 mamy:



Niech opisuje iloć dodawań jedynki w powyższej formule. Wtedy to liczba odejmowań jedynki. Transpozycja ma cykl -elementowy i cykli -elementowych, czyli . Zatem



dla pewnego . Analogicznie



dla pewnego . Porównując obydwa wyniki otrzymujemy



czyli różnica jest zawsze parzysta.

End of proof.gif

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 to , gdzie jest liczbą transpozycji, na które można rozłożyć .

Obserwacja 6.8

Dla dowolnych

  • ,
  • ,
  • ,

Dowód

Identyczność jest złożeniem zera transpozycji. Drugi punkt wynika natychmiast z Obserwacji 6.6. Dla dowodu trzeciego odnotujmy tylko, że .

End of proof.gif

Przykład

Dla relaksu rozważmy łamigłówkę logiczną rozgrywaną na kwadracie . 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 :

  • 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
  • ,
  • Wniosek 6.5 daje wtedy jednak, że jest złożeniem transpozycji, czyli 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 w jest dokładnie tyle samo permutacji parzystych co nieparzystych.

Dowód

Niech i będzie listą wszystkich parzystych permutacji w . Ponadto, rozważmy transpozycję . Wtedy oczywiście permutacje są parami różne, gdyż jeśli to . Ponadto dowolna jest nieparzysta, bo Pozostaje pokazać, że dowolna nieparzysta permutacja jest na liście . Ponieważ to jest permutacją parzystą, a zatem jest postaci dla pewnego . To zaś oznacza, że



czyli jest na liście . Uzyskana bijekcja dowodzi naszej obserwacji.

End of proof.gif

Podziały

Liczby Stirlinga

Liczba Stirlinga dla cykli (często nazywana liczbą Stirlinga pierwszego rodzaju) to liczba permutacji zbioru -elementowego złożonych z dokładnie cykli, czyli takich permutacji , że . Przyjmujemy, że , 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ść dla wszystkich . Przyjmujemy, że dla .

MD1-5-5.swf

Przykład

Lista permutacji złożonych z cykli:

  • Mamy permutacji złożonych z dwóch cykli, zatem .

Obserwacja 6.10

Dla

  • , dla
  • ,
  • ,
  • ,
  • , dla

Dowód

Pierwszy punkt jest natychmiastowa konsekwencją faktu, że nie można podzielić niepustego zbioru na części (cykli).

Liczba opisuje permutacje o jednym cyklu. Każda taka permutacja jest zadana wzorcem . Wzorzec taki może być wypełniony -elementami na sposobów. Ale ten sam cykl ma wiele opisów różniących się jedynie przesunięciem. Zatem każdy -elementowy cykl może być zapisany według takiego wzorca na sposobów, czyli liczba cykli na zbiorze -elementowym to , co dowodzi punktu drugiego.

Liczba opisuje permutacje o cyklach. Permutacja taka musi wiec być typu , 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 -elementowych, czyli , co dowodzi punktu trzeciego.

Dla dowodu punktu czwartego zauważmy jedynie, że jedyną permutacją o cyklach na zbiorze -elementowym jest identyczność.

Równie łatwo jest stwierdzić, że zbiór -elementowy nie może być podzielony na więcej niż niepustych części (mających stanowić cykle).

End of proof.gif

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



Dowód

Niech będzie wyróżnionym i ustalonym elementem -elementowego zbioru . Permutacje zbioru o cyklach można podzielić na dwa typy, w których:

  • stanowi jednoelementowy cykl,
  • jest w cyklu co najmniej -elementowym.

W pierwszym przypadku pozostałe elementów zbioru muszą uformować cykli, co jest możliwe na sposobów. W drugim przypadku, po usunięciu elementu permutacje badanego typu wciąż będą mieć cykli. Jest ich zatem tyle, co permutacji -elementowego zbioru o cyklach, czyli . Element może rozbudować każdą permutację zbioru sposobów (wchodząc do cyklu jako następnik jednego z elementów). Zatem permutacji drugiego typu jest dokładnie .

End of proof.gif
MD1-5-6.swf

W Trójkącie Stirlinga dla cykli, -ty wiersz zawiera liczby permutacji zbioru -elementowego o kolejno cyklach. Zatem suma wszystkich tych wartości to liczba wszystkich permutacji zbioru -elementowego, czyli . Dostajemy stąd natychmiast:

Obserwacja 6.12

Dla



Ciekawy jest nastepujacy związek liczb Stirlinga dla cykli z liczbami harmonicznymi .

Obserwacja 6.13

Dla



Dowód

Dla tożsamość jest oczywista, a dla przybiera postać Pokażemy że obydwie liczby z naszej obserwacji to sumaryczna liczba cykli we wszystkich permutacjach zbioru -elementowego, tzn. .

  • Permutacji o cyklach jest dokładnie . W sumie permutacje o cyklach mają więc cykli, czyli .
  • Zliczymy najpierw -elementowe cykle zbudowane z elementów zbioru -elementowego. Każdy taki cykl jest wyznaczony przez wypełnienie wzorca , ale z dokładnością do przesunięcia. Wypełnień jest oczywiście tyle, ile injekcji postaci ,

czyli . Zatem zliczanych cykli -elementowych jest dokładnie .

Każdy cykl -elementowy występuje w dokładnie permutacjach zbioru -elementowego, gdyż tyle jest permutacji pozostałych elementów. Zatem sumaryczna liczba cykli we wszystkich permutacjach zbioru -elementowego wynosi:



End of proof.gif

W liczbach Stirlinga dla cykli wypełnialiśmy wzorce postaci:



w sposób injektywny i z dokładnością do:

  • kolejności cykli,
  • przesunięć cyklicznych w każdym z cykli.

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



czyli podział zbioru -elementowego na parami rozłącznych podzbiorów. W podziale, podzbiory takie nazywamy blokami. Przypomnijmy, że podział zbioru na bloków wyznacza relację równoważności na zbiorze o klasach równoważności.

Liczba Stirlinga dla podziałów (często nazywana liczbą Stirlinga drugiego rodzaju) to liczba podziałów zbioru -elementowego na dokładnie bloki. Znów przyjmujemy, że oraz dla .

MD1-5-7.swf

Przykład

Lista podziałów na dwa bloki:

  • Mamy podziałów zbioru na dwa bloki,

zatem .

Obserwacja 6.14

Dla

  • ,
  • , dla ,
  • , dla ,
  • , dla ,
  • ,
  • ,
  • , dla .

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 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 i niech . 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 . Element może stanowić blok z dowolnym podzbiorem pozostałego -elementowego zbioru poza podzbiorem pełnym, gdyż wtedy drugi blok byłby pusty. Zatem jest dokładnie możliwości wyboru bloku dla , i tym samym tyleż jest podziałów .

Dowody pozostałych trzech własności można przeprowadzić jak dla liczb Stirlinga dla cykli.

End of proof.gif

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



MD1-5-8.swf

Dowód

Niech, jak zwykle, i niech będzie ustalonym elementem. Znów, podziały zbioru na bloków można podzielić na dwa typy:

  • stanowi blok jednoelementowy,
  • jest w bloku co najmniej dwuelementowym.

Każdy podział pierwszego typu jest jednoznacznie wyznaczony przez -elementowego zbioru na bloków. Jest ich więc dokładnie . W drugim przypadku pozostałe elementy dzielone są wciąż na bloków. Można taki podział wykonać na sposobów. Element może rozszerzyć każdy taki podział zbioru math>X</math> do podziału zbioru na sposobów wchodząc do któregoś z bloków. Zatem jest dokładnie podziałów drugiego typu.

End of proof.gif

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 wyznacza podział zbioru na 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 liczba surjekcji wynosi .

Dowód

Niech . Jak już zauważyliśmy, surjekcja postaci wyznacza pewien podział zbioru dodatkowo poetykietowany elementami zbioru na bloków . Nieetykietowanych podziałów jest oczywiście . Ponieważ każdy podział może być poetykietowany na sposobów, możemy zakończyć dowód.

End of proof.gif

Obserwacja 6.17

Dla



Dowód

Niech . Pojedynczy składnik rozważanej sumy to liczba wyborów ciągu zbiorów , odpowiednio elementowych. Rzeczywiście możemy wybrać na sposobów, na sposobów itd. Każdy taki ciąg zbiorów odpowiada jednoznacznie ciągowi bloków , gdzie . W podziale nie jest jednak istotne uporządkowanie bloków , co oznacza, że powinniśmy przejść od ciągu do rodziny bloków , wydzielając tym samym każdy składnik sumy przez . Tak wydzielona suma to nic innego jak liczba podziałów zbioru -elementowego na bloków, czyli .

End of proof.gif

Przykład



Liczby Bella

Eric Temple Bell (1883-1960)
Zobacz biografię

W Trójkącie Pascala -ty wiersz sumuje się do

liczby podzbiorów zbioru -elementowego, czyli do . W Trójkąta Stirlinga dla cykli -ty wiersz sumuje się do liczby permutacji zbioru -elementowego, czyli do . Zajmiemy się teraz sumą -tego wiersza Trójkąta Stirlinga dla podziałów. Oczywiście suma taka to liczba wszystkich podziałów zbioru elementowego, lub inaczej liczby wszystkich relacji równoważności na zbiorze -elementowym.


Liczba Bella

to liczba podziałów zbioru -elementowego, czyli



Lista kilku pierwszych liczb Bella:



Liczby Bella spełniają piękną zależność rekurencyjną:

Obserwacja 6.18



Dowód

Wybierzmy i ustalmy w -elementowym zbiorze pewien element . Policzmy teraz ile jest podziałów zbioru takich, że blok zawierający ma dokładnie elementów. Oczywiście pozostałe elementów tego bloku może zostać wybranych ze zbioru na sposobów. Każdy taki blok możemy rozbudować do podziału zbioru poprzez podzielenie pozostałych na bloki. Podział taki jest oczywiście możliwy na sposobów, skąd sumując po wszystkich możliwych wartościach otrzymujemy



End of proof.gif

Bazy przestrzeni wielomianów

Przestrzeń wektorowa wszystkich wielomianów jednej zmiennej rzeczywistej ma naturalną bazę złożoną z jednomianów



W różnicowym odpowiedniku Twierdzenia Taylora widzieliśmy (bez dowodu), że każdy wielomian można przedstawić jako kombinację liniową dolnych silni . Pokażemy teraz, że rzeczywiście zarówno dolne silnie



jak i górne silnie



stanowią bazy dla przestrzeni wielomianów , 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 i zerują się dla oraz .

Obserwacja 6.19

Dla oraz



Dowód

Dla dowodu indukcyjnego zauważmy najpierw, że przy mamy . W kroku indukcyjnym korzystamy tym razem z faktu, że , dostając



End of proof.gif

Obserwacja 6.20

Dla oraz



Dowód

Zaprezentujemy dwa dowody. Pierwszy - indukcyjny - pracuje dla dowolnego , a drugi - kombinatoryczny - w oczywisty sposób jedynie dla .

Dla dowodu indukcyjnego zauważmy najpierw, że przy mamy . W kroku indukcyjnym korzystamy z faktu, że dostając:



Dla dowodu kombinatorycznego załóżmy, że i niech będzie zbiorem -elementowym. Oczywiście to liczba funkcji postaci . Każda taka funkcja przyjmuje wartości. Policzmy więc ile funkcji przyjmuje dokładnie wartości. Ciąg różnych wartości ze zbioru -elementowego można wybrać na sposobów. Z każdym takim -elementowym ciągiem możemy stowarzyszyć jakiś podział zbioru na bloków, tzn. kolejnym blokom tego podziału (uporządkowanym najpierw według najmniejszych elementów w blokach) przyporządkowujemy -tą wartość wybranego ciągu. Tym sposobem mamy funkcji przyjmujących dokładnie wartości. Sumując po wszystkich możliwych otrzymujemy żądaną równość.

End of proof.gif

Wskazaliśmy współczynniki przejścia z bazy górnych silni w jednomiany oraz z jednomianów w dolne silnie. Nierówności



zachodzące dla , 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:



Obserwacja 6.21

Dla oraz



Dowód

Udowodnimy jedynie pierwszą równość, pozostawiając analogiczny dowód dla drugiej jako ćwiczenie.



End of proof.gif

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



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 obiektów klasyfikujemy w kategorii pytamy o liczbę konfiguracji (klasyfikacji) o co najwyżej kategoriach oraz o dokładnie kategoriach.

Większość wariantów klasyfikacji obiektów na 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 -elementowego w zbiór -elementowy wynosi .

Klasyfikacja na dokładnie kategorie to funkcja surjektywna. Zgodnie z Obserwacją 6.16, liczba takich klasyfikacji to, .

  • 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 bloków. Liczba takich konfiguracji to suma liczb Stirlinga dla podziałów .

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

  • 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 na sumę liczb naturalnych . Liczba rozwiązań takiego równania została policzona w jednym z przykładów wykładu o współczynnikach dwumianowych i wynosi .

I znów, gdy kategorii, czyli składników w rozkładzie , ma być dokładnie , zliczamy jedynie rozwiązania spełniające dodatkowo . Zgodnie z innym przykładem analizowanym w wykładzie o współczynnikach dwumianowych liczba takich rozwiązań to .

  • 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 na sumę zachodzi . Liczba 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ą .

Podziały liczby

Podział liczby na składników to przedstawienie w postaci sumy



gdzie .

Liczbę podziałów na składników oznaczamy przez .

Przykład

Lista podziałów na składniki:



  • .

Obserwacja 6.23

Dla

  • ,
  • ,
  • ,
  • , dla
  • .

Dowód

Uzasadnimy jedynie ostatni punkt. Dla dowodu ograniczenia górnego liczby zauważmy, że interesujące nas podziały liczby są rozwiązaniami równania , a tych, jak już wiemy, jest dokładnie .

Z drugiej strony dowolny podział liczby generuje co najwyżej rozwiązań równania (generuje dokładnie , 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.

End of proof.gif

Ograniczenie górne dla można poprawić:

Obserwacja 6.24



Dowód

Dla podziału definiujemy



Zauważmy, że wszystkie liczby są różne oraz



A zatem podziały liczby na składników stoją w bijektywnej odpowiedniości z podziałami liczby na parami różnych składników. Każdy podział na parami różnych składników generuje dokładnie rozwiązań równania



gdzie . Wiemy zaś, że to ostatnie równanie posiada co najwyżej rozwiązań. A zatem ciągów , a tym samym podziałów na składników, jest co najwyżej .

End of proof.gif

Ostatnia obserwacja pozwala na opisanie granicznego zachowania liczb przy ustalonym .

Wniosek 6.25

Dla dowolnego



Dość skutecznym narzędziem do badania podziałów liczb naturalnych są tzw. diagramy Ferrersa.

Diagram Ferrersa dla podziału składa się z wierszy o odpowiednio elementach.

SW 6.3.swf
SW 6.4.swf

Przykład

Użyteczność diagramów Ferrersa ilustrują dowody kilku nastepnych obserwacji.

Obserwacja 6.26

Liczba jest równa liczbie podziałów liczby (na dowolną liczbę składników) o największym składniku równym .

Dowód

Odwracając o stopni diagram podziału liczby na składników otrzymamy diagram podziału liczby , którego największy składnik równy jest . Oczywiście jest to odwzorowanie bijektywne, gdyż odwracając z powrotem o stopni otrzymamy ten wyjściowy diagram.

End of proof.gif

Obserwacja 6.27

Liczba jest równa liczbie podziałów na co najwyżej składników.

Dowód

Wycinając ostatnią kolumnę w diagramie podziału liczby na składników otrzymamy podział liczby na co najwyżej składników. Łatwo zauważyc, że jest to odwzorowanie bijektywne.

End of proof.gif