Z Skrypty dla studentów Ekonofizyki UPGOW

Spis treści [ukryj] 1 Funkcje 1.1 Notacja: 1.2 Przykłady funkcji 1.3 Surjekcje, injekcje i bijekcje 1.4 Funkcje odwrotne 1.5 Składanie funkcji 1.6 Funkcje wielu zmiennych 2 Zliczanie zbiorów 2.1 Zasada Szufladkowa 3 Zasady zliczania 3.1 Szablon:Kotwica 3.2 Szablon:Kotwica 3.3 Szablon:Kotwica 3.4 Szablon:Kotwica 3.5 Zliczanie podzbiorów 4 Zliczanie funkcji 5 Permutacje 5.1 Rozkład permutacji na rozłączne cykle

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

$\forall x\in X \ \exists! y \in Y \ \ \left\langle x,y \right\rangle\in f,$

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
• $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}$
• ${\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:

$x \mapsto a_nx^n + a_{n-1}x^{n-1} + \ldots + a_2x^2 + a_1 x + a_0$

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

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

Szablon:Przyklad

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

Szablon:Przyklad

Szablon:Kotwica to funkcja, która jest jednocześnie surjekcją i injekcją.

Szablon:Przyklad

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

Szablon:Przyklad

Składanie funkcji

Szablon:Kotwica funkcji $f : X \longrightarrow Y$ i funkcji $g : Y \longrightarrow Z$ to funkcja

$gf: X \longrightarrow Z$

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"

$X \longrightarrow Y \longrightarrow Z$

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

Szablon:Przyklad

Widzieliśmy, że nie zawsze $fg = gf$.

Szablon:Obserwacja

Szablon:Obserwacja

Szablon:Przyklad

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.

Szablon:Przyklad

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ść).

Szablon:Obserwacja

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

$g(x)= \left\{ \begin{array} {cl} f(x),& \textrm{dla} \quad x\neq a \\ b,& \textrm{dla} \quad x=a \end{array} \right.$

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:Wniosek

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

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:Obserwacja

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

Szablon:Przyklad

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

Szablon:Wniosek

Szablon:Dowod

Szablon:Przyklad

Szablon:Dowod

• W grupie $13$ osób muszą być co najmniej dwie, które urodziły się w tym samym miesiącu.

Szablon:Dowod

Czasem, umiejętnie dobierając "pudełka" można pokazać bardziej zaskakujące fakty...

Szablon:Przyklad

Szablon:Przyklad

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:

$\left\vert A\cup B\right\vert=\left\vert A\right\vert+\left\vert B\right\vert.$

Szablon:Dowod

Łatwy dowód indukcyjny pozwala uogólnić zasadę dodawania na dowolnie wiele skończonych zbiorów.

Szablon:Wniosek

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

$\aligned &&\left\vert A_1\cup A_2\cup\ldots\cup A_n\right\vert\ =\ \sum_{I\subseteq{\left\{ {1,\ldots,n} \right\}\ }}\left(-1\right)^{\left\vert I\right\vert+1}\left\vert\bigcap_{i\in I}A_i\right\vert\\ &&\begin{array} {lr} = \left\vert A_1\right\vert+\left\vert A_2\right\vert+\left\vert A_3\right\vert+\ldots &+\left\vert A_{n-2}\right\vert+\left\vert A_{n-1}\right\vert+\left\vert A_n\right\vert\\ -\left\vert A_1\cap A_2\right\vert-\left\vert A_1\cap A_3\right\vert-\ldots&-\left\vert A_{n-2}\cap A_n\right\vert-\left\vert A_{n-1}\cap A_n\right\vert\\ +\left\vert A_1\cap A_2 \cap A_3\right\vert+\ldots&+\left\vert A_{n-2}\cap A_{n-1} \cap A_n\right\vert\\ -\left\vert A_1\cap A_2 \cap A_3\cap A_4\right\vert-\ldots&-\left\vert A_{n-3}\cap A_{n-2}\cap A_{n-1} \cap A_n\right\vert\\ +\ldots&\\ \left(-1\right)^{n+1}\left\vert A_1\cap A_2\cap\ldots\cap A_n\right\vert& \end{array} \endaligned$

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.

Szablon:Dowod

skąd już natychmiast dostajemy:

Szablon:Wzor

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:

$\aligned \left\vert\bigcup_{k=1}^nA_k\right\vert\ =\ \left\vert\bigcup_{k=1}^{n-1}A_k\right\vert+\left\vert A_n\right\vert-\left\vert\bigcup_{k=1}^{n-1}A_k\cap A_n\right\vert. \endaligned$

Wykorzystując założenie indukcyjne dla wartości $n-1$ zachodzi

$\aligned \left\vert\bigcup_{k=1}^nA_k\right\vert&=\sum_{I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }}\left(-1\right)^{\left\vert I\right\vert+1}\left\vert\bigcap_{i\in I}A_i\right\vert+\left\vert A_n\right\vert-\sum_{I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }}\left(-1\right)^{\left\vert I\right\vert+1}\left\vert\bigcap_{i\in I}A_i\cap A_n\right\vert\\ &=\sum_{I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }}\left(-1\right)^{\left\vert I\right\vert+1}\left\vert\bigcap_{i\in I}A_i\right\vert+\sum_{I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }}\left(-1\right)^{\left\vert I\cup{\left\{ {n} \right\}\ }\right\vert+1}\left\vert\bigcap_{i\in I\cup{\left\{ {n} \right\}\ }}A_i\right\vert. \endaligned$

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

$\aligned\left\vert\bigcup_{k=1}^nA_k\right\vert\ =\ \sum_{I\subseteq{\left\{ {1,\ldots,n} \right\}\ }}\left(-1\right)^{\left\vert I\right\vert+1}\left\vert\bigcap_{i\in I}A_i\right\vert,\endaligned$

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

$X\times Y={\left\{ {(x,y): x\in X, y\in Y} \right\}\ }.$

Szablon:Kotwica

Dla skończonych zbiorów $X,Y$:

$\left\vert X\times Y\right\vert=\left\vert X\right\vert\cdot\left\vert Y\right\vert.$

Szablon:Dowod

Szablon:Przyklad

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

Szablon:Przyklad

$\begin{array} {|c||c|c|c|c|c} \hline n&0&1&2&3&\ldots\\ \hline p_n&1&2&4&8&\ldots\\ \hline \end{array}$

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

$p_n = 2^n$

co można łatwo uzasadnić przez indukcję.

Szablon:Obserwacja

Zliczanie funkcji

Szablon:Kotwica postaci $X \longrightarrow Y$ oznaczamy przez $Y^X$.

Szablon:Obserwacja

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

$(f(x_0),f(x_1),\ldots,f(x_{m-1}))\in \underbrace{Y\times\ldots\times Y}_{m\ razy}.$

A więc zbiór funkcji z $X$ w $Y$ jest równoliczny z $Y^m$. Z Zasady Mnożenia otrzymujemy więc:

$\vert\underbrace{Y\times\ldots\times Y}_{m\ razy}\vert =\underbrace{\left\vert Y\right\vert\times\ldots\times\left\vert Y\right\vert}_{m\ razy} =n^m= \left\vert Y\right\vert^{\left\vert X\right\vert}.$

}}

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

Szablon:Przyklad

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

Szablon:Obserwacja

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

$f(x_0),f(x_1),\ldots,f(x_{m-1}).$

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

Szablon:Przyklad

Szablon:Obserwacja

Szablon:Dowod

Szablon:Przyklad

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.

Szablon:Przyklad

Szablon:Przyklad

Ponieważ permutacje są bijekcjami, to natychmiast z Obserwacji 3.2 dostajemy:

Szablon:Obserwacja

Następne spostrzeżenie jest natychmiastowym wnioskiem z Obserwacji 3.11.

Szablon:Wniosek

Szablon:Przyklad

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

Szablon:Przyklad

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

Szablon:Przyklad

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:

1. wybierz dowolny element $x\in X$, który nie jest jeszcze w żadnym cyklu,
2. iteruj permutację $\alpha$ otrzymując kolejno: $\alpha(x),\alpha^2(x),\alpha^3(x),\ldots$ aż do uzyskania $\alpha^j(x)=x$,
3. dodaj do rozkładu cykl $x,\ldots,\alpha^{j-1}(x)$,
4. jeśli w zbiorze $X$ pozostały jeszcze elementy niepokryte przez żaden cykl, to wróć do pierwszego punktu.

Szablon:Dowod

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

Szablon:Przyklad