Informatyka MIMUW

Zliczanie funkcji

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

Obserwacja 3.9

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

$\vert Y^X\vert=\vert Y\vert^{\vert X\vert}.$

Dowód

Niech $X={\{ {x_0,\ldots,x_{m-1}} \}\ }$ oraz $Y={\{ {y_0,\ldots, y_{n-1}} \}\ }$. 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{\vert Y\vert\times\ldots\times\vert Y\vert}_{m\ razy} =n^m= \vert Y\vert^{\vert X\vert}.$

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 ${\{ {\textrm{Bartek},\textrm{Paweł},\textrm{Piotrek}} \}\ }$ 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 ${\{ {0,1,2,3} \}\ }$ w dziesięcioelementowy zbiór cyfr ${\{ {0,1,\ldots,9} \}\ }$. 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}{ll} {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{\{ {x\in X:f(x)=1} \}\ }$ zbioru $X$. Nadto, odpowiedniość

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

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

Obserwacja 3.10

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

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

Dowód

Niech $X={\{ {x_0,\ldots,x_{m-1}} \}\ }$ i $Y={\{ {y_0,\ldots,y_{n-1}} \}\ }$. 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)$.

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 ${\{ {0,1,2,3} \}\ }$ w $10$-elementowy zbiór cyfr ${\{ {0,1,\ldots,9} \}\ }$. Zatem jest ich dokładnie $10\cdot9\cdot8\cdot7=5040$.

Obserwacja 3.11

Liczba bijekcji pomiędzy skończonymi zbiorami $X$ i $Y$, gdzie $\vert X\vert=\vert Y\vert$ wynosi $\vert X\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 $\vert f(X)\vert < \vert Y\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$.

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