Z Skrypty dla studentów Ekonofizyki UPGOW
Spis treści |
Funkcje
Ten fragment wykładu przypomina poznany już wcześniej materiał. Służy jedynie ustaleniu terminologii i notacji.
Szablon:Kotwica o dziedzinie \(X\) i przeciwdziedzinie \(Y\) to dowolna relacja \(f \subseteq X \times Y\) taka, że:
- \(\forall x\in X \ \exists y \in Y \ \ \left\langle x,y \right\rangle\in f\)
- \(\forall x\in X \ \forall y_1,y_2\in Y \ \ \left(\left\langle x,y_1 \right\rangle\in f \wedge \left\langle x,y_2 \right\rangle\in f\right) \rightarrow y_1=y_2\)
Pierwszy warunek mówi, że każdy element dziedziny ma jakąś wartość przypisaną funkcją \(f\). Drugi, że taka wartość jest co najwyżej jedna (dowolne dwie są bowiem równe). W skrócie oba warunki możemy zapisać łącznie jako
gdzie kwantyfikator \(\exists!\) oznacza istnieje dokładnie jeden.
- Ważne jest
- wykorzystanie wszystkich elementów dziedziny: każdemu elementowi dziedziny ...
- i jednoznaczność: jest przyporządkowany dokładnie jeden element przeciwdziedziny,
- nie wyklucza to sytuacji, gdy np. dwóm elementom dziedziny przyporządkowany jest ten sam element przeciwdziedziny,
- nie każdy element przeciwdziedziny musi być wykorzystany, tzn. mogą istnieć takie elementy przeciwdziedziny, które nie są przyporządkowane żadnemu elementowi dziedziny,
- dziedzina i przeciwdziedzina mogą być tym samym zbiorem.
Notacja:
- Piszemy \(f : X \longrightarrow Y\) lub \(X \stackrel{f}{\longrightarrow} Y\) na oznaczenie funkcji o nazwie \(f\), której dziedziną jest zbiór \(X\), a przeciwdziedziną zbiór \(Y\).
- elementy dziedziny nazywamy argumentami funkcji
- elementy przeciwdziedziny im przyporządkowane nazywamy wartościami funkcji.
- Piszemy \(f(x) = y\) lub \(f : x \mapsto y\) na oznaczenie tego, że funkcja \(f\) elementowi \(x\) przyporządkowuje element \(y\)
- mówimy wtedy, że \(y\) jest wartością funkcji \(f\) na argumencie \(x\).
- Często podaje się przepis na funkcję, wykorzystując
- operacje arytmetyczne: \(f(x) = 3x + 7\)
- lub inne powszechnie znane funkcje \(g(x) = 2\sin(x)\cos(x)\).
- W powyższych przykładach dziedziny i przeciwdziedziny można się domyślić (zapewne liczby rzeczywiste), ale dla ścisłości powinno się je podać, np. \(f : \mathbb{R} \longrightarrow \mathbb{R}\).
Przykłady funkcji
Najczęściej będziemy się zajmowali funkcjami, które działają na liczbach (dziedziną i przeciwdziedziną będą zbiory liczbowe, np. \(\mathbb{N}, \mathbb{R}\)), ale można mówić o funkcjach na różnych zbiorach.
- \(f : \mathbb{N} \ni n \mapsto 2n \in \mathbb{N}\),
- jest zwartym zapisem, że \(f\) jest funkcją postaci \(f : \mathbb{N} \longrightarrow \mathbb{N}\)
daną przepisem \(f(n) = 2n\) - jako przeciwdziedzinę określiliśmy zbiór liczb naturalnych,
ale w istocie wartościami tej funkcji są tylko liczby parzyste
- jest zwartym zapisem, że \(f\) jest funkcją postaci \(f : \mathbb{N} \longrightarrow \mathbb{N}\)
- \(g : \mathbb{N} \longrightarrow \mathbb{R}, \ g(n) = n/2\),
- określenie \(g : \mathbb{N} \longrightarrow \mathbb{N}\) nie byłoby tu prawidłowe, gdyż wartość \(n/2\) nie zawsze jest liczbą naturalną
- \(h : \mathbb{N} \longrightarrow {\left\{ {13} \right\}\ }, \ h(n) = 13\),
- to też jest poprawnie określona funkcja, mimo że niezbyt frapująca (tzw. funkcja stała)
- \(f : \mathbb{N} \longrightarrow \mathbb{N}, \ f(n) = (1 + 3 + 5 + ... + (2n+1))^n\).
- takie określenie też jest poprawne, choć nie od razu widać, ile to jest
- \(g : \mathbb{R} \ni x \mapsto \sin\frac{x}{\pi}\in \mathbb{R}\) jest całkiem poprawną funkcją.
- \(h : \mathbb{R} \ni x \mapsto \sin\frac{\pi}{x}\in \mathbb{R}\),
- to określenie (mimo, że podobne do poprzedniego) jest błędne:
nie da się policzyć wartości \(h(0)\);
należałoby więc napisać np. \(h : \mathbb{R}-{\left\{ {0} \right\}\ } \longrightarrow \mathbb{R}\)
- to określenie (mimo, że podobne do poprzedniego) jest błędne:
- \({\left\{ {0,1} \right\}\ }^* \ni w \mapsto w1 \in {\left\{ {0,1} \right\}\ }^*\),
- to funkcja określona na słowach nad alfabetem dwuelementowym \({\left\{ {0,1} \right\}\ }\)
- każdemu słowu przypisuje to słowo rozszerzone na końcu o symbol \(1\)
- \(d: {\left\{ {0,1} \right\}\ }^* \longrightarrow \mathbb{N}, \ d(w) = \) długość słowa \(w \)
Szablon:Kotwica to funkcja:
gdzie
- liczby \(a_n, a_{n-1}, \ldots, a_1,a_0\) zwane są współczynnikami wielomianu
- mówimy więc o wielomianach o współczynnikach
- naturalnych - jeśli \(a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{N}\)
- całkowitych - jeśli \(a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{Z}\)
- wymiernych - jeśli \(a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{Q}\)
- rzeczywistych - jeśli \(a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{R}\)
- liczba \(n\) zwana jest stopniem wielomianu, ale tylko o ile \(a_n \neq 0\).
- mówimy więc o wielomianach o współczynnikach
Surjekcje, injekcje i bijekcje
Szablon:Kotwica to funkcja \(f : X \longrightarrow Y\) spełniająca warunek
\(\forall y\in Y \ \exists x\in X \ \ f(x) = y \)
- Intuicyjnie, funkcja jest surjekcją, jeśli jej cała przeciwdziedzina jest wykorzystana, tzn. każdy jej element jest wartością funkcji dla jakiegoś elementu dziedziny,
- surjekcje często są nazywane funkcjami "na",
- piszemy też wtedy \(f : X \twoheadrightarrow Y\).
<flash>file=SW_2.2.swf|width=250|height=200</flash>
Szablon:Kotwica to funkcja \(f : X \longrightarrow Y\) spełniająca warunek:
\(\forall x_1,x_2 \in X \ \ x_1\neq x_2 \rightarrow f(x_1)\neq f(x_2) \)
- Intuicyjnie, funkcja jest injekcją, jeśli różnym elementom dziedziny funkcja przyporządkowuje różne elementy przeciwdziedziny,
- injekcje często są nazywane funkcjami różnowartościowymi,
- piszemy też wtedy \(f : X \hookrightarrow Y\).
<flash>file=SW_2.3.swf|width=250|height=200</flash>
Szablon:Kotwica to funkcja, która jest jednocześnie surjekcją i injekcją.
Funkcje odwrotne
Traktując funkcję \(f : X \longrightarrow Y\) jako relację \(f \subseteq X \times Y\) (zbiór par), możemy rozważać relację \(f^{-1}\) odwrotną do \(f\).
Kiedy ta relacja jest funkcją?
- ponieważ \(f^{-1}\) ma spełniać warunek, że każdy element dziedziny \(f^{-1}\) (tzn. zbioru \(Y\)) ma przypisaną jakąś wartość, oznacza to, że sama funkcja \(f\) wyczerpuje wszystkie elementy przeciwdziedziny, a zatem, że \(f\) jest surjekcją,
- nadto \(f^{-1}\) ma przypisywać dokładnie jeden taki element, czyli że każdy element z \(Y\) jest przypisany poprzez \(f\) jednemu elementowi z \(X,\) a zatem \(f\) musi być injekcją.
A zatem: funkcja posiada funkcję odwrotną, wtedy i tylko wtedy, gdy jest bijekcją.
- Nieformalnie tworzenie funkcji odwrotnej polega na odwracaniu strzałek.
- Gdyby \(f\) nie była surjekcją, to przy próbie odwrócenia strzałek niektóre elementy zbioru \(Y\) nie miałyby przyporządkowanego żadnego elementu z \(X\).
- Gdyby zaś \(f\) nie była injekcją, to przy próbie odwrócenia strzałek niektóre strzałki byłyby "rozdwojone".
Składanie funkcji
Szablon:Kotwica funkcji \(f : X \longrightarrow Y\) i funkcji \(g : Y \longrightarrow Z\) to funkcja
określona dla wszystkich argumentów \(x \in X\) jako \((gf)(x) = g(f(x))\).
- Nieformalnie - najpierw obliczamy wartość funkcji \(f\) dla elementu \(x\),
a następnie obliczamy wartość funkcji \(g\) dla wyniku tego obliczenia; czyli "idziemy dalej wzdłuż następnej strzałki"
- Piszemy \(gf\) (a nie \(fg\)) na oznaczenie złożenia, w którym najpierw obliczana jest wartość funkcji \(f\), a potem funkcji \(g\).
- W praktyce, przy złożeniu \(gf\), dziedzina funkcji \(g\) nie musi być tym samym zbiorem, co przeciwdziedzina funkcji \(f\) - wystarczy, by była większa.
Widzieliśmy, że nie zawsze \(fg = gf\).
Funkcje wielu zmiennych
- Funkcja dwóch zmiennych to funkcja, której dziedziną jest zbiór par (zamiast pojedynczych elementów).
- Piszemy np. \(f : X \times Y \longrightarrow Z\).
- Zatem funkcja taka każdej parze \((x,y)\in X \times Y\) przyporządkowuje dokładnie jeden element \(f(x,y) \in Z\).
- Podobnie można zdefiniować funkcje trzech i więcej zmiennych.
Zliczanie zbiorów
Gdy chcemy policzyć liczbę samochodów na parkingu zazwyczaj wskazujemy na kolejne samochody odliczając: jeden, dwa, trzy, itd., aż do momentu gdy każdy samochód zostanie wskazany. Wtedy ostatnia liczba, którą wypowiedzieliśmy jest uważana za liczbę samochodów na parkingu.
Aby wprowadzić matematyczny model procedury zliczania definiujemy początkowe odcinki liczb naturalnych:
\(\aligned \mathbb{Z}_0&=\emptyset,\\ \mathbb{Z}_1&={\left\{ {0} \right\}\ },\\ \mathbb{Z}_2&={\left\{ {0,1} \right\}\ },\\ &\vdots\\ \mathbb{Z}_k&={\left\{ {0,\ldots,k-1} \right\}\ }. \endaligned\)
Załóżmy, że na parkingu stoi \(n\) samochodów. Zliczając je wybieramy elementy \(\mathbb{Z}_n\) (zazwyczaj kolejne liczby) i przypisujemy je do samochodów na parkingu. Uwaga: wybierając liczby z \(\mathbb{Z}_n\) zaczynamy od \(0\) i kończymy na \(n-1\) (na ogół nie-informatycy zliczają od \(1\) do \(n\)). Określamy zatem w trakcie tego zliczania bijekcję \(f:\mathbb{Z}_n\rightarrow S\), gdzie \(S\) jest zbiorem samochodów na parkingu. W istocie jest to bijekcja, bo dwa różne samochody mają różne numery (injektywność) i każdy samochód jest policzony (surjektywność).
<flash>file=SW 2.5.swf|width=250|height=250</flash>
Szablon:Dowod\) jest injekcją z \(\mathbb{Z}_{n_0-1}\) w \(\mathbb{Z}_{m-1}\), czyli \(n_0-1\in S\) co stoi w sprzeczności z minimalnością \(n_0\) w \(S\).
Jeśli \(m-1\in f({\left\{ {0,\ldots,n_0-2} \right\}\ })\), to niech \(a\) i \(b\) będą takimi liczbami, że \(f(a)=m-1\) i \(f(n_0-1)=b\).
Wtedy funkcja \(g:\ N_{n_0-1}\rightarrow\mathbb{Z}_{m-1}\) zadana przez
jest injekcją, bo dla \(x_1,x_2\in\mathbb{Z}_{n_0-1}-{\left\{ {a} \right\}\ }\) zachodzi \(g(x_1)=g(x_2)\rightarrow x_1=x_2\) i dodatkowo \(b\notin g(\mathbb{Z}_{n_0}-{\left\{ {a} \right\}\ })=f(\mathbb{Z}_{n_0}-{\left\{ {a} \right\}\ })\). Zatem znów \(n_0-1\in S\), co stoi w sprzeczności z minimalnością \(n_0\) w \(S\). }}
Szablon:Kotwica to zbiór bijektywny z pewnym zbiorem postaci \(\mathbb{Z}_n\).
Szablon:Kotwica to zbiór, który nie jest skończony.
Jeśli \(X\) jest zbiorem skończonym, to Wniosek 3.4 gwarantuje nam, że \(X\) jest bijektywny z dokładnie jednym zbiorem postaci \(\mathbb{Z}_n\). Rozważając skończony zbiór \(n\)-elementowy \(X\), często używamy notacji \(X={\left\{ {x_0,x_1,\ldots,x_{n-1}} \right\}\ }\) ukrywającej w sobie bijekcję postaci \(\mathbb{Z}_n \longrightarrow X\).
Szablon:Kotwica skończonego zbioru \(X\), to jedyna liczba naturalna \(n\) taka, że istnieje bijekcja z \(\mathbb{Z}_n\) w \(X\). Liczbę te oznaczamy
przez \(\left\vert X\right\vert\).
Szablon:Przyklad \right\}\ }\). Oczywiście \(\mathbb{P} \neq \emptyset\), bo \(0\in \mathbb{P}\). Nadto suma wszystkich \( p_i \) jest ograniczeniem zbioru \(\mathbb{P}\), a więc, z Zasady Maksimum, \(\mathbb{P}\) posiada element największy, powiedzmy \(p_0\). Ponieważ \(p_0\) jest największą liczbą parzystą, \(p_0+2\notin \mathbb{P}\), co oczywiście daje sprzeczność. }}
Szablon:Dowod\) jest również injekcją. A zatem złożenie \(g^{-1} f|_{\mathbb{Z}_{n+1}}\) jest injekcją z \(\mathbb{Z}_{n+1}\) w \(\mathbb{Z}_n\), co stoi w sprzeczności z Obserwacją 3.3. }}
Szablon:Kotwica to zbiór skończony lub bijektywny z \(\mathbb{N}\).
Zasada Szufladkowa
Wróćmy jeszcze do Obserwacji 3.3 - formalnej podstawy zliczania skończonych zbiorów. Ma ona także bardziej praktyczną interpretację. Jest to formalne ujęcie faktu powszechnie znanego jako Zasada Szufladkowa Dirichleta (wierzy się, że jako pierwszy opisał ja Dirichlet w 1834).
- W grupie \(13\) osób muszą być co najmniej dwie, które urodziły się w tym samym miesiącu.
Czasem, umiejętnie dobierając "pudełka" można pokazać bardziej zaskakujące fakty...
Szablon:Przyklad \right\}\ }\) można wybrać dwa rozłączne podzbiory, dające tę samą sumę.
Istotnie:
- Szuflady poetykietujmy liczbami reprezentującymi możliwe sumy liczb w co najwyżej 10-cio elementowych podzbiorach zbioru \({\left\{ {1,2,3,\ldots,100} \right\}\ }\). Ponieważ największa możliwa taka suma to \(91+92+93+\cdots+99+100 = 955\), to mamy \( 955 \) szuflad z etykietami: \(0,1,2,3,\ldots, 955\)
- z drugiej strony \(10\)-cio elementowy zbiór \({\left\{ {a_1,a_2,\ldots,a_{10}} \right\}\ }\) ma \(2^{10}=1024\) podzbiory, więc muszą być dwa podzbiory zbioru \({\left\{ {a_1,a_2,\ldots,a_{10}} \right\}\ }\) o tej samej sumie.
- Te dwa podzbiory nie muszą być rozłączne. Ale jeśli z obu z nich usuniemy wspólne liczby, to pozostałe dalej będą dawać takie same sumy, a powstałe zbiory będą już rozłączne.
}}
Zasady zliczania
Bardzo często w tym kursie będziemy stać przed problemem zliczenia pewnego skończonego zbioru obiektów. Skrajnie niewygodne i nieefektywne byłoby, gdybyśmy za każdym razem konstruowali bijekcję z \(\mathbb{Z}_n\) w nasz zbiór dla pewnego naturalnego \( n \). Na szczęście istnieje wiele reguł pozwalających szybciej zliczać obiekty kombinatoryczne. Poniżej przedstawiamy te podstawowe. Pierwsza z nich jest bardzo prosta i w sposób intuicyjny stosowana od początków cywilizacji.
Szablon:Kotwica
Dla skończonych i rozłącznych zbiorów \(A\) i \(B\) mamy:
Łatwy dowód indukcyjny pozwala uogólnić zasadę dodawania na dowolnie wiele skończonych zbiorów.
Więcej pracy wymaga analiza sytuacji, gdy zbiory \(A,B\) nie są rozłączne.
Szablon:Kotwica
Dla zbiorów skończonych \({\left\{ {A_1,A_2,\ldots,A_n} \right\}\ }\) zachodzi
W szczególności, \(\left\vert A\cup B\right\vert=\left\vert A\right\vert+\left\vert B\right\vert-\left\vert A\cap B\right\vert\), o ile tylko \( A,B \) są skończone.
skąd już natychmiast dostajemy:
W sytuacji dowolnie wielu \(n\) zbiorów użyjemy rozumowania indukcyjnego. Oczywiście \( n=1,2 \) twierdzenie jest prawdziwe. Załóżmy, że \( n>2 \). Na mocy równości (1) otrzymujemy:
Wykorzystując założenie indukcyjne dla wartości \( n-1 \) zachodzi
Rodzina wszystkich podzbiorów \( I \) zbioru liczb \({\left\{ {1,\ldots,n} \right\}\ }\) można podzielić na dwie rozłączne rodziny:
- pierwsza składa się z tych \(I\), które nie zawierają \(n\), czyli \({\left\{ {I:I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }} \right\}\ }, \)
- druga jest rodziną tych \(I\), które zawierają \(n\), czyli \({\left\{ {I\cup{\left\{ {n} \right\}\ }:I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }} \right\}\ } \).
W rezultacie otrzymujemy, że
co kończy dowód.
Wniosek 3.7 pozwala uogólnić Zasadę Szufladkową. Załóżmy, że pewna ilość obiektów jest rozmieszczona w \(n\) szufladach. Niech \(A_i\) będzie zbiorem obiektów w \(i\)-tej szufladce. Ponieważ zbiory obiektów w różnych szufladach są rozłączne, to ilość obiektów we wszystkich szufladach wynosi \(\left\vert A_1\cup\ldots\cup A_n\right\vert=\left\vert A_1\right\vert\cup\ldots\cup\left\vert A_n\right\vert\). Zatem jeśli każda szufladka ma co najwyżej \(r\) obiektów, to w sumie jest co najwyżej \(nr\) obiektów.
Szablon:Kotwica
Jeśli \(m\) obiektów rozmieszczonych jest w \(n\) szufladach i \(m>nr\), dla pewnego naturalnego \(r\), to istnieje szufladka z co najmniej \(r+1\) obiektami.
Przypomnijmy, że Szablon:Kotwica (produkt) zbiorów \(X\) i \(Y\) to zbiór
Szablon:Kotwica
Dla skończonych zbiorów \(X,Y\):
Zliczanie podzbiorów
Szablon:Kotwica, lub inaczej zbiór podzbiorów, zbioru \(X\) oznaczamy przez \(\mathcal{P}(X)\).
Szablon:Przyklad \right\}\ }\) i \(\left\vert\mathcal{P}({\left\{ {\emptyset} \right\}\ })\right\vert=2\) }}
i można wysunąć hipotezę, że w ogólności \(p_n = 2^n\). Ale jak ją uzasadnić?
Załóżmy, że znamy liczbę \(p_n\) i chcemy policzyć \(p_{n+1}\). Niech więc zbiór \(Z\) ma \(n+1\) elementów, czyli po usunięciu ze zbioru \(Z\) elementu \(a\in Z\) dostajemy \(n\)-elementowy zbiór \(Z'\). Podobnie jak w dowodzie Zasady Włączania-Wyłączania, podzbiory zbioru \(Z\) można podzielić na dwa typy:
- albo mają w sobie element \(a\),
- albo go nie mają.
W drugim przypadku są to podzbiory zbioru \(Z'\). Jest więc ich dokładnie \(p_n\).
Każdy zaś podzbiór pierwszego typu, czyli \(A \subseteq Z\) takie, że \(a\in A\) jest jednoznacznie wyznaczony przez swoje pozostałe elementy, tzn. elementy różne od \(a\). A zatem każdy taki zbiór \(A\), że \(a \in A \subseteq Z\), jest postaci \(A'\cup {\left\{ {a} \right\}\ }\) dla pewnego \(A'\subseteq Z'\). A zatem podzbiorów zbioru \(Z\), w których jest element \(a\) jest też tyle ile podzbiorów zbioru \(Z'\), tzn. \(p_n\).
Łącznie więc zbiór \(Z\) ma \(p_n + p_n\) podzbiorów, czyli \(p_{n+1} = 2\cdot p_n \) Teraz już bez trudu stwierdzamy, że to wraz z warunkiem \(p_0 = 1\) jest spełnione przez
co można łatwo uzasadnić przez indukcję.
Zliczanie funkcji
Szablon:Kotwica postaci \(X \longrightarrow Y\) oznaczamy przez \(Y^X\).
Szablon:Dowod \right\}\ }\) oraz \(Y={\left\{ {y_0,\ldots, y_{n-1}} \right\}\ }\). Każda funkcja \(f: X \longrightarrow Y\) to krotka wartości dla kolejnych \(x_i\):
A więc zbiór funkcji z \(X\) w \(Y\) jest równoliczny z \(Y^m\). Z Zasady Mnożenia otrzymujemy więc:
}}
Szablon:Przyklad \right\}\ }\) w pięcioelementowy zbiór marek piwa. A więc istnieje \(5^3=125\) sposobów spożycia pierwszej kolejki. I tyleż sposobów dla każdej nastepnej...... }}
Posługując się Obserwacją 3.8 udowodnimy jeszcze raz wzór na ilość podzbiorów skończonego zbioru. Zatem Obserwację 3.9 możemy traktować jako uogólnienie Obserwacji 3.8.
Szablon:Dowod \right\}\ }\) i \(Y={\left\{ {y_0,\ldots,y_{n-1}} \right\}\ }\). Każdą injekcję z \(X\) w \(Y\) możemy utożsamić z uporządkowanym wyborem \(m\) różnych elementów ze zbioru \(Y\):
Pierwszy element możemy wybrać na \(n\) sposobów, drugi na \(n-1\), bo musi być różny od poprzednio wybranego, trzeci już tylko na \(n-2\) sposoby, itd., aż wreszcie \(m\)-ty na \(n-m+1\) sposobów. Zatem liczba injekcji równa jest \(n(n-1)\cdot\ldots\cdot(n-m+1)\). }}
Permutacje
Szablon:Kotwica zbioru skończonego \(X\) to bijekcja z \(X\) w \(X\).
Szablon:Kotwica oznaczamy przez \(S_n\), a permutacje bedziemy w tym kursie oznaczać małymi literami greckimi.
Ponieważ permutacje są bijekcjami, to natychmiast z Obserwacji 3.2 dostajemy:
Następne spostrzeżenie jest natychmiastowym wnioskiem z Obserwacji 3.11.
Permutację \(\alpha\) zbioru \(X={\left\{ {x_0,\ldots,x_{n-1}} \right\}\ }\) wygodnie jest identyfikować z krotką \((\alpha(x_0),\ldots,\alpha(x_{n-1}))\in X^n\). Często też permutację interpretuje się jako uporządkowanie zbioru \(X\).
<flash>file=7ksiazek.jpg|width=250|height=250</flash>
<flash>file=MD1-2-8.swf|width=250|height=250</flash>
Szablon:Kotwica zbioru \(n\)-elementowego \(X\) to taka permutacja zbioru \(X\), dla której \({\left\{ {x,\alpha(x),\alpha^2(x),\ldots,\alpha^{n-1}(x)} \right\}\ }=X\), przy dowolnym \(x\in X\). Łatwo zauważyć, że jeśli dla pewnego \(x_0\in X\) mamy \({\left\{ {x,\alpha(x),\alpha^2(x),\ldots,\alpha^{n-1}(x)} \right\}\ }=X\), to jest tak dla wszystkich \(x\in X\), czyli \(\alpha\) jest cyklem na \(X\). Cykl \(\alpha\) zbioru \(X\) zapisujemy jako \((x,\alpha(x),\ldots,\alpha^{n-1}(x))\) dla dowolnie wybranego \(x\in X\).
Rozkład permutacji na rozłączne cykle
Dowolną permutację \(\alpha\) zbioru \(X\) można rozłożyć na rozłączne cykle w sposób następujący:
- wybierz dowolny element \(x\in X\), który nie jest jeszcze w żadnym cyklu,
- iteruj permutację \(\alpha\) otrzymując kolejno: \(\alpha(x),\alpha^2(x),\alpha^3(x),\ldots \) aż do uzyskania \(\alpha^j(x)=x\),
- dodaj do rozkładu cykl \(x,\ldots,\alpha^{j-1}(x)\),
- jeśli w zbiorze \(X\) pozostały jeszcze elementy niepokryte przez żaden cykl, to wróć do pierwszego punktu.
Jeśli permutacja \(\alpha\) złożona jest z \(k\) rozłącznych cykli, to zapisujemy \(\alpha=(x_0,\ldots)(x_1,\ldots)\ldots(x_{k-1},\ldots)\), gdzie w kolejnych nawiasach są elementy kolejnych cykli startujące od odpowiednio: \(x_0,\ldots,x_{k-1}\).