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 Zn 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:
|A∪B|=|A|+|B|.
Dowód
Niech liczności zbiorów |A|=m, |B|=n będą poświadczone bijekcjami f:Zm→A i g:Zn→B. Wtedy funkcja h:Zm+n→A∪B zadana przez:
h(x)={f(x),dla x∈{0,…,m−1} g(x−m),dla x∈{m,…,m+n−1}
jest bijekcją. Istotnie, skoro zbiory A i B są rozłączne, to dla dowolnych x1∈{0,…,m−1} , x2∈{m,…,m+n−1} zachodzi h(x1)≠h(x2). Ponadto restrykcje h do zbiorów zbiorów {0,…,m−1} i {m,…,m+n−1} są injekcjami. A zatem h jest injekcją.
Dla dowodu surjektywności h weźmy dowolny element y∈A∪B. Załóżmy, że y∈A (w drugim przypadku dowód przebiega analogicznie). Wtedy z surjektywności f wiemy, że istnieje x∈Zm 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 A1,…,An skończonych i parami rozłącznych:
|A1∪…∪An|=|A1|+…+|An|.
Więcej pracy wymaga analiza sytuacji, gdy zbiory A,B nie są rozłączne.
Dla zbiorów skończonych {A1,A2,…,An} zachodzi
|A1∪A2∪…∪An| = ∑I⊆{1,…,n} (−1)|I|+1|⋂i∈IAi|=|A1|+|A2|+|A3|+…+|An−2|+|An−1|+|An|−|A1∩A2|−|A1∩A3|−…−|An−2∩An|−|An−1∩An|+|A1∩A2∩A3|+…+|An−2∩An−1∩An|−|A1∩A2∩A3∩A4|−…−|An−3∩An−2∩An−1∩An|+…(−1)n+1|A1∩A2∩…∩An|
W szczególności, |A∪B|=|A|+|B|−|A∩B|, o ile tylko A,B są skończone.
Dowód
Zaczniemy od dowodu drugiego zdania. Ponieważ trzy zbiory A−B,A∩B i B−A są parami rozłączne i sumują się do (A−B)∪(A∩B)∪(B−A)=A∪B, na mocy Wniosku 3.7 mamy:
|A∪B|=|(A−B)∪(A∩B)∪(B−A)|=|A−B|+|A∩B|+|B−A|
skąd
|A∪B|+|A∩B|=|A−B|+|A∩B|+|B−A|+|A∩B|=(|A−B|+|A∩B|)+(|B−A|+|A∩B|)=|(A−B)∪(A∩B)|+|(B−A)∪(A∩B)|=|A|+|B|
skąd już natychmiast dostajemy:
|A∪B|=|A|+|B|−|A∩B|. (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:
|n⋃k=1Ak| = |n−1⋃k=1Ak|+|An|−|n−1⋃k=1Ak∩An|.
Wykorzystując założenie indukcyjne dla wartości n−1 zachodzi
|n⋃k=1Ak|=∑I⊆{1,…,n−1} (−1)|I|+1|⋂i∈IAi|+|An|−∑I⊆{1,…,n−1} (−1)|I|+1|⋂i∈IAi∩An|=∑I⊆{1,…,n−1} (−1)|I|+1|⋂i∈IAi|+∑I⊆{1,…,n−1} (−1)|I∪{n} |+1|⋂i∈I∪{n} Ai|.
Rodzina wszystkich podzbiorów I zbioru liczb {1,…,n} można podzielić na dwie rozłączne rodziny:
W rezultacie otrzymujemy, że
|n⋃k=1Ak| = ∑I⊆{1,…,n} (−1)|I|+1|⋂i∈IAi|,
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 Ai 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 |A1∪…∪An|=|A1|∪…∪|An|. 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×Y={(x,y):x∈X,y∈Y} .
Dla skończonych zbiorów X,Y:
|X×Y|=|X|⋅|Y|.
Dowód
Najpierw pokażemy, że |Zm×Zn|=m⋅n. W tym celu pokażemy, że funkcja
f:Zm×Zn∋(i,j)↦in+j∈Zmn
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≤i′, wtedy (i′−i)n=j−j′. Lewa strona równości jest wielokrotnością n, zaś prawa leży w zbiorze {−n+1,…,n−1} , gdyż j,j′∈Zn. 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∈Zmn. Niech i będzie największą liczbą taką, że in≤y. Wtedy y<(i+1)n zatem istnieje j∈{0,…,n−1} takie, że y=in+j=f(i,j), co było do udowodnienia.
Załóżmy teraz, że |X|=m i |Y|=n. Wtedy, z poczynionej wyżej obserwacji, dowód Zasady Mnożenia jest natychmiastowy, gdyż
|X×Y|=|Zm×Zn|=m⋅n=|X|⋅|Y|.
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 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:
∅,{a} ,{b} ,{a,b}
a zbiór trzyelementowy {a,b,c} ma osiem podzbiorów:
∅,{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 pn oznacza liczbę podzbiorów zbioru n-elementowego. Na podstawie dotychczasowych przykładów mamy:
n0123…pn1248…
i można wysunąć hipotezę, że w ogólności pn=2n. Ale jak ją uzasadnić?
Załóżmy, że znamy liczbę pn i chcemy policzyć pn+1. Niech więc zbiór Z ma n+1 elementów, czyli po usunięciu ze zbioru Z elementu a∈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 pn.
Każdy zaś podzbiór pierwszego typu, czyli A⊆Z takie, że a∈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∈A⊆Z, jest postaci A′∪{a} dla pewnego A′⊆Z′. A zatem podzbiorów zbioru Z, w których jest element a jest też tyle ile podzbiorów zbioru Z′, tzn. pn.
Łącznie więc zbiór Z ma pn+pn podzbiorów, czyli pn+1=2⋅pn Teraz już bez trudu stwierdzamy, że to wraz z warunkiem p0=1 jest spełnione przez
pn=2n
co można łatwo uzasadnić przez indukcję. 0
Obserwacja 3.8
Dla dowolnego, skończonego zbioru X
|P(X)|=2|X|.