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.
Dla skończonych i rozłącznych zbiorów \( A \) i \( B \) mamy:
\( \vert A\cup B\vert=\vert A\vert+\vert B\vert. \)
Dowód
Niech liczności zbiorów \( \vert A\vert=m \), \( \vert B\vert=n \) będą poświadczone bijekcjami \( f:\mathbb{Z}_m \to A \) i \( g:\mathbb{Z}_n \to B \). Wtedy funkcja \( h:\mathbb{Z}_{m+n}\to A\cup B \) zadana przez:
\( h(x)= \left\{ \begin{array} {ll} f(x), & \textrm{dla }x\in{\{ {0,\ldots,m-1} \}\ } \\ g(x-m), & \textrm{dla } x\in{\{ {m,\ldots,m+n-1} \}\ } \end{array} \right.\)
jest bijekcją. Istotnie, skoro zbiory \( A \) i \( B \) są rozłączne, to dla dowolnych \( x_1\in{\{ {0,\ldots,m-1} \}\ } \), \( x_2\in{\{ {m,\ldots,m+n-1} \}\ } \) zachodzi \( h(x_1)\neq h(x_2) \). Ponadto restrykcje \( h \) do zbiorów zbiorów \( {\{ {0,\ldots,m-1} \}\ } \) i \( {\{ {m,\ldots,m+n-1} \}\ } \) 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ą.
Ł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:
\( \vert A_1\cup\ldots\cup A_n\vert=\vert A_1\vert+\ldots+\vert A_n\vert. \)
Więcej pracy wymaga analiza sytuacji, gdy zbiory \( A,B \) nie są rozłączne.
Dla zbiorów skończonych \( {\{ {A_1,A_2,\ldots,A_n} \}\ } \) zachodzi
\( \begin{align*} & & \vert A_1\cup A_2\cup\ldots\cup A_n\vert\ =\ \sum_{I\subseteq{\{ {1,\ldots,n} \}\ }}(-1)^{\vert I\vert+1}\vert\bigcap_{i\in I}A_i\vert \\ & & \begin{array} {lr} = \vert A_1\vert+\vert A_2\vert+\vert A_3\vert+\ldots & +\vert A_{n-2}\vert+\vert A_{n-1}\vert+\vert A_n\vert \\ -\vert A_1\cap A_2\vert-\vert A_1\cap A_3\vert-\ldots & -\vert A_{n-2}\cap A_n\vert-\vert A_{n-1}\cap A_n\vert \\ +\vert A_1\cap A_2 \cap A_3\vert+\ldots & +\vert A_{n-2}\cap A_{n-1} \cap A_n\vert \\ -\vert A_1\cap A_2 \cap A_3\cap A_4\vert-\ldots & -\vert A_{n-3}\cap A_{n-2}\cap A_{n-1} \cap A_n\vert \\ +\ldots & \\ (-1)^{n+1}\vert A_1\cap A_2\cap\ldots\cap A_n\vert & \end{array} \end{align*} \)
W szczególności, \( \vert A\cup B\vert=\vert A\vert+\vert B\vert-\vert A\cap B\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
\( \begin{align*} |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| \end{align*} \)
skąd już natychmiast dostajemy:
\( \vert A\cup B\vert=\vert A\vert+\vert B\vert-\vert A\cap B\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:
\( \begin{align*} \vert\bigcup_{k=1}^nA_k\vert\ =\ \vert\bigcup_{k=1}^{n-1}A_k\vert+\vert A_n\vert-\vert\bigcup_{k=1}^{n-1}A_k\cap A_n\vert. \end{align*} \)
Wykorzystując założenie indukcyjne dla wartości \( n-1 \) zachodzi
\( \begin{align*} \vert\bigcup_{k=1}^nA_k\vert & =\sum_{I\subseteq{\{ {1,\ldots,n-1} \}\ }}(-1)^{\vert I\vert+1}\vert\bigcap_{i\in I}A_i\vert+\vert A_n\vert-\sum_{I\subseteq{\{ {1,\ldots,n-1} \}\ }}(-1)^{\vert I\vert+1}\vert\bigcap_{i\in I}A_i\cap A_n\vert \\ & =\sum_{I\subseteq{\{ {1,\ldots,n-1} \}\ }}(-1)^{\vert I\vert+1}\vert\bigcap_{i\in I}A_i\vert+\sum_{I\subseteq{\{ {1,\ldots,n-1} \}\ }}(-1)^{\vert I\cup{\{ {n} \}\ }\vert+1}\vert\bigcap_{i\in I\cup{\{ {n} \}\ }}A_i\vert. \end{align*} \)
Rodzina wszystkich podzbiorów \( I \) zbioru liczb \( {\{ {1,\ldots,n} \}\ } \) można podzielić na dwie rozłączne rodziny:
W rezultacie otrzymujemy, że
\( \begin{align*}\vert\bigcup_{k=1}^nA_k\vert\ =\ \sum_{I\subseteq{\{ {1,\ldots,n} \}\ }}(-1)^{\vert I\vert+1}\vert\bigcap_{i\in I}A_i\vert,\end{align*} \)
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 \( \vert A_1\cup\ldots\cup A_n\vert=\vert A_1\vert\cup\ldots\cup\vert A_n\vert \). Zatem jeśli każda szufladka ma co najwyżej \( r \) obiektów, to w sumie jest co najwyżej \( nr \) obiektów.
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={\{ {(x,y): x\in X, y\in Y} \}\ }. \)
Dla skończonych zbiorów \( X,Y \):
\( \vert X\times Y\vert=\vert X\vert\cdot\vert Y\vert. \)
Dowód
Najpierw pokażemy, że \( \vert\mathbb{Z}_m\times\mathbb{Z}_n\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 \( {\{ {-n+1,\ldots,n-1} \}\ } \), 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{\{ {0,\ldots,n-1} \}\ } \) takie, że \( y=in+j=f(i,j) \), co było do udowodnienia.
Załóżmy teraz, że \( \vert X\vert=m \) i \( \vert Y\vert=n \). Wtedy, z poczynionej wyżej obserwacji, dowód Zasady Mnożenia jest natychmiastowy, gdyż
\( \vert X\times Y\vert=\vert\mathbb{Z}_m\times \mathbb{Z}_n\vert=m\cdot n=\vert X\vert\cdot\vert Y\vert. \)
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ą?
Zbiór potegowy, lub inaczej zbiór podzbiorów, zbioru \( X \) oznaczamy przez \( \mathcal{P}(X) \).
Przykład
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 \( {\{ {a,b} \}\ } \) ma następujące cztery podzbiory:
\( \emptyset,{\{ {a} \}\ }, {\{ {b} \}\ }, {\{ {a,b} \}\ } \)
a zbiór trzyelementowy \( {\{ {a,b,c} \}\ } \) ma osiem podzbiorów:
\( \emptyset, {\{ {a} \}\ }, {\{ {b} \}\ }, {\{ {c} \}\ }, {\{ {a,b} \}\ }, {\{ {a,c} \}\ }, {\{ {b,c} \}\ }, {\{ {a,b,c} \}\ } \)
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:
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 {\{ {a} \}\ } \) 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ę. 0
Obserwacja 3.8
Dla dowolnego, skończonego zbioru \( X \)
\( \vert\mathcal{P}(X)\vert=2^{\vert X\vert}. \)