Processing math: 100%

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

Zasada dodawania

Dla skończonych i rozłącznych zbiorów A i B mamy:

|AB|=|A|+|B|.

Dowód

Niech liczności zbiorów |A|=m, |B|=n będą poświadczone bijekcjami f:ZmA i g:ZnB. Wtedy funkcja h:Zm+nAB zadana przez:

h(x)={f(x),dla x{0,,m1} g(xm),dla x{m,,m+n1} 

jest bijekcją. Istotnie, skoro zbiory A i B są rozłączne, to dla dowolnych x1{0,,m1} , x2{m,,m+n1}  zachodzi h(x1)h(x2). Ponadto restrykcje h do zbiorów zbiorów {0,,m1}  i {m,,m+n1}  są injekcjami. A zatem h jest injekcją.

Dla dowodu surjektywności h weźmy dowolny element yAB. Załóżmy, że yA (w drugim przypadku dowód przebiega analogicznie). Wtedy z surjektywności f wiemy, że istnieje xZm 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:

|A1An|=|A1|++|An|.

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 {A1,A2,,An}  zachodzi

|A1A2An| = I{1,,n} (1)|I|+1|iIAi|=|A1|+|A2|+|A3|++|An2|+|An1|+|An||A1A2||A1A3||An2An||An1An|+|A1A2A3|++|An2An1An||A1A2A3A4||An3An2An1An|+(1)n+1|A1A2An|

W szczególności, |AB|=|A|+|B||AB|, o ile tylko A,B są skończone.

Dowód

Zaczniemy od dowodu drugiego zdania. Ponieważ trzy zbiory AB,AB i BA są parami rozłączne i sumują się do (AB)(AB)(BA)=AB, na mocy Wniosku 3.7 mamy:

|AB|=|(AB)(AB)(BA)|=|AB|+|AB|+|BA|

skąd

|AB|+|AB|=|AB|+|AB|+|BA|+|AB|=(|AB|+|AB|)+(|BA|+|AB|)=|(AB)(AB)|+|(BA)(AB)|=|A|+|B|

skąd już natychmiast dostajemy:

|AB|=|A|+|B||AB|.      (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:

|nk=1Ak| = |n1k=1Ak|+|An||n1k=1AkAn|.

Wykorzystując założenie indukcyjne dla wartości n1 zachodzi

|nk=1Ak|=I{1,,n1} (1)|I|+1|iIAi|+|An|I{1,,n1} (1)|I|+1|iIAiAn|=I{1,,n1} (1)|I|+1|iIAi|+I{1,,n1} (1)|I{n} |+1|iI{n} Ai|.

Rodzina wszystkich podzbiorów I zbioru liczb {1,,n}  można podzielić na dwie rozłączne rodziny:

  • pierwsza składa się z tych I, które nie zawierają n, czyli {I:I{1,,n1} } ,
  • druga jest rodziną tych I, które zawierają n, czyli {I{n} :I{1,,n1} } .

W rezultacie otrzymujemy, że

|nk=1Ak| = I{1,,n} (1)|I|+1|iIAi|,

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 |A1An|=|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.

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×Y={(x,y):xX,yY} .

Zasada Mnożenia

Dla skończonych zbiorów X,Y:

|X×Y|=|X||Y|.

Dowód

Najpierw pokażemy, że |Zm×Zn|=mn. W tym celu pokażemy, że funkcja

f:Zm×Zn(i,j)in+jZmn

jest bijekcją.

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

Dla dowodu surjektywności rozważmy yZmn. Niech i będzie największą liczbą taką, że iny. Wtedy y<(i+1)n zatem istnieje j{0,,n1}  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|=mn=|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ą?

  • 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 cC, nN. Zatem liczba pojedynków to liczność zbioru C×N.
  • |C×N|=|C||N|=1215=300.

Zliczanie podzbiorów

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

Przykład

  • P()={}  i |P()|=1
  • P({} )={,{} }  i |P({} )|=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 {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:

n0123pn1248

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 aZ 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 pn.

Każdy zaś podzbiór pierwszego typu, czyli AZ takie, że aA jest jednoznacznie wyznaczony przez swoje pozostałe elementy, tzn. elementy różne od a. A zatem każdy taki zbiór A, że aAZ, jest postaci A{a}  dla pewnego AZ. 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=2pn 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|.