Matematyka dyskretna 1/Wykład 3: Zliczanie zbiorów i funkcji

From Studia Informatyczne

Spis treści

Funkcje

Ten fragment wykładu przypomina poznany już wcześniej materiał. Służy jedynie ustaleniu terminologii i notacji.

Funkcja 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

Wielomian 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

Grafika:Surjekcja.png

Przykład surjekcji

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

Przykład

Funkcja \mathbb{R} \ni x \mapsto x^3 \in \mathbb{R} jest surjekcją.
Funkcja \mathbb{Q} \ni x \mapsto x^3 \in \mathbb{Q} nie jest surjekcją.
Funkcja \mathbb{N} \ni x \mapsto 2x \in \mathbb{N} nie jest surjekcją.
Funkcja \mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q} jest surjekcją.
Funkcja \mathbb{Z} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z} jest surjekcją.
Funkcja \mathbb{R} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z} jest surjekcją.
Funkcja \mathbb{Z} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Q} nie jest suriekcją.
Funkcja \mathbb{R} \ni x \mapsto \sin{x} \in \mathbb{R} nie jest surjekcją.
Funkcja {\left\{ {0,1} \right\}\ }^* \ni w \mapsto w1 \in {\left\{ {0,1} \right\}\ }^* nie jest suriekcją.
Funkcja {\left\{ {0,1} \right\}\ }^* \ni w \mapsto d(w) \in \mathbb{N} jest suriekcją.



Przykład injekcji

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

Przykład

Funkcja \mathbb{R} \ni x \mapsto x^3 \in \mathbb{R} jest injekcją.
Funkcja \mathbb{R} \ni x \mapsto x^2 \in \mathbb{R} nie jest injekcją.
Funkcja \mathbb{Z} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z} jest injekcją.
Funkcja \mathbb{R} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z} nie jest injekcją.
Funkcja \mathbb{N} \ni x \mapsto 2x \in \mathbb{N} jest injekcją.
Funkcja \mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q} jest injekcją.
Funkcja \mathbb{R} \ni x \mapsto \sin{x} \in \mathbb{R} nie jest injekcją.
Funkcja {\left\{ {0,1} \right\}\ }^* \ni w \mapsto w1 \in {\left\{ {0,1} \right\}\ }^* jest injekcją.
Funkcja {\left\{ {0,1} \right\}\ }^* \ni w \mapsto d(w) \in \mathbb{N} nie jest injekcją.



Przykład bijekcji

Bijekcja to funkcja, która jest jednocześnie surjekcją i injekcją.

Przykład

Funkcja \mathbb{R} \ni x \mapsto x^3 \in \mathbb{R} jest bijekcją.
Funkcja \mathbb{Q} \ni x \mapsto x^3 \in \mathbb{Q} nie jest bijekcją.
Funkcja \mathbb{N} \ni x \mapsto 2x \in \mathbb{N} nie jest bijekcją.
Funkcja \mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q} jest bijekcją.
Funkcja \mathbb{Z} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z} jest bijekcją.
Funkcja \mathbb{R} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z} nie jest bijekcją.
Funkcja \mathbb{Z} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Q} nie jest bijekcją.
Funkcja {\left\{ {0,1} \right\}\ }^* \ni w \mapsto w1 \in {\left\{ {0,1} \right\}\ }^* nie jest bijekcją.
Funkcja {\left\{ {0,1} \right\}\ }^* \ni w \mapsto d(w) \in \mathbb{N} nie jest bijekcją.

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

Przykład

  • Funkcja f : \mathbb{R} \ni x \mapsto 2x \in \mathbb{R} jest bijekcją, a zatem posiada funkcję odwrotną. Tę funkcję odwrotną można wyliczyć: skoro y = f(x) = 2x, to f^{-1}(y) = x = y/2. Zatem f^{-1} : \mathbb{R} \ni x \mapsto x/2 \in \mathbb{R}.
  • Funkcja \mathbb{R} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z} nie jest injekcją. Nie posiada więc funkcji odwrotnej.
  • Funkcja \mathbb{N} \ni x \mapsto 2x \in \mathbb{N} nie jest surjekcją. Nie posiada więc funkcji odwrotnej. Ale rozważając tę funkcję z przeciwdziedziną \mathbb{P} będącą zbiorem liczb parzystych, tzn. \mathbb{N} \ni x \mapsto 2x \in \mathbb{P} staje się ona bijekcją i posiada funkcję odwrotną \mathbb{P} \ni x \mapsto x/2 \in \mathbb{N}.
  • Funkcja \mathbb{R} \ni x \mapsto x^2 \in \mathbb{R} nie jest ani injekcją ani surjekcją. Nie posiada więc funkcji odwrotnej. Surjektywność można by "uratować", rozważając
f : \mathbb{R} \ni x \mapsto x^2 \in [0, +\infty).


Wciąż jednak brakowałoby injektywności. Ograniczając jednak, tę funkcję do liczb nieujemnych, tzn. traktując ją jako:


f|_{[0, +\infty)}: [0, +\infty) \ni x \mapsto x^2 \in [0, +\infty),


staje się już bijekcją, więc posiada funkcję odwrotną, którą jest


[0, +\infty) \ni x \mapsto \sqrt{x} \in [0, +\infty).


Składanie funkcji

Złożenie 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.

Przykład

  • Niech f : \mathbb{N} \ni n \mapsto n + 2 \in \mathbb{N} i g : \mathbb{N} \ni n \mapsto 3n \in \mathbb{N}. Wówczas dla gf : \mathbb{N} \longrightarrow \mathbb{N} mamy (gf)(n) = g(f(n)) = g(n + 2) = 3(n + 2)= 3n+6 a dla fg : \mathbb{N} \longrightarrow \mathbb{N} mamy (fg)(n) = f(g(n)) = f(3n) = 3n + 2.

Morał: złożenia fg i gf to (na ogół) różne funkcje.

  • Niech f : \mathbb{R} \ni x \mapsto \sin 3x \in \mathbb{R} i g : \mathbb{R} \ni x \mapsto  (x + \pi)^2 \in\mathbb{R}. Wówczas złożenie fg: \mathbb{R} \longrightarrow \mathbb{R} dane jest wzorem
(fg)(x) = f(g(x)) = f((x + \pi)^2) = \sin(3(x + \pi)^2).


Morał: Nie zawsze da się łatwo wyliczyć przepis na funkcję złożoną.

  • Gdy f : X \longrightarrow Y jest bijekcją, to istnieje funkcja odwrotna f^{-1} : Y \longrightarrow X. Jeśli złożymy f^{-1} f, to uzyskamy funkcję X \longrightarrow X, która "nic nie robi":
(f^{-1} f)(x) = f^{-1}(f(x)) = x.


Taka funkcja zwana jest identycznością na zbiorze X i oznaczana id_X. Podobnie - składając f f^{-1} : Y \longrightarrow Y, otrzymamy identyczność na zbiorze Y.

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

Obserwacja 3.1

Dla funkcji X \stackrel{h}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z \stackrel{f}{\longrightarrow} W zachodzi f(gh) = (fg)h.

Obserwacja 3.2

Nadto dla X \stackrel{f}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z mamy:

  • Jeśli f, g są surjekcjami, to gf jest surjekcją.
  • Jeśli f, g są injekcjami, to gf jest injekcją.
  • Jeśli f, g są bijekcjami, to gf jest bijekcją.
  • Pierwsza i trzecia z powyższych własności nie zachodzą, jeśli dziedzina funkcji g jest większa niż przeciwdziedzina funkcji f.

Przykład

Zbadaj czy dla funkcji X \stackrel{f}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z zachodzi:

  • jeśli gf jest surjekcją, to f jest surjekcją
  • jeśli gf jest surjekcją, to g jest surjekcją
  • jeśli gf jest injekcją, to f jest injekcją
  • jeśli gf jest injekcją, to g jest injekcją

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.

Przykład

Przykładem funkcji dwóch zmiennych są działania arytmetyczne:

  • \mathbb{R} \times \mathbb{R} \ni (x,y) \mapsto x+y \in \mathbb{R}
  • \mathbb{R} \times \mathbb{R} \ni (x,y) \mapsto x-y \in \mathbb{R}
  • \mathbb{R} \times \mathbb{R} \ni (x,y) \mapsto xy \in \mathbb{R}
  • \mathbb{R} \times \mathbb{R}-{\left\{ {0} \right\}\ } \ni (x,y) \mapsto \frac{x}{y} \in \mathbb{R}
  • \mathbb{N} \times \mathbb{N} \ni (x,y) \mapsto x^y \in \mathbb{N}

a także konkatenacja (sklejenie) słów

  • X^* \times X^* \ni (v,w) \mapsto vw \in X^*, gdzie vw oznacza słowo (krotkę) powstałe z doklejenia słowa w na końcu słowa v.

Zliczanie zbiorów

Liczenie samochodów na parkingu
Enlarge
Liczenie samochodów na parkingu

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

Obserwacja 3.3

Gdy m<n, to nie istnieje injekcja z \mathbb{Z}_n w \mathbb{Z}_m.



SW 2.5.swf

Dowód

Niech S będzie zbiorem liczb naturalnych n takich, że istnieje injekcja postaci f:\mathbb{Z}_m\rightarrow\mathbb{Z}_n, przy pewnym m<n. Oczywiście 0\notin S, bo nie istnieje liczba naturalna m taka, że 0\leq m<0. Także 1\notin S, bo nie istnieje funkcja z niepustego zbioru \mathbb{Z}_1 w pusty \mathbb{Z}_0. Dla dowodu niewprost załóżmy, że S jest niepusty. Wtedy, z Zasady Minimum, S ma element najmniejszy, powiedzmy math>n_0>1</math>. Istnieje zatem m<n_0 i injekcja f:\mathbb{Z}_{n_0}\rightarrow\mathbb{Z}_m. Analogicznie jak wcześniej m\neq 0 oraz m\neq 1, bo inaczej wszystkie elementy N_{n_0} musiałyby mieć tę samą wartość, co stoi w sprzeczności z injektywnością f. Zatem m-1 jest dodatnią liczbą naturalną.

Jeśli m-1\notin f({\left\{ {0,\ldots,n_0-2} \right\}\ }), to restrykcja f|_{\mathbb{Z}_{n_0-1}} 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.

image:End_of_proof.gif

Wniosek 3.4

Jeśli istnieje bijekcja ze zbioru \mathbb{Z}_m na \mathbb{Z}_n, to m=n.

Zbiór skończony to zbiór bijektywny z pewnym zbiorem postaci \mathbb{Z}_n.

Zbiór nieskończony 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.

Liczba elementów 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.

Przykład

Oczywiście \left\vert\mathbb{Z}_n\right\vert = n. W szczególności zbiór pusty ma, zgodnie z intuicją, liczbę elementów równą 0.

Przykład

Zbiór liczb parzystych \mathbb{P} jest nieskończony.

Dla dowodu niewprost załóżmy, że \left\vert\mathbb{P}\right\vert=k, tzn. \mathbb{P} = {\left\{ {p_0,\ldots,p_{k-1}} \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ść.

Obserwacja 3.5

Zbiór X jest nieskończony wtedy i tylko wtedy, gdy istnieje injekcja z \mathbb{N} w X.

Dowód

Załóżmy, że X jest nieskończony i zdefiniujmy indukcyjnie funkcję f:\mathbb{N}\longrightarrow X, kładąc:

  1. niech f(0) będzie dowolnym, wybranym elementem X,
  2. gdy f(0),\ldots,f(n) są już określone, wtedy niech f(n+1) będzie dowolnie wybranym elementem z X-{\left\{ {f(0),\ldots,f(n)} \right\}\ }.

To, że wyboru opisanego w punkcie drugim możemy zawsze dokonać, wynika wprost z nieskończoności zbioru X. Istotnie, gdyby zbiór X-{\left\{ {f(0),\ldots,f(n)} \right\}\ } był pusty, to f byłoby bijekcją \mathbb{Z}_{n+1} \longrightarrow X świadczącą o tym, że X jest skończony. Oczywiście, tak zdefiniowana funkcja f : \mathbb{N} \longrightarrow X jest injekcją.

Dla dowodu implikacji odwrotnej załóżmy, że istnieje injekcja f:\mathbb{N}\longrightarrow X oraz że X jest skończony tzn. że istnieje bijekcja g:\mathbb{Z}_n\longrightarrow X dla pewnego n. Zauważmy, że restrykcja f|_{\mathbb{Z}_{n+1}} 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.

image:End_of_proof.gif

Zbiór przeliczalny to zbiór skończony lub bijektywny z \mathbb{N}.

Przykład

  • zbiór pusty jest przeliczalny, bo jest skończony,
  • zbiór liczb parzystych jest przeliczalny, bo f(x)=2x jest bijekcją \mathbb{N}\longrightarrow\mathbb{P}
  • zbiór liczb całkowitych jest przeliczalny, bo


f(x)= \left\{ \begin{array} {cl} \frac{x}{2},&\textrm{dla parzystych } x, \\  \frac{-1-x}{2},&\textrm{dla nieparzystych } x, \end{array}  \right.


jest bijekcją z \mathbb{N} w \mathbb{Z}.

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

Wniosek 3.6 [Zasada Szufladkowa Dirichleta]

Jeśli n obiektów jest rozmieszczonych w m szufladach i n>m, to istnieje szuflada z przynajmniej dwoma obiektami.

Dowód

Zbiór obiektów jest bijektywny ze zbiorem \mathbb{Z}_n, zaś zbiór szuflad z \mathbb{Z}_m. Rozmieszczenie obiektów w szufladach to określenie funkcji z \mathbb{Z}_n w \mathbb{Z}_m. Ponieważ n>m to Obserwacja 3.3 mówi nam, ze funkcja ta nie jest injekcją, a zatem lokuje co najmniej dwa obiekty w tej samej szufladzie.

image:End_of_proof.gif

Przykład

Proste przykłady:

  • Wśród mieszkańców Krakowa co najmniej dwie osoby mają tę samą liczbę włosów na głowie.

Dowód

Rzeczywiście, liczba włosów na głowie człowieka nie przekracza 500 000, natomiast liczba mieszkańców Krakowa przekracza 800 000. Weźmy 500 000 szufladek ponumerowanych kolejnymi liczbami naturalnymi od 0 do 499 999 i wkładajmy do szufladki o danym numerze osoby, które mają taką liczbę włosów na głowie, jak numer szufladki. Ponieważ osób jest 800 000, a szufladek 500 000, z Zasady Szufladkowej wynika, że w jednej szufladce muszą znaleźć się co najmniej dwie osoby.

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

Dowód

Weźmy 12 szufladek z nazwami miesięcy i wkładajmy do nich osoby, które urodziły się w danym miesiącu. Ponieważ osób jest 13, a szufladek 12, w jednej z nich muszą być co najmniej dwie osoby.

image:End_of_proof.gif

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

Przykład

Pewna grupa osób wita się podając sobie ręce. Nikt nie wita się z samym sobą i żadna para osób nie wita się podwójnie. Czy muszą być dwie osoby, które witały taką samą liczbę osób?

  • Gdy jest n osób, to każda z nich przywita 0 lub 1 lub 2 lub ... n-1 osób.
  • Utwórzmy więc n szuflad z etykietami k=0,1,2,\ldots, n-1 i umieśćmy osobę w szufladzie o etykiecie k, jeśli witała się z dokładnie k osobami.
  • Skoro jest n osób i n szuflad, to ...
    niewiele z tego wynika  :-(
  • Ale... niewiele wynika tylko jeśli wszystkie szuflady będą zajęte, a tak jest w przypadku, gdy również dwa konkretne pudełka o etykietach 0 i n-1 są zajęte. Tyle, że nie jest to możliwe - nie może być osoby, która przywitała wszystkie pozostałe i równocześnie takiej, która nie przywitała nikogo.
  • A zatem n osób zajęło co najwyżej n-1 szuflad, więc w jednej z nich są co najmniej dwie osoby - takie, które przywitały tę samą liczbę osób.

Przykład

Wybierając n+1 liczb spośród 1,2,3,\ldots, 2n, wśród wybranych liczb zawsze znajdziemy dwie, z których jedna dzieli drugą.

Istotnie:

  • Określmy relacje xRy na liczbach naturalnych, tak by:
xRy \ \ \Leftrightarrow iloraz \frac{x}{y} jest potęgą (być może ujemną) liczby 2.


Oznacza to, że xRy jeśli liczby x, y mają ten sam największy czynnik nieparzysty.

  • Szufladami niech będą klasy równoważności relacji R.
  • Ile jest klas-szuflad dla liczb ze zbioru {\left\{ {1,2,3,\ldots, 2n} \right\}\ }? Co najwyżej n, gdyż tyle może być liczb nieparzystych w zbiorze {\left\{ {1, 2, ..., 2n} \right\}\ }.
  • Skoro wybrano n + 1, to rozkładając je do naszych szuflad jakieś dwie, powiedzmy a,b muszą trafić do wspólnej szuflady.

Oznacza to, że któryś z ilorazów \frac{a}{b}, \frac{b}{a} jest dodatnią potęgą dwójki, a zatem a dzieli b lub b dzieli a.

Przykład

Wybierzmy dowolnie 10 różnych liczb naturalnych a_1,a_2,\ldots,a_{10} spośród 1,2,3,\ldots,100. Pokażemy, że w zbiorze {\left\{ {a_1,a_2,\ldots,a_{10}} \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.

Zasada dodawania

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.


Dowód

Niech liczności zbiorów \left\vert A\right\vert=m, \left\vert B\right\vert=n będą poświadczone bijekcjami f:\mathbb{Z}_m\rightarrow A i g:\mathbb{Z}_n\rightarrow B. Wtedy funkcja h:\mathbb{Z}_{m+n}\rightarrow A\cup B zadana przez:


h(x)= \left\{ \begin{array} {ll} f(x),&\textrm{dla }x\in{\left\{ {0,\ldots,m-1} \right\}\ } \\  g(x-m),& \textrm{dla } x\in{\left\{ {m,\ldots,m+n-1} \right\}\ } \end{array}  \right.


jest bijekcją. Istotnie, skoro zbiory A i B są rozłączne, to dla dowolnych x_1\in{\left\{ {0,\ldots,m-1} \right\}\ }, x_2\in{\left\{ {m,\ldots,m+n-1} \right\}\ } zachodzi h(x_1)\neq h(x_2). Ponadto restrykcje h do zbiorów zbiorów {\left\{ {0,\ldots,m-1} \right\}\ } i {\left\{ {m,\ldots,m+n-1} \right\}\ } są injekcjami. A zatem h jest injekcją.

Dla dowodu surjektywności h weźmy dowolny element y\in A\cup B. Załóżmy, że y\in A (w drugim przypadku dowód przebiega analogicznie). Wtedy z surjektywności f wiemy, że istnieje x\in\mathbb{Z}_m takie, że f(x)=y. Ale h(x)=f(x)=y. Zatem h jest surjekcją.

image:End_of_proof.gif

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

Wniosek 3.7

Dla zbiorów A_1,\ldots,A_n skończonych i parami rozłącznych:


\left\vert A_1\cup\ldots\cup A_n\right\vert=\left\vert A_1\right\vert+\ldots+\left\vert A_n\right\vert.


Więcej pracy wymaga analiza sytuacji, gdy zbiory A,B nie są rozłączne.

Zasada włączania i wyłączania

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.

Dowód

Zaczniemy od dowodu drugiego zdania. Ponieważ trzy zbiory A - B, A\cap B i B- A są parami rozłączne i sumują się do (A - B) \cup (A\cap B) \cup (B- A) = A \cup B, na mocy Wniosku 3.7 mamy:


|A \cup B| = |(A - B) \cup (A\cap B) \cup (B- A)| =  |A - B| + |A\cap B| + |B- A|


skąd


\aligned |A \cup B| + |A \cap B|  & =|A - B| + |A\cap B| + |B- A| + |A\cap B| \\ & =(|A - B| + |A\cap B|) + (|B- A| + |A\cap B|)  \\ & =|(A - B) \cup (A\cap B)| + |(B- A) \cup (A\cap B)|  \\ & =|A| + |B| \endaligned
image:End_of_proof.gif


skąd już natychmiast dostajemy:


\left\vert A\cup B\right\vert=\left\vert A\right\vert+\left\vert B\right\vert-\left\vert A\cap B\right\vert.      (1)


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.

Uogólniona Zasada Szufladkowa

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 iloczyn kartezjański (produkt) zbiorów X i Y to zbiór


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

Zasada Mnożenia

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.


Dowód

Najpierw pokażemy, że \left\vert\mathbb{Z}_m\times\mathbb{Z}_n\right\vert=m \cdot n. W tym celu pokażemy, że funkcja


f:\mathbb{Z}_m\times\mathbb{Z}_n \ni (i,j) \mapsto in+j \in \mathbb{Z}_{mn}


jest bijekcją.

Dla dowodu injektywności załóżmy, że f(i,j)=f(i',j'), czyli in+j=i'n+j'. Bez straty ogólności możemy założyć, że i\leq i', wtedy (i'-i)n=j-j'. Lewa strona równości jest wielokrotnością n, zaś prawa leży w zbiorze {\left\{ {-n+1,\ldots,n-1} \right\}\ }, gdyż j,j'\in\mathbb{Z}_n. Ponieważ 0 jest jedyną wielokrotnością liczby n w tym zbiorze, to i'-i=0 i j-j'=0, co dowodzi injektywności f.

Dla dowodu surjektywności rozważmy y\in\mathbb{Z}_{mn}. Niech i będzie największą liczbą taką, że in\leq y. Wtedy y<(i+1)n zatem istnieje j\in{\left\{ {0,\ldots,n-1} \right\}\ } takie, że y=in+j=f(i,j), co było do udowodnienia.

Załóżmy teraz, że \left\vert X\right\vert=m i \left\vert Y\right\vert=n. Wtedy, z poczynionej wyżej obserwacji, dowód Zasady Mnożenia jest natychmiastowy, gdyż


\left\vert X\times Y\right\vert=\left\vert\mathbb{Z}_m\times \mathbb{Z}_n\right\vert=m\cdot n=\left\vert X\right\vert\cdot\left\vert Y\right\vert.


image:End_of_proof.gif

Przykład

Rozważ turniej rycerski między bractwem czerwonych a bractwem niebieskich. Bractwo czerwonych ma 12 rycerzy, bractwo niebieskich 15. Ile różnych indywidualnych pojedynków może być stoczonych, jeśli rycerze z tego samego bractwa nigdy ze sobą nie walczą?

  • Niech C i N będą zbiorami rycerzy, odpowiednio z bractwa czerwonych i z bractwa niebieskich,
  • każdy pojedynek może być interpretowany jako uporządkowana para (c,n), gdzie c\in C, n\in N. Zatem liczba pojedynków to liczność zbioru C\times N.
  • \left\vert C\times N\right\vert=\left\vert C\right\vert\cdot\left\vert N\right\vert=12\cdot15=300.

Zliczanie podzbiorów

Zbiór potegowy, lub inaczej zbiór podzbiorów, zbioru X oznaczamy przez \mathcal{P}(X).

Przykład

  • \mathcal{P}(\emptyset)={\left\{ {\emptyset} \right\}\ } i \left\vert\mathcal{P}(\emptyset)\right\vert=1
  • \mathcal{P}({\left\{ {\emptyset} \right\}\ })={\left\{ {\emptyset,{\left\{ {\emptyset} \right\}\ }} \right\}\ } i \left\vert\mathcal{P}({\left\{ {\emptyset} \right\}\ })\right\vert=2

Przykład

Ile podzbiorów ma skończony zbiór n-elementowy? Łatwo jest odpowiedzieć na to pytanie dla małych liczb n. Np. zbiór {\left\{ {a,b} \right\}\ } ma następujące cztery podzbiory:


\emptyset,{\left\{ {a} \right\}\ }, {\left\{ {b} \right\}\ }, {\left\{ {a,b} \right\}\ }


a zbiór trzyelementowy {\left\{ {a,b,c} \right\}\ } ma osiem podzbiorów:


\emptyset, {\left\{ {a} \right\}\ }, {\left\{ {b} \right\}\ }, {\left\{ {c} \right\}\ }, {\left\{ {a,b} \right\}\ }, {\left\{ {a,c} \right\}\ }, {\left\{ {b,c} \right\}\ }, {\left\{ {a,b,c} \right\}\ }


Spróbujmy odpowiedzieć na to pytanie w ogólnej sytuacji i w sposób rekurencyjny.

Niech p_n oznacza liczbę podzbiorów zbioru n-elementowego. Na podstawie dotychczasowych przykładów mamy:


\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ę.


Obserwacja 3.8

Dla dowolnego, skończonego zbioru X


\left\vert\mathcal{P}(X)\right\vert=2^{\left\vert X\right\vert}.


Zliczanie funkcji

Zbiór funkcji postaci X \longrightarrow Y oznaczamy przez Y^X.

Obserwacja 3.9

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


\left\vert Y^X\right\vert=\left\vert Y\right\vert^{\left\vert X\right\vert}.


Dowód

Niech X={\left\{ {x_0,\ldots,x_{m-1}} \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}.


image:End_of_proof.gif

Przykład

Trzech kolegów: Bartek, Paweł i Piotrek spotkali się w pubie tuż po zdanym egzaminie z matematyki dyskretnej. Okazało się, że jest pięć marek piwa do wyboru. Na ile sposobów mogą oni wypić pierwszą kolejkę?

Każdy wybór marki piwa przez wszystkie 3 osoby możemy interpretować jako funkcję ze zbioru {\left\{ {\textrm{Bartek},\textrm{Paweł},\textrm{Piotrek}} \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......

Przykład

Kod PIN jest kodem autoryzującym właściciela karty bankomatowej. Składa się on z 4 cyfr dziesiętnych. Ile jest różnych kodów PIN?

Każdy kod PIN to funkcja z czteroelementowego zbioru pozycji {\left\{ {0,1,2,3} \right\}\ } w dziesięcioelementowy zbiór cyfr {\left\{ {0,1,\ldots,9} \right\}\ }. Z Obserwacji 3.9 wynika że kodów PIN jest dokładnie 10^4=10000.

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.

Dowód

Alternatywny dowód Obserwacji 3.8
Zauważmy, że dowolny podzbiór A\subseteq X wyznacza jednoznacznie funkcję \chi_A:X\rightarrow \mathbb{Z}_2 w następujący sposób:


\chi_Y(x)= \left\{ \begin{array} {cl} 0,&\textrm{dla }x\in X- A \\  1,&\textrm{dla }x\in A \end{array}  \right.


Również każda funkcja f :X \longrightarrow \mathbb{Z}_2 wyznacza jednoznacznie podzbiór A_f{\left\{ {x\in X:f(x)=1} \right\}\ } zbioru X. Nadto, odpowiedniość


\mathcal{P}(X) \ni A \mapsto \chi_A \in \mathbb{Z}_2^X


jest bijektywna. Zatem \left\vert\mathcal{P}(X)\right\vert=\left\vert\mathbb{Z}_2^X\right\vert =2^{\left\vert X\right\vert}.

image:End_of_proof.gif

Obserwacja 3.10

Liczba injekcji ze zbioru skończonego X w zbiór skończony Y wynosi:


\left\vert Y\right\vert(\left\vert Y\right\vert-1)\cdot\ldots\cdot(\left\vert Y\right\vert-\left\vertX\right\vert+1)= \frac{\left\vert Y\right\vert!}{(\left\vert Y\right\vert-\left\vert X\right\vert)!}.


Dowód

Niech X={\left\{ {x_0,\ldots,x_{m-1}} \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).

image:End_of_proof.gif

Przykład

Ile jest PIN-ów, czyli cztero-elementowych słów złożonych z cyfr dziesiętnych, takich że żadna cyfra się nie powtarza?

Każdy PIN z niepowtarzającymi się cyframi to injekcja z cztero-elementowego zbioru pozycji {\left\{ {0,1,2,3} \right\}\ } w 10-elementowy zbiór cyfr {\left\{ {0,1,\ldots,9} \right\}\ }. Zatem jest ich dokładnie 10\cdot9\cdot8\cdot7=5040.

Obserwacja 3.11

Liczba bijekcji pomiędzy skończonymi zbiorami X i Y, gdzie \left\vert X\right\vert=\left\vert Y\right\vert wynosi \left\vert X\right\vert!.

Dowód

Pokażemy najpierw, że każda injekcja f: X \longrightarrow Y jest bijekcją. Istotnie, gdyby f nie było surjekcją, to f(X) byłoby właściwym podzbiorem zbioru Y. A zatem \left\vert f(X)\right\vert < \left\vert Y\right\vert i funkcja f : X \longrightarrow f(X) ustalałaby injekcję ze zbioru o większej liczbie elementów w zbiór o mniej liczny. A to nie jest możliwe na mocy Obserwacji 3.3. Udowodniliśmy, że liczba bijekcji z X w Y równa jest liczbie injekcji z X w Y, czyli, z Obserwacji 3.10), wynosi ona:


n(n-1)\cdot\ldots\cdot(n-n+2)(n-n+1)=n!.


Zauważmy jeszcze, że \emptyset \subseteq \emptyset \times \emptyset jest nie tylko funkcją \emptyset : \emptyset \longrightarrow \emptyset, ale i bijekcją i jest to jedyna bijekcja \emptyset \longrightarrow \emptyset.

image:End_of_proof.gif

Przykład

Na kurs tańca uczęszcza pięciu chłopaków i pięć dziewcząt. Większość kroków tanecznych ćwiczy się parami. Dla urozmaicenia pary często się zmieniają. Na ile sposobów może być wykonany jeden taniec?

Niech C będzie zbiorem chłopaków, a D zbiorem dziewcząt. Matematycznym modelem doboru par do tańca jest bijekcja f:C\rightarrow D. Zatem możliwych wyborów jest tyle samo co bijekcji pomiędzy 5-elementowymi zbiorami, czyli 5!=5\cdot4\cdot3\cdot2\cdot1=120.

Permutacje

Permutacja zbioru skończonego X to bijekcja z X w X.

Zbiór permutacji zbioru \mathbb{Z}_n oznaczamy przez S_n, a permutacje bedziemy w tym kursie oznaczać małymi literami greckimi.

Przykład

Rozważ funkcję \alpha:\mathbb{Z}_7\rightarrow\mathbb{Z}_7 zadaną przez poniższą tabelę:


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


Funkcja \alpha jest bijekcją z \mathbb{Z}_7 w \mathbb{Z}_7, zatem jest permutacją i \alpha\in S_7.

Przykład

Dla permutacji \alpha,\beta\in S_5 zadanych przez poniższą tabelę:


\begin{array} {|c||c|c|c|c|c|} \hline n&0&1&2&3&4\\ \hline \alpha(n)&4&2&3&0&1\\ \hline \beta(n)&2&3&1&4&0\\ \hline \end{array}


ich złożenia podane są poniżej:


\begin{array} {|c||c|c|c|c|c|} \hline n&0&1&2&3&4\\ \hline \beta\alpha(n)&0&1&4&2&3\\ \hline \alpha\beta(n)&3&0&2&1&4\\ \hline \end{array}


Zauważ, że oba złożenia także są permutacjami \mathbb{Z}_5.

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

Obserwacja 3.12

Dla dowolnych permutacji \alpha,\beta skończonego zbioru X:

  • \alpha\beta,\beta\alpha są permutacjami X,
  • \alpha^{-1} jest permutacją X taką, że \alpha\alpha^{-1}=id_{X}=\alpha^{-1}\alpha=.

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

Wniosek 3.13

Zbiór n-elementowy ma dokładnie n! permutacji, \left\vert S_n\right\vert=n!.

Przykład

Oto wszystkie (3!=6) permutacje zbioru S_3:


\begin{array} {ccccccccccc} 0&1&2&\qquad&0&1&2&\qquad&0&1&2\\ \downarrow&\downarrow&\downarrow&&\downarrow&\downarrow&\downarrow&&\downarrow&\downarrow&\downarrow\\ 0&1&2&\qquad&0&2&1&\qquad&1&0&2\\ \\ 0&1&2&\qquad&0&1&2&\qquad&0&1&2\\ \downarrow&\downarrow&\downarrow&&\downarrow&\downarrow&\downarrow&&\downarrow&\downarrow&\downarrow\\ 1&0&2&\qquad&2&0&1&\qquad&2&1&0 \end{array}



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.





Przykład

Na ile sposobów można poukładać koło siebie na półce 7 książek?

Na dokładnie tyle, ile jest permutacji zbioru siedmio-elementowego, a więc 7!=5040.

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

Przykład

Rozważmy \alpha\in S_6 daną przez

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

  • sekwencja 0, \alpha(0)=3, \alpha^2(0)=1, \alpha^3(0)=5, \alpha^4(0)=4, \alpha^5(0)=2 pokwywa całe \mathbb{Z}_6,
  • zatem \alpha=(0,3,1,5,4,2) jest cyklem.

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.

Dowód

Dla dowodu poprawności algorytmu rozkładu pokażemy najpierw, że iteracja w drugim punkcie zawsze osiąga element wyjściowy x. Ponieważ zbiór X jest skończony iteracja x,\alpha(x),\alpha^2(x)\ldots w pewnym kroku musi wrócić do elementu już rozważanego, zatem \alpha^i(x)=\alpha^j(x) dla pewnych i<j. Weźmy najmniejsze takie j, że \alpha^i(x)=\alpha^j(x) dla pewnego 0\leq i<j. Gdyby i\neq 0 to z faktu, że \alpha jest permutacją mamy \alpha^{i-1}(x)=\alpha^{j-1}(x), co stoi w sprzeczności z minimalnością j. A zatem \alpha^j(x)=x.

Pozostaje jeszcze pokazać, że otrzymane cykle są rozłączne. Załóżmy, że nie są i weźmy pierwszy napotkany element y=\alpha^i(x), który był już w którymś z poprzednich cykli. Zauważmy, że i>0 gdyż x był wybrany jako element nie pokryty przez żaden cykl (patrz punkt pierwszy). Wiemy, że istnieje element z w tym samym cyklu co y taki, że \alpha(z)=y, ale także \alpha(\alpha^{i-1}(x))=y. Ponieważ \alpha jest permutacją, otrzymujemy \alpha^{i-1}(x)=z, co stoi w sprzeczności z faktem, że y jest jedynym elementem z poprzedniego cyklu.

image:End_of_proof.gif

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


Przykład

Rozważmy jeszcze raz permutację \alpha\in S_7:


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


Rozkład \alpha na cykle:

  • 0, \alpha(0)=2, \alpha(2)=6, \alpha(6)=5, \alpha(5)=1, \alpha(1)=3, \alpha(3)=0,
  • 4, \alpha(4)=4,
  • \alpha=(026513)(4).