Uvod u diskretnu matematiku [0th ed.] 9531975361 [PDF]

Zitiervorschau

Darko Zˇ ubrinic´ MATEMATIKA 3 Uvod u diskretnu matematiku

G

o

ISBN 953-197-536-1

Darko Zˇ ubrinic´ Redoviti profesor Fakulteta elektrotehnike i racˇunarstva Zavod za primijenjenu matematiku

MATEMATIKA 3 Uvod u diskretnu matematiku

0. izdanje

Zagreb, 2006.

c Prof. dr. sc. Darko Zˇ ubrinic´, 2006.

Urednik Sandra Gracˇan, dipl. inzˇ .

Nakladnik Element, Zagreb

Dizajn ovitka Edo Kadic´

Tisak Element, Zagreb

Nijedan dio ove knjige ne smije se preslikavati niti umnazˇ ati na bilo koji nacˇin, bez pismenog dopusˇtenja nakladnika

PREDGOVOR Moguc´e je tek priblizˇ no opisati sˇto sve obuhvac´a diskretna matematika. Ona se bavi relacijama na konacˇnim skupovima, rekurzivnim relacijama, algoritmima, matematicˇkom logikom, Booleovim algebrama, kombinatorikom, particijama, teorijom grafova, raznim diskretnim algebarskim strukturama (npr. konacˇnim grupama, prstenima, poljima), itd. Algebarskom strukturom zovemo bilo koji skup na kojem je definirana barem jedna operacija (obicˇno binarna). Pojam ‘diskretne’ matematike zahtijeva pojasˇnjenje. Njen temelj cˇine ‘diskretni’ skupovi. Tu obicˇno mislimo na a) skup koji ima konacˇno mnogo elemenata (konacˇan skup), npr. skup 0 1 , 1 2 3 , skup slova abecede, skup znakova na tipkovnici racˇunala, b) ili beskonacˇan skup cˇiji se elementi mogu poredati u slijed (prebrojiv skup). Takvi su npr. skupovi prirodnih i cijelih brojeva. Vidjet c´emo da se elementi skupa realnih brojeva ne mogu poredati u slijed. Pojam ‘diskretan’ stoji nasuprot pojmu ‘kontinuiran’ (neprekinut). Npr. skup realnih brojeva R je ‘kontinuiran’, dok je skup cijelih brojeva Z diskretan. Slicˇno, za neku funkciju kazˇ emo da je diskretna ako je skup njenih vrijednosti diskretan skup. Razumije se, ‘diskretnu’ i ‘kontinuiranu’ matematiku nije moguc´e strogo odijeliti. Npr. moguc´e su i funkcije koje su dijelom diskretne, a dijelom ‘kontinuirane’. Mnogi rezultati diskretne matematike dobivaju se uz pomoc´ diferencijalnog racˇuna, dakle metodama ‘kontinuirane’ matematike, i obratno.

f g f

y

g

y y=f(n)

1

2

y=f(x)

3

4

n

1

2

3

4

x

Sl. 1. Diskretna i neprekinuta funkcija. Pojedine tvrdnje nose nazive teoremi, propozicije, leme. Teoremom (stavkom) zovemo neku vazˇ niju tvrdnju, dok je lema pomoc´na tvrdnja, priprema za dokaz nekog teorema ili propozicije. Propozicija po vazˇ nosti stoji negdje izmedu teorema i leme. Korolarom zovemo posljedak nekog teorema ili propozicije. Oznaka Teorem 3 oznacˇava trec´i teorem u tekuc´em odjeljku, a Teorem 5.2.3 oznacˇava Teorem 3 u Odjeljku 5.2. Slicˇno za propozicije, leme, korolare i primjere. U decimalnom zapisu realnih brojeva rabit c´emo radije decimalnu tocˇku nego decimalni zarez. Knjigu je otipkao sam autor rabec´i Knuthov tipografski sistem TEX (i netrivijalnu nadogradnju ostvarenu u poduzec´u Element), koji je zasˇtitni znak American Mathematical Society. O TEX-u vidi http://www.tugboat.org. Veliku zahvalnost dugujem dr. Andrei Aglic´ Aljinovic´, dr. Mariu Pavcˇevic´u, dr. Mariu Krnic´u, mr. Nevenu Grbcu i mr. Kristijanu Tabaku na pomoc´i i dopusˇtenju da izbor zadataka s rjesˇenjima s pismenih ispita na FER-u (Fakultetu elektrotehnike i racˇunalstva) bude uvrsˇten u ovu knjizˇ icu, nastalu na temelju moje knjige Diskretna matematika u izdanju poduzec´a Element.

Zagreb, listopada 2006.

Ne samo moc´no oruzˇ je u borbi za opstanak, matematika je simbol nasˇe intelektualne snage i jamstvo, da c´e se ljudski duh vazda boriti za uzvisˇene ciljeve. — Danilo BLANUSˇ A (1903.–1987.)

SADRZˇ AJ 1. Skupovi . . . . . . . . . . . . . . . . . . . 1.1. Algebra skupova . . . . . . . . . . . . 1.2. Kartezijev produkt skupova . . . . . . 1.3. Ekvipotentni skupovi, kardinalni broj . 1.4. Prebrojivi skupovi i njihovo kodiranje 1.5. Neprebrojivost skupa realnih brojeva .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

1 1 6 7 10 11

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

16 16 17 19 22

3. Uvod u kombinatoriku . . . . . . . . . . . . . . . . . . . 3.1. Pravilo produkta . . . . . . . . . . . . . . . . . . . . 3.2. Varijacije, permutacije i kombinacije bez ponavljanja 3.3. Permutacije, varijacije i kombinacije s ponavljanjem . 3.4. Formula ukljucˇivanja – iskljucˇivanja . . . . . . . . . 3.5. Funkcije izvodnice . . . . . . . . . . . . . . . . . . . 3.6. Dirichletovo nacˇelo . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

25 25 31 36 44 50 57

4. Rekurzivne relacije ili diferencijske jednadzˇ be . . . . 4.1. Fibonaccijev slijed . . . . . . . . . . . . . . . . . 4.2. Asimptotsko ponasˇanje sljedova; oznake O, Ω , Θ 4.3. Linearne rekurzivne relacije . . . . . . . . . . . . 4.4. Nehomogene rekurzivne relacije . . . . . . . . . 4.5. Primjeri rjesˇavanja Eulerovom metodom . . . . . 4.6. Rjesˇavanje s pomoc´u funkcija izvodnica . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

66 66 70 76 81 84 87

. . . . . .

. . . . . .

2. Binarne relacije . . . . . . . . . . . . . . . . . 2.1. Refleksivne, simetricˇne, tranzitivne relacije 2.2. Relacija ekvivalencije . . . . . . . . . . . 2.3. Razredi ekvivalencije, particija skupa . . . 2.4. Josˇ neki primjeri . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

92

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

93

Literatura Kazalo

. . . . . . .

1.

Skupovi

1.1. Algebra skupova

Temeljne definicije i oznake. Pod pojmom skupa razumijevamo bilo koju mnozˇ inu elemenata. Npr.: (a) skup svih prirodnih brojeva N = f1 2 3 : : :g ; (b) skup svih cijelih brojeva Z = f: : : ;2 ;1 0 1 2 : : :g ; a (c) racionalnih brojeva Q (elementi su mu razlomci b , gdje su a b 2 Z i b 6= 0 ); p (d) skup svih realnih brojeva R ; on sadrz ˇi p sve racionalne, kao i brojeve poput 2 , π = 3:14 : : : , e = 2:71828 : : : , φ = 1+2 5 = 1:618 : : : , koji nisu racionalni; (e) skup kompleksnih brojeva C , koji sadrz ˇ i sve z = x + iy , takve da su x y 2 R , pri cˇ emu je i imaginarna jedinica za koju se definira da je i2 = ;1 . Te vrlo vazˇ ne skupove upoznali smo u osnovnoj i srednjoj sˇkoli. Povijesno, za njihovo uvodenje trebala su duga stoljec´a mukotrpnog i vrlo slozˇ enog znanstvenog razvoja, osobito za nulu, negativne cijele brojeve i kompleksne brojeve. Skup realnih brojeva strogo je definiran tek u 19. stoljec´u. Neka je X bilo koji unaprijed ucˇ vrsˇc´en skup koji zˇ elimo promatrati, tzv. univerzalni skup. U njemu gledamo podskupove A , B , C itd. (skupove i podskupove obicˇ no oznacˇ avamo velikim slovima). Cˇ injenicu da element x pripada skupu A biljezˇ imo sa x 2 A (ponekad i sa A 3 x , tj. skup A sadrzˇ i element x ). Ako x nije u A , onda pisˇemo x 2 = A . Skupove obic ˇ no zadajemo na dva nacˇ ina: a) popisivanjem njegovih elemenata, ako je to moguc´e: npr. A = f1 2 3g , ili b) opisno, s pomoc´u nekog svojstva. Tocˇ nije, skup A svih elemenata x 2 X koji imaju neku vlastitost P(x ) oznacˇ avamo sa A = fx 2 X : P(x )g . Npr. ako je X = R i vlastitost P(x ) oznacˇ ava da je x = tg x , onda je A = fx 2 R : x = tg x g skup svih realnih rjesˇenja jednadzˇ be x = tg x . Skup racionalnih brojeva mozˇ emo opisati kao Q = f ab : a b 2 Z b 6= 0g .

2

1. SKUPOVI

Skup ne ovisi o poretku elemenata u njegovu zapisu, kao niti o tome ima li ponavljanja nekog elementa: npr. f1 2 3g = f3 2 1g = f2 2 3 3 3 1g . Sljedec´a definicija je jasna: kazˇ emo da je skup A podskup skupa B ako je A sadrzˇ an u B , tj. ako za svaki element x 2 X vrijedi da ako je x 2 A , onda je x 2 B . Pisˇemo A  B . Znak  zovemo znakom inkluzije (ukljucˇ ivanja). Ako je A  B , onda kazˇ emo da je B nadskup od A , sˇto mozˇ emo pisati i kao B  A . Ocˇ evidno je A  A za bilo koji skup A . Ako je A  B i A 6= B , onda kazˇ emo da je A pravi podskup od B . Vazˇ an podskup od X je onaj koji ne sadrzˇ i niti jedan element, tzv. prazan skup. Oznacˇ avamo ga sa  . Smatramo da za svaki skup A vrijedi   A , tj. prazan skup je sadrzˇ an u svakom skupu. Takoder smatramo da postoji samo jedan prazan skup. Primjedba 1. Moguc´i su i skupovi koji kao svoje elemente sadrzˇ e druge skupove. Npr. skup A = fag ima kao element skup fag , tj. fag 2 A . Skup A ne sadrzˇ i element a : a 2 = A . Isto tako skup  ne sadrz ˇ i niti jedan element, dok skup fg sadrzˇ i jedan element (element mu je prazan skup).



Radi potpunosti, cˇ itatelja c´emo vrlo sazˇ eto podsjetiti josˇ i na neke temeljne pojmove u vezi s funkcijama. Neka su zadana dva neprazna skupa A i B . Funkcijom f iz A u B , zovemo pravilo (postupak) kojim svakom elementu a iz polaznog skupa A pridruzˇ ujemo tocˇno jedan element iz skupa B , koji oznacˇ avamo sa f (a) , i zovemo slikom elementa a u skupu B . Funkciju oznacˇ avamo sa f : A ! B . Funkcija se cˇ esto zove josˇ i preslikavanje. Umjesto b = f (a) ponekad pisˇemo i a 7! b . Kao sˇto smo rekli, ne mozˇ e nekom a 2 A biti pridruzˇ eno visˇe b -ova iz B , nego samo jedan, koji zovemo f (a) . Ali, neki b 2 B mozˇ e funkcijom f biti pridruzˇ en dvama ili visˇe razlicˇ itih elemenata iz A . Za zadanu funkciju f : A ! B skup A zove se domena, a skup B kodomena funkcije. Ako je b = f (a) , onda a zovemo argumentom funkcije, a b vrijednosˇc´u od f za argument a . Skup poredanih dvojaca (a f (a)) zove se graf funkcije f . Kad kazˇ emo poredani dvojac, onda nam to znacˇ i da je a 2 A prvi element, i f (a) 2 B drugi element u dvojcu (a f (a)) . Za dvije funkcije f : A1 ! B1 i g : A2 ! B2 kazˇ emo da su jednake ako imaju iste domene, tj. A1 = A2 , iste kodomene, tj. B1 = B2 , i za sve a 2 A vrijedi f (a) = g(a) . Npr. dvije funkcije f : N ! N i g : Z ! N zadane na ‘isti’ nacˇ in: f (x ) = x 2 + 1 i g(x ) = x 2 + 1 , smatramo razlicˇ itim funkcijama jer su im domene razlicˇ ite. Slijed (ili niz) u skupu A je bilo koja funkcija f : N ! A . Vrijednosti te funkcije su f (n) = an 2 A , tj. redom a1 a2 a3 : : : , pa slijed cˇ esto oznacˇ avamo i na ovaj nacˇ in: (an ) . Slika funkcije f : A ! B definira se kao skup f (A) = f f (a) 2 B : a 2 Ag , tj. kao skup svih b 2 B koji su ‘pogodeni’ s nekim a 2 A uz pomoc´ funkcije. Za funkciju f : A ! B kazˇ emo da je surjekcija ako je njena slika jednaka cˇ itavoj kodomeni, tj. f (A) = B . Rijecˇ ima: f je surjekcija ako za svaki b 2 B postoji a 2 A takav da je b = f (a) . Svaki element kodomene B je ‘pogoden’ s bar jednim elementom domene A . Za funkciju f : A ! B kazˇ emo da je injekcija ako razlicˇ itim vrijednostima argumenta pridruzˇ uje razlicˇ ite vrijednosti u slici, tj. ako je a1 6= a2 , onda je f (a1 ) 6= f (a2 ) .

1.1. ALGEBRA SKUPOVA

3

To je isto sˇto i zahtijevati da ako je f (a1 ) = f (a2 ) , onda je a1 = a2 . Injektivna funkcija ‘ne lijepi’ razlicˇ ite elemente iz skupa A u isti element iz B . Primijetite da za svaku funkciju f : A ! B vrijedi da iz a1 = a2 slijedi f (a1 ) = f (a2 ) . Funkcija f : A ! B koja je istodobno injekcija i surjekcija zove se bijekcija. U tom slucˇ aju mozˇ emo definirati inverznu funkciju f ;1 : B ! A na sljedec´i nacˇ in: f ;1 (b) = a onda i samo onda ako vrijedi f (a) = b . Inverzna funkcija je takoder bijekcija. Jasno je da izmedu dva skupa A i B s konacˇ no mnogo elemenata postoji bijekcija f : A ! B onda i samo onda ako skupovi A i B imaju isti broj elemenata. Bijekcija f : A ! A , tj. iz skupa A u samog sebe, cˇ esto se zove permutacija (premjestba) skupa A . Jedna vrlo vaz ˇ na permutacija skupa A je identitet id : A ! A , koja sve elemente u A ostavlja nepromijenjenim: id(a) = a . Za dvije funkcije f : A ! B i g : B ! C (primijetite da su ‘ulancˇ ane’ preko skupa B ), definirana je nova funkcija g  f : A ! C , zadana sa (g  f )(a) = g( f (a)) . Zove se kompozicija (skladanje) funkcija f i g . Za kompoziciju triju (ulancˇ anih) funkcija vrijedi zakon asocijativnosti: ako je h : C ! D , onda imamo h  (g  f ) = (h  g)  f . Pretpostavimo li da je f : A ! B bijekcija, ocˇ evidno vrijedi f ;1  f = idA (identitet na skupu A ) i f  f ;1 = idB (identitet na skupu B ). Ako je zadana josˇ jedna bijekcija, g : B ! C , onda je g  f : A ! C takoder bijekcija. Vrijedi sljedec´e vazˇ no pravilo za nalazˇ enje inverza kompozicije dviju bijekcija: (g

 f );1 = f ;1  g;1

:

U ovoj knjizi cˇ esto c´e nam se pojavljivati pojam n faktorijela, n! , koji se za n = 0 definira kao 0! = 1 , a za bilo koji prirodni broj n kao umnozˇ ak n uzastopnih prirodnih brojeva od 1 do n : n! = n(n ; 1) : : : 2 1: Npr. 1! = 1 , 2! = 2 , 3! = 6 , 4! = 24 , 5! = 120 itd. Vrijedi (n + 1)! = (n + 1) n! . Isto tako vazˇ an c´e nam biti pojam binomnog koeficijenta nk , koji se definira za nenegativne cijele brojeve n i k uz uvjet k ? n sa: n0 = 1 , a za 1 ? k ? n stavljamo n n(n ; 1) : : : (n ; k + 1) = : k k! Primijetite da u brojniku imamo padajuc´i umnozˇ ak tocˇ no k prirodnih brojeva, pocˇ evsˇi n od n . Lako se provjeri da je nk = k!(nn!;k)! , i vrijedi svojstvo simetrije: nk = n; k .

;



;

;

Npr.

; ; 

;7 = ;7 = 765 = 35 . 4

3



321

Uobicˇ ajene kratke oznake za zbroj i produkt n realnih brojeva a1 a2 n X i=1

ai

=

a1 + a2 + : : : + an

Yn i=1

ai

=

:::

an su

a1 a2 : : : an :

Teorem o dijeljenju cijelog broja a s prirodnim brojem b kazˇ e da postoje jednoznacˇ no odredni q 2 Z (djelomicˇ ni kvocijent) i ostatak r 2 f0 1 : : : b ; 1g tako da je a = qb + r:

4

1. SKUPOVI

r 0

b

2b

...

a

qb

(q+1)b

Sl. 1.1. Algoritam dijeljenja: a = qb + r .

Prost ili prim broj je bilo koji prirodan broj p > 2 koji je djeljiv samo s 1 i sa p , tj. jedini djelitelji su mu 1 i on sam. To su redom: p = 2 , 3 , 5 , 7 , 11 , 13 , 17 , 23 , 29 , itd. Prostih brojeva ima beskonacˇ no mnogo (Euklidov teorem). Podsjetimo se jos i Osnovnog teorema aritmetike. On kazˇ e da za svaki prirodan broj a > 2 postoje jednoznacˇ no odredeni prosti brojevi u rastuc´em slijedu, p1 < p2 < : : : < pk , takvi da je n n n a = p11 p22 : : : pk k gdje su ni prirodni brojevi koji su takoder jednoznacˇ no odredeni ( ni se zove kratnost prostog broja pi u tom rastavu). Na pr. 12 = 4 3 = 22 31 , 9 = 32 , 11 = 111 . Algebra skupova. Kazˇ emo da su skupovi A i B jednaki ako vrijedi A  B i B  A . U tom slucˇ aju pisˇemo A = B . Unijom skupova A i B sadrzˇ anih u univerzalnom skupu X zovemo skup C svih elemenata x takvih da je x 2 A ili x 2 B (moguc´e je da je x i u oba skupa). Pisˇemo C = A B . Presjek skupova A i B je skup D svih elemenata x takvih da je x 2 A i x 2 B . Oznacˇ avamo ga sa D = A \ B (skup zajednicˇ kih elemenata u A i B ). Ovdje smo namjerno istaknuli da je skupovna operacija povezana sa veznikom ili, a operacija \ sa veznikom i. Za dva skupa A i B kazˇ emo da su disjunktni ako im je presjek prazan, tj. A\B =  . Za vec´i broj (‘familiju’) skupova kazˇ emo da cˇ ine disjunktnu familiju skupova, ako se niti koja dva skupa iz familije ne sijeku. Npr. tri skupa A , B i C cˇ ine disjunktnu familiju ako su A \ B , A \ C i B \ C prazni skupovi. Razlika skupova A i B je skup E svih elemenata x za koje je x 2 A i x 2 = B. Oznaka je E = A n B . Ako je A podskup univerzalnog skupa X , onda definiramo komplement A skupa A sa A = X n A . Vazˇ no je primijetiti da komplement ovisi i o izboru univerzalnog skupa, tj. ispravnije bi bilo rec´i ‘komplement skupa A u skupu X ’. Ocˇ evidno je komplement od A jednak A , doticˇ no A = A . Isto tako je jasno da vrijedi A n B = A \ B . Komplement skupa A cˇ esto se oznacˇ ava i sa Ac ili A . X A

_ A

Sl. 1.2. Komplement skupa A .

Definicija. Za bilo koji skup X mozˇ emo definirati skup koji kao svoje elemente sadrzˇ i sve podskupove od X . Skup svih podskupova od X zovemo partitivni skup

1.1. ALGEBRA SKUPOVA

5

od X . Oznacˇ ava se cˇ esto sa P (X ) , ali mi c´emo radije rabiti oznaku 2X . Razlog je sljedec´i: ako skup X ima n elemenata, onda partitivni skup 2X ima tocˇ no 2n elemenata (vidi Teorem 3.1.5). Npr. za skup X = f1 2 3g je 2X skup od sljedec´ih 23 = 8 elemenata:  , f1g , f2g , f3g , f1 2g , f2 3g , f1 3g , f1 2 3g . Kao sˇto vidimo, elementi partitivnog skupa su podskupovi od X . Npr.  2 2X , X 2 2X . Na partitivnom skupu definirane su tri osnovne operacije: (i) dvije operacije (unija) i \ (presjek) koje dvama elementima A B 2 P (X ) pridruzˇ uju trec´i element iz P (X ) . To su tzv. binarne operacije na X (opc´a definicija binarne operacije bit c´e dana u Poglavlju 2). (ii) operacija komplementiranja A 7! A , koja je unarna operacija, tj. operacija sa samo jednom varijablom A 2 P (X ) . A A

X

B B

A A

X

B B

Sl. 1.3. Unija i presjek skupova.

Nije tesˇko dokazati da na partitivnom skupu P (X ) vrijede neka jednostavna pravila s obzirom na tri navedene operacije: , \ i komplementiranje u X .

2 2X . Vrijede ova pravila algebre skupova: idempotentnost operacija unije i presjeka: A A = A , A \ A = A ; asocijativnost: (A B) C = A (B C) , (A \ B) \ C = A \ (B \ C) ; komutativnost: A B = B A , A \ B = B \ A ; distributivnost: A \ (B C) = (A \ B) (A \ C) , A (B \ C) = (A B) \ (A C) ; DeMorganove formule: A B = A \ B , A \ B = A B ; A  = A, A \ X = A; A X = X , A \  = ; komplementiranost: A A = X , A \ A =  ;

Teorem 1. Neka su A B C

(1) (2) (3) (4) (5) (6) (7) (8) (9) involutivnost komplementiranja: A = A .

Primjedba 2. Iz teorema je vidljivo da sva navedena pravila algebre skupova imaju svojstvo dualnosti: ako u jednom pravilu zamijenimo svuda sa \ i obratno, i isto tako  sa X i obratno, dobivamo takoder valjano pravilo algebre skupova. Na taj nacˇ in se iz jednog zakona distribucije dobiva drugi – njemu dualan, iz jedne DeMorganove formule druga (i obratno). Primjedba 3. Zbog svojstva asocijativnosti opravdano je umjesto A (B C) pisati krac´e A B C , i taj izraz racˇ unati na bilo koji od dva nacˇ ina navedena u (2). Isto vrijedi i za A \ B \ C . Primjedba 4. Ako imamo vec´i broj skupova A1 : : : An , onda umjesto A1 : : : An pis ˇemo krac´e nk=1 Ak . Slicˇ no i za presjek \ . Ako imamo beskonacˇ an slijed

6

1. SKUPOVI

skupova (An ) , n = 1 2 : : : , onda njihovu uniju oznacˇ avamo sa k1=1 Ak i slicˇ no za presjek. Primjedba 5. U gornjem teoremu je dobro primijetiti da je  najmanji, a X najvec´i element u sljedec´em smislu: za svaki podskup A u X vrijedi   A  X . (niz)

Primjer 1. Dokazˇ imo za ilustraciju samo DeMorganovu formulu A \ B = A B u prethodnom teoremu. U tu svrhu dokazˇ imo najprije da je skup na lijevoj strani jed= A \ B . Onda nakosti podskup skupa na desnoj strani. Neka je x 2 A \ B , tj. x 2 je x 2 = A ili x 2 = B (jer x nije u oba skupa istodobno, vidi Sliku 1.3 desno). Dakle x 2 A ili x 2 B , tj. x 2 A B . Time smo dokazali da je A \ B  A B . Obratna inkluzija dokazuje se na slicˇ an nacˇ in.

1.2. Kartezijev produkt skupova U matematici je pojam Kartezijeva produkta skupova od iznimne vazˇ nosti, jer se susrec´e posvuda.

Definicija. Ako su A1 ,: : : , An neprazni skupovi, onda definiramo Kartezijev

produkt

A1  A2  : : :  An

kao skup svih poredanih n –teraca (a1 a2 : : : an ) takvih da je ak 2 Ak za sve k = 1 : : : n . Taj se skup oznacˇ ava krac´e sa nk=1 Ak . Kartezijev umnozˇ ak dvaju skupova dobro je gledati kao ‘pravokutnik’ razapet sa A1 horizontalno i A2 vertikalno, cˇ iji su elementi tocˇ ke oblika (a1 a2 ) . Pri tom su a1 i a2 koordinatne vrijednosti. Vidi Sliku 3.1. Za tri skupa dobivamo ‘kvadar’ itd. Korisno je znati da se Kartezijev umnozˇ ak skupova mozˇ e opisati i na drugi, ravnopravan nacˇ in. Ako je (a1 : : : an ) 2 nk=1 Ak , onda taj n -terac mozˇ emo promatrati kao funkciju f : f1 : : : ng ! nk=1 Ak takvu da je f (k) = ak i

Q

Q

f (k) 2 Ak () n Obratno, svaka funkcija f : f1 : : : ng ! k=1 Ak sa tim svojstvom () odreduje pripadni n -terac (a1 : : : an ) iz Kartezijeva produkta, gdje je ak = f (k) . Drugim rijecˇ ima, Kartezijev produkt skupova mozˇ e se definirati i kao skup svih funkcija f : f1 : : : ng ! nk=1 Ak sa svojstvom () .

Primjer 1. Za skupove A1 = f1 2 3g i A2 = fa bg je

A1  A2 = f(1 a) (2 a) (3 a) (1 b) (2 b) (3 b)g: Vidimo da za bilo koje konacˇ ne skupove A i B vrijedi da je broj elemenata u Kartezijevom produktu A  B jednak umnosˇku broja elemenata u A i B . Drugim rijecˇ ima, vrijedi produktno pravilo: jA  Bj = jAj jBj , gdje smo s j j oznacˇ ili broj elemenata skupa (tzv. kardinalni broj skupa).

Povijesna crtica 1ee2 Pojam funkcije uveo je 1694. g. Gottfried Wilhelm Leibniz (1646.–1716.), a u modernom smislu Leonhard Euler (1707.–1783.), od kojeg potjecˇ e i oznaka f (x ) . Oznake  i  za relaciju podskupa i nadskupa medu skupovima, kao i princip dualnosti u matematicˇ ku logiku, uveo je njemacˇ ki matematicˇ ar Ernst Schr¨oder (1841.–1911.). Oznaku 2 za element skupa, zatim binarne 1ee2

1.3. EKVIPOTENTNI SKUPOVI, KARDINALNI BROJ

7

operacije i \ za uniju i presjek skupova uveo je Talijan Giuseppe Peano (1858.– 1932.). Cˇ esto je korisno skupove oznacˇ avati s pomoc´u Vennovih dijagrama, nazvanih prema engleskom matematicˇ aru Johnu Vennu (1834.–1923.), vidi npr. Sliku 1.3.

1.3. Ekvipotentni skupovi, kardinalni broj U ovom i daljnjim odjeljcima bit c´e nam vrlo vazˇ ni pojmovi kao sˇto su injektivna, surjektivna i bijektivna funkcija, te pojam slijeda.

Definicija. Za neprazan skup A kazˇ emo da je konacˇan ako postoji prirodan broj n i bijekcija f : f1 2 : : : ng ! A . Broj n zovemo kardinalni broj skupa A i oznacˇ avamo ga sa jAj . Kazˇ emo josˇ da A ima n elemenata. U tom slucˇ aju skup A je moguc´e zapisati kao A = fa1 a2 : : : an g , gdje je ak := f (k) , k = 1 : : : n . I prazan skup  smatramo konacˇ nim skupom s kardinalnim brojem 0 . Za skup A kazˇ emo da je beskonacˇ an ako nije konacˇ an. Postoje dvije osnovne vrste beskonacˇ nih skupova: (i) za beskonacˇ an skup A kaz ˇ emo da je prebrojiv ako se skup njegovih elemenata mozˇ e poredati u beskonacˇan slijed: A = fa1 a2 a3 : : :g . (ii) za beskonacˇ an skup A kaz ˇ emo da je neprebrojiv ako se ne mozˇ e poredati u slijed. Jasno je da je N prebrojiv skup. Vidjet c´emo kasnije da je cˇ ak i skup racionalnih brojeva Q prebrojiv, kao i to da je skup R neprebrojiv. Ponekad je korisno znati ovo jednostavno svojstvo: ako je skup A konacˇan i ako je f : A ! A injektivna funkcija, onda je f i surjekcija (dakle bijekcija). To slijedi odmah iz ove propozicije. Propozicija 1. Neka su A i B konacˇ ni skupovi koji imaju isti broj elemenata, tj. jAj = jBj . Funkcija f : A ! B je injektivna onda i samo onda ako je surjektivna.

DOKAZ . Neka je f injektivna funkcija. Onda skupovi A i f (A) imaju isti broj elemenata, doticˇ no jAj = j f (A)j . Zbog jAj = jBj je onda j f (A)j = jBj . Odavde zajedno sa f (A)  B , i jer je B konacˇ an skup, slijedi f (A) = B , dakle f je surjekcija. Obratno, neka je f surjekcija. Onda je jAj > j f (A)j = jBj , pa zbog jAj = jBj imamo jAj = j f (A)j . Buduc´i da je A konacˇ an skup, to znacˇ i da je f injekcija. Mozˇ e se pokazati da beskonacˇ ni skupovi nemaju ovo svojstvo. Sˇ tovisˇe, skup A je beskonacˇ an onda i samo onda ako postoji bijekcija na neki njegov pravi podskup, vidi Primjer 1 nizˇ e. Kao sˇto smo rekli, za beskonacˇ an skup A kazˇ emo da je prebrojiv ako se njegovi cˇ lanovi mogu poredati u slijed: A = fa1 a2 : : :g . Ekvivalentno tome, skup A je prebrojiv ako postoji bijekcija f : N ! A .

f

g

Doista, ako je A = a1 a2 : : : ak : : : prebrojiv skup, onda mozˇ emo definirati bijekciju A sa f (k) = ak . Obratno, ako je f : N A bijekcija, onda skup A mozˇ emo poredati u f :N slijed (niz) stavljajuc´i ak := f (k) . Funkcija f zove se funkcija prebrojavanja skupa A .

!

!

Primjer 1. Skup svih parnih brojeva 2N = f2 4 6 : : :g je prebrojiv, jer je f : N ! 2N , f (k) = 2k , bijekcija (provjerite). Opc´enitije, svaki beskonacˇ an podskup skupa prirodnih brojeva je prebrojiv, jer se ocˇ evidno mozˇ e poredati u slijed brojeva po velicˇ ini, vidi Teorem 3 nizˇ e.

8

1. SKUPOVI

A sˇto bi bio kardinalni broj skupa koji je beskonacˇ an? Da bismo dosˇli do tog pojma, primijetimo da skup A ima n elemenata onda i samo onda ako postoji bijekcija s A na skup f1 2 : : : ng . Definirajmo zato najprije pojam ekvipotentnosti medu skupovima.

Definicija. Kazˇ emo da je skup A ekvipotentan (jednakobrojan) sa skupom B ako postoji bijekcija f : A ! B . Ekvipotentnost je zapravo jedna relacija medu skupovima, o kojima c´e visˇe rijecˇ i biti u Poglavlju 2. Teorem 2. Oznacˇ imo svojstvo da je skup A ekvipotentan sa skupom B oznakom A  B . Ekvipotentnost ima ova temeljna svojstva: (i) refleksivnost: A  A za svaki skup A ; (ii) simetricˇ nost: ako je A  B , onda je i B  A ; (iii) tranzitivnost: ako je A  B i B  C , onda je A  C .

DOKAZ . (i) Identitet id : A ! A , id(x ) = x , je bijekcija; (ii) ako je f : A ! B bijekcija, onda je i inverzna funkcija f ;1 : B ! A takoder bijekcija; (iii) Ako su funkcije f : A ! B i g : B ! C bijekcije, onda je i njihova kompozicija g  f : A ! C takoder bijekcija. Jasno je da za konacˇ ne skupove A i B njihova ekvipotentnost znacˇ i upravo to da imaju isti broj elemenata. Broj elemenata konacˇ nog skupa zovemo kardinalni broj skupa. Razumno je na slicˇ an nacˇ in definirati i kardinalni broj za beskonacˇ ne skupove.

Definicija. Za skupove A i B kazˇ emo da imaju isti kardinalni broj ako su ekvipotentni, doticˇ no ako postoji bijekcija s jednog na drugi. Pisˇemo jAj = jBj . Ako je zadan konacˇ an skup A = fa1 : : : an g , onda je njegov kardinalni broj jednak n : jAj = n .

Definicija. Ako je skup A prebrojiv, onda njegov kardinalni broj oznacˇavamo sa @0 i zovemo “alef nula” (prema prvom slovu @ “alef” hebrejskoga pisma), i pisˇemo jAj = @0 . Kardinalni broj skupa R realnih brojeva oznacˇ avamo sa c i zovemo kontinuum. Pisˇemo jRj = c . Kardinalne brojeve bilo koja dva skupa A i B mozˇ emo usporedivati ovako. Kazˇ emo da je jAj ? jBj (i cˇ itamo: kardinalni broj skupa A je manji ili jednak od kardinalnog broja skupa B ) ako postoji injektivna funkcija f : A ! B . To je isto sˇto i rec´i da je skup A ekvipotentan s nekim podskupom od B (i to upravo sa f (A) ). Ukoliko je jAj ? jBj i skupovi A i B nisu ekvipotentni, onda pisˇemo jAj < jBj . Ako su skupovi A i B konacˇ ni, onda jAj ? jBj izrazˇ ava uobicˇ ajen odnos ? (manje ili jednako) izmedu broja elementa skupa A i broja elemenata skupa B .

j j?j j

Mozˇ e se pokazati da ako je A B (tj. skup A je ekvipotentan nekom podskupu od B ) i (tj. skup B je ekvipotentan nekom podskupu A ), onda postoji i bijekcija izmedu skupova A i B , tj. A = B . Za beskonacˇne skupove ova tvrdnja zove se Schr¨oder–Bernsteinov teorem, i njen dokaz nije jednostavan, vidi Papic´, str. 55]. Naravno, za konacˇne skupove A i B ova je tvrdnja ocˇevidna.

jBj ? jAj

jj jj

Jasno je da vrijedi N  R , pa je dakle @0 ? c . Kasnije c´emo pokazati da ne postoji bijekcija sa skupa N na R , odakle c´e slijediti da su ova dva beskonacˇ na kardinalna broja medusobno razlicˇ ita, tj. @0 < c (vidi Teorem 1.5.1).

Primjer 2. Buduc´i da postoji bijekcija sa N = f1 2 3 : : :g na 2N (skup svih parnih brojeva), onda je jNj = j2Nj = @0 . Dakle imamo skup koji je ekvipotentan

1.3. EKVIPOTENTNI SKUPOVI, KARDINALNI BROJ

9

svom pravom podskupu! Kod konacˇ nih skupova se tako sˇto ne mozˇ e dogoditi. Takvu vlastitost imaju svi beskonacˇ ni skupovi, i samo oni. Evo josˇ tri slicˇ na primjera: (i) Skupovi (;1 1) i R su ekvipotentni. Dovoljno je vidjeti da je funkcija f : R ! (;1 1) zadana sa f (x ) = th x bijekcija. (ii) Bilo koja dva otvorena intervala u R oblika (a b) i (c d) su ekvipotentna. Nai;c (x ; a) + c je bijekcija me, funkcija f : (a b) ! (c d) definirana sa f (x ) = bd; a (pravac kroz tocˇ ke A(a c) i B(b d) u ravnini). (iii) Skupovi N i njegov pravi podskup f5 6 7 : : :g su ekvipotentni, jer je funkcija pomaka f (k) = k + 4 bijekcija medu njima. U dokazu sljedec´eg teorema rabit c´emo ocˇ evidnu cˇ injenicu da svaki podskup skupa prirodnih brojeva ima minimalni element. Teorem 3. Svaki beskonacˇ an podskup prebrojiva skupa je prebrojiv.

DOKAZ . Umjesto skupa A = fa1 a2 : : :g dovoljno je tvrdnju dokazati za N = f1 2 : : :g . Neka je dakle A = N i B beskonacˇan podskup od N . Odaberimo najmanji prirodni broj b1 u B . Zatim iz B izbacimo b1 i gledamo najmanji element b2 u preostalom skupu B n fb1 g . Neka je zatim b3 najmanji prirodni broj u B n fb1 b2 g , itd. Nije tesˇko provjeriti da je funkcija f : N ! B definirana sa f (k) = bk bijekcija, pa je B prebrojiv skup.

Primjedba 1. Iz prethodnog teorema vidimo da c´e neki skup A biti prebrojiv onda i samo onda ako postoji injektivno preslikavanje f : A ! N cˇ ija je slika f (A) beskonacˇ an podskup od N . Naime ako f gledamo kao funkciju f : A ! f (A) , onda je f bijekcija i skup f (A) je prebrojiv. Sljedec´e svojstvo imaju samo beskonacˇ ni skupovi. Teorem 4. Neka je A beskonacˇ an skup i K njegov konacˇ an podskup. Onda su skupovi A i A n K ekvipotentni, tj. jAj = jA n K j .

DOKAZ . Neka je K = fa1 : : : ak g . Buduc´i da je A beskonacˇ an skup, onda postoji prebrojiv podskup S , koji sadrzˇ i K , tj. S = fa1 : : : ak ak+1 : : :g . Funkcija f : A ! A n K definirana kao identitet na A n S i kao pomak za k na slijedu S : f (x )

=

x

ai+k

za x za x

2 A n S, = ai 2 S ,

je ocˇ evidno bijekcija. (0

Primjer 3. Na temelju ovog stavka imamo zanimljiv zakljucˇak: skupovi 0 1] , 1] , (0 1) su ekvipotentni.

Primjedba 2. Spomenimo da se kardinalni broj skupa A u literaturi cˇesto oznacˇ ava i sa card A ili ]A umjesto jAj .

10

1. SKUPOVI

1.4. Prebrojivi skupovi i njihovo kodiranje Rabec´i Primjedbu 1.3.1 mozˇ emo lako dokazati da je npr. skup Nk svih poredanih k –teraca prirodnih brojeva prebrojiv. Sˇ tovisˇe, vrijedi

=

N:::N

N N2 N3 : : : je prebrojiv. Drugim rijecˇ ima, skup svih konacˇ nih sljedova prirodnih brojeva je prebrojiv. Teorem 1. Skup A

=

DOKAZ . Odaberimo slijed prostih brojeva p1 = 2 , p2 = 3 , p3 = 5 , p4 = 7 , p5 itd. Skup prostih brojeva je beskonacˇ an. Definirajmo funkciju f : A ! N sa f (n1

:::

n

=

11

n

nk ) = p11 : : : pk k :

Dokazˇ imo da je ova funkcija injekcija. Neka je f (n1 : : : nk ) = f (m1 : : : mj ) , tj. m n n m p11 : : : pk k = p1 1 : : : pj j . Buduc´i da imamo jednakost brojeva koji su rastavljeni na proste faktore, prema Osnovnom teoremu aritmetike slijedi da je k = j i ni = mi za sve i = 1 : : : k . Time je injektivnost od f dokazana. Slika preslikavanja f je ocˇ evidno beskonacˇ an skup (vec´ za “jednocˇ lane” sljedove n je skup pripadnih vrijednosti oblika f (n) = 2n , dakle beskonacˇ an skup). Tvrdnja slijedi iz Primjedbe 1.3.1.

Definicija. Funkcija f : A ! N iz dokaza prethodnog teorema zove se kodiranje skupa A . Npr. trojcu (6 14 9) bit c´e pridruzˇ en kˆod 26 314 59 . Primjedba 1. Skup svih konacˇnih sljedova cijelih brojeva je prebrojiv. Buduc´i da je skup svih konacˇ nih sljedova sastavljenih samo od 0 i 1 njegov beskonacˇ an podskup, onda je i on prebrojiv. Cˇ ine ga sljedovi nula i jedinica oblika: 0 , 101 , 1101001 itd. Pokazuje se da je skup svih beskonacˇnih sljedova nula i jedinica neprebrojiv, doticˇ no ima kardinalni broj c (dakle ekvipotentan je sa R ; vidi sljedec´i odjeljak). Teorem 2. Skupovi cijelih brojeva Z i racionalnih brojeva Q su prebrojivi.

DOKAZ . (i) Najprije c´emo skup svih pozitivnih cijelih brojeva preslikati bijektivno u skup svih parnih prirodnih brojeva, a zatim negativne cijele brojeve i nulu bijektivno u neparne prirodne brojeve. To radi funkcija f : Z ! N koja pozitivnim cijelim brojevima pridruzˇ uje parne prirodne brojeve, a nuli i negativnim cijelim brojevima pridruzˇ uje neparne prirodne brojeve: 2k za k > 0 f (k) = 2jkj + 1 za k ? 0 Ona je ocˇ evidno bijekcija. (ii) Dovoljno je pronac´i injektivnu funkciju f : Q ! N , vidi Teorem 1.3.3. Mozˇ emo ju lako konstruirati kodiranjem. Svaki racionalan broj x je odreden s tri podatka: predznakom p ( +1 ili ;1 ), brojnikom m 2 N0 i nazivnikom n 2 N . Pretpostavit c´emo da su brojnik i nazivnik skrac´eni do kraja (tj. bez zajednicˇ kog djelitelja > 1 ). Funkcija f : Q ! N definirana sa f ( p mn ) = 2 p+1 3m 5n je injektivna, sˇto se dobiva m m odmah iz Osnovnog teorema aritmetike. Naime ako je f ( p1 n 1 ) = f ( p2 n 2 ) , onda je



2 p1 +1 3m1 5n1 = 2 p2 +1 3m2 5n2 , dakle p1 + 1 m m p1 n 1 = p2 n 2 . 1

2

=

p2 + 1 , m1

1

=

m2 , n1

2

=

n2 , doticˇ no

1.5. NEPREBROJIVOST SKUPA REALNIH BROJEVA

11

Primjedba 2. Prebrojivost skupa Z cijelih brojeva mozˇ e se lako dokazati i kodiranjem. Pokusˇajte. I prebrojivost skupa Q racionalnih brojeva mozˇ e se dokazati izravno, tako da se poreda u slijed. Racionalne brojeve pisˇemo u obliku  mn i slazˇ emo ih u slijed ovako: (1) najprije pisˇemo nulu, zatim (2) poredamo sve pozitivne racionalne brojeve kojima je zbroj brojnika i nazivnika jednak 2 : 11 , (2’) poredamo sve negativne racionalne brojeve kojima je zbroj brojnika i nazivnika jednak ;2 : ; 11 , (3) pisˇemo sve pozitivne racionalne brojeve kojima je zbroj brojnika i nazivnika jednak 3 : 12 , 21 , (3’) poredamo sve negativne racionalne brojeve kojima je zbroj brojnika i nazivnika jednak 3 : ; 12 , ; 21 , itd. Dakle skup racionalnih brojeva Q mozˇ e se poredati u slijed ovako 0 , 1 , ;1 12 , 2 1 2 1 3 2 3 1 2 3 1 , ; 2 , ; 1 , 3 , 1 , 2 , 1 , ; 3 , ; 2 , ; 1 , itd. Pri tom se neki od racionalnih brojeva i ponavljaju. Time je dokazano da vrijedi jQj = @0 . Sljedec´a slika pokazuje kako se pozitivni racionalni brojevi mogu poredati u slijed: 1 1

1 2

1 3

1 4

2 1

2 2

2 3

2 4

3 1

3 2

3 3

3 4

4 1

4 2

4 3

4 4

Sl. 1.4.

1.5. Neprebrojivost skupa realnih brojeva Kao sˇto smo rekli, kardinalni broj skupa realnih brojeva R zovemo kontinuum

(kaz ˇ emo da realnih brojeva ima kontinuum), a kardinalni broj skupa prirodnih brojeva zovemo 0 (alef nula). Zbog N R je ocˇ evidno 0 c . Sljedec´i teorem pokazuje da je 0 = c . Skupovi realnih i racionalnih brojeva su oba beskonacˇ ni, ali ne podjed-

@ @ 6



@ ?

nako. Pokazˇ imo da je skup realnih brojeva ‘visˇe beskonacˇ an’ nego skup racionalnih.

Teorem 1. (Georg Cantor) Skup R je neprebrojiv, tj. nije ekvipotentan sa skupom N . Drugim rijecˇ ima vrijedi @0 < c , tj. skup realnih brojeva ne mozˇ e se poredati u slijed.

DOKAZ . (Cantorov dijagonalni postupak) Pretpostavimo suprotno, tj. da je skup R prebrojiv. Vec´ smo vidjeli da je R ekvipotentan s intervalom (0 1] , pa se onda i skup

12

1. SKUPOVI

1] mozˇ e poredati u slijed: (0 1] = fx 1 x 2 : : :g . Prikazˇ imo ove brojeve u decimalnom zapisu. Taj prikaz nije jednoznacˇ an, jer se npr. broj s konacˇ nim decimalnim prikazom 0:31 mozˇ e pisati i u obliku beskonacˇ nog decimalnog prikaza 0:30999 : : : . Za svaki broj iz (0 1] rabit c´emo, radi jednoznacˇ nosti, njegov beskonacˇ an decimalni prikaz. Onda vrijedi x 1 = 0:a11 a12 a13 : : : x 2 = 0:a21 a22 a23 : : : x 3 = 0:a31 a32 a33 : : : gdje su aij znamenke izmedu 0 i 9 . Pogledajmo sada slijed znamenaka a11 , a22 , a33 itd. na “dijagonali” u gornjem decimalnom prikazu. Odaberimo slijed znamenaka bn iz skupa f1 : : : 9g na ovaj nacˇ in: znamenka b1 neka je odabrana tako da bude razlicˇ ita od a11 , b2 razlicˇ ita od a22 itd. Onda je broj b := 0:b1 b2 b3 : : : razlicˇ it od x 1 (ne podudaraju se u prvoj decimali), isto tako b 6= x 2 (ne podudaraju se u drugoj decimali), itd. Stoga b 2 = fx 1 x 2 x 3 : : :g = (0 1] . To je kontradikcija, jer decimalni prikaz od b pokazuje da je b 2 (0 1] . (0

Primjedba 1. Gledajuc´i brojeve iz intervala 0 1] u binarnom zapisu, nije tesˇko vidjeti da je na isti nacˇ in i skup svih beskonacˇ nih sljedova sastavljenih samo od nula i jedinica (npr. 010110 : : : ) neprebrojiv. Primjedba 2. Vidjeli smo da ako je A  N , onda je A ili konacˇan ili prebrojiv skup. Postavlja se pitanje vrijedi li nesˇto slicˇ no i za skup A za koji je NAR tj. slijedi li odavde da je nuzˇ no jAj = @0 ili jAj = c ? Ta se hipoteza zove Cantorova hipoteza kontinuuma. Ili mozˇ da postoji skup A takav da je @0 < jAj < c , tj. postoji kardinalni broj koji je strogo izmedu @0 i c ? Neocˇ ekivan odgovor na to pitanje dao je Paul Cohen 1964. g. Navedeni problem je neodlucˇiv. To znacˇ i da se hipoteza kontinuuma ne mozˇ e niti dokazati niti opovrgnuti s pomoc´u preostalih aksioma teorije skupova. Drugim rijecˇ ima, moguc´a je jedna suvisla teorija skupova u kojoj c´e hipoteza kontinuuma vrijediti (tj. nema kardinalnog broja izmedu @0 i c ), a moguc´a je isto tako i druga suvisla teorija skupova u kojoj hipoteza kontinuuma nec´e vrijediti. Hipoteza kontinuuma ne mozˇ e se izvesti iz standardne aksiomatike teorije skupova, pa se ona sama mozˇ e postulirati kao nezavisan aksiom teorije skupova, ili pak se mozˇ e postulirati njena negacija. Problem je slicˇan kao kod znamenitog petog Euklidova aksioma (aksioma o paralelama - kroz zadanu tocˇku u ravnini prolazi tocˇno jedan pravac paralelan sa zadanim pravcem): mozˇ e li se peti Euklidov aksiom izvesti iz prva cˇetiri? Pokazuje se da ne mozˇ e. Pazˇ ljivo razmatranje tog pitanja dovelo je do otkric´a neeuklidskih geometrija (Lobacˇevski, i josˇ ranije Gauss).

Primjedba 3. Skup svih racionalnih brojeva Q je prebrojiv (Teorem 1.4.2), skup svih realnih je neprebrojiv (Teorem 1), dakle skup svih iracionalnih brojeva R n Q (tj. realnih brojeva koji nisu racionalni) je neprebrojiv, tocˇ nije, jR n Qj = c . Iracionalni brojevi su tocˇ no oni cˇ iji decimalni prikaz nije periodicˇ an. Mozˇ e se dokazati da je i jCj = c , doticˇ no skupovi C i R su ekvipotentni. Sˇ tovisˇe, za svaki prirodan broj n vrijedi jRn j = c , gdje je Rn skup svih poredanih n -teraca realnih brojeva. Josˇ jedan vazˇ an prebrojiv skup koji je sadrzˇ an u (neprebrojivom) skupu realnih brojeva cˇ ini skup algebarskih brojeva. Definicija. Za realan broj a kazˇ emo da je algebarski broj ako postoji polinom P(x ) s cjelobrojnim koeficijentima koji nisu svi 0 , takav da je P(a) = 0 .

1.5. NEPREBROJIVOST SKUPA REALNIH BROJEVA

13

Primjeri algebarskih brojeva su svi racionalni brojevi ba , gdje je a 2 N , b 2 Z p p (nultocˇ ka od ax ; b ), 2 (nultocˇ ka od x 2 ; 2 ), 3 2 (nultocˇ ka od x 3 ; 2) ,

q5

p

2 + 3=7 (lako mozˇ ete nac´i polinom s cjelobrojnim koeficijentima cˇ ija je ovo nultocˇ ka), itd. itd. Vrijedi ovakav iznenadujuc´ rezultat: Propozicija 2. Skup svih algebarskih brojeva je (samo) prebrojiv.

DOKAZ . Svakom polinomu s cjelobrojnim koeficijentima mozˇ emo pridruzˇ iti konacˇ an slijed njegovih cjelobrojnih koeficijenata. Buduc´i da je to pridruzˇ ivanje injektivno, i skup konacˇ nih sljedova cijelih brojeva prebrojiv (po Teoremu 1.4.1), onda je i skup svih polinoma s cjelobrojnim koeficijentima prebrojiv, tj. mozˇ emo ga poredati u slijed: P1 P2 P3 : : : Svakom od tih polinoma pripada konacˇ no mnogo kompleksnih nultocˇ aka (najvisˇe onoliko koliki je stupanj pripadnog polinoma; Gaussov osnovni teorem algebre). Prebrojivost skupa svih tih nultocˇ aka (algebarskih brojeva) mozˇ e se pokazati “nadovezivanjem”. Npr. ako je P1 polinom cˇ etvrtog stupnja s nul-tocˇ kama z11 , z12 , z13 , z14 , onda im pridruzˇ imo prirodne brojeve 1 2 3 4 , ako je P2 polinom desetog stupnja s nultocˇ kama z21 z22 : : : z2 10 , pridruzˇ ujemo im brojeve 5 6 : : : 14 , itd.

Definicija. Realni brojevi koji nisu algebarski zovu se transcendentni brojevi. Na temelju prethodne propozicije zakljucˇ ujemo da je skup transcendentnih brojeva (cˇ ak) neprebrojiv. To nije basˇ u skladu s cˇ injenicom da smo do sada upoznali samo p 3 dva od njih: π i e . Ima ih medutim josˇ, poput 2 , ln 2 , sin 1 (vidi povijesnu crticu na str. 222). Jedan neprebrojiv skup transcendentnih brojeva mozˇ e se konstruirati ovako: x = n1=1 10ann! , gdje je an 2 f0 1g i skup svih an koji su jednaki 1 je beskonacˇ an. Da je svaki od tih brojeva transcendentan, dokazao je francuski matematicˇ ar Joseph Liouville (1809–1882). Njihova neprebrojivost je jasna: svakom x mozˇ emo bijektivno pridruzˇ iti slijed (an ) nula i jedinica (taj skup sljedova je neprebrojiv).

P

Zadatci za vjezˇ bu 1. Ispitaj koja je od sljedec´ih funkcija f : N ! N injekcija, surjekcija, ili bijekcija: (a) f (k) = 2k + 3 (b) f (n) = (n ; 5)2 + 3 , (c) f (x ) = x 2 + 2x + 3 (d) f (a) = a3 ; 3r + 5 . 2. Zadan je skup A = f1 2 3g . (a) Uvjeri se da ima ukupno 27 funkcija f : A ! A . (b) Nadi sve surjektivne funkcije f : A ! A . (c) Nadi sve injektivne funkcije f : A ! A . (d) Nadi sve bijekcije f : A ! A . 3. Pokazˇ i da je skup A svih neparnih brojeva prebrojiv tako da konstruirasˇ bijekciju s N na A . 4. Konstruiraj formulom neku bijekciju sa skupa N na skup A svih onih prirodnih brojeva koji pri dijeljenju s 5 daju ostatak 3 . Nadi njoj inverznu funkciju. 5. Konstruiraj neku bijekciju sa skupa h : A ! B , gdje je A skup svih prirodnih brojeva koji pri dijeljenju s 5 daju ostatak 3 , a B skup svih prirodnih brojeva koji pri dijeljenju s 3 daju ostatak 2 . 6. Konstruiraj formulom neku injektivnu funkciju sa skupa Z  Z u skup N . 7. Konstruiraj (sˇto je moguc´e jednostavnijom formulom) neku surjektivnu funkciju iz skupa Z  Z na N . 8. Konstruiraj neku bijekciju sa skupa Z  Z u skup N .

14

1. SKUPOVI

9. (tezˇ i zadatak) Napisˇi racˇ unalni program koji c´e unosom cijelih brojeva x i y dati na izlazu redni broj n tocˇ ke Tn (x y ) u gore opisanom spiralnom prebrojavanju. 10. (tezˇ i zadatak) Konstruiraj bijekciju sa zatvorenog intervala 0 1] na poluotvoren interval (0 1] . Nacrtaj graf te funkcije. Naputci i rjesˇenja

)

)

1. (a) Za injektivnost treba provjeriti da f (k1 ) = f (k1 ) 2k1 + 3 = 2k2 + 3 k1 = k2 . Ispitaj intervale monotonosti ove funkcije gledajuc´i najprije a kao realan parametar. 2. (a) Sve funkcije dobijemo tako da elementima 1 2 3 pridruzˇ ujemo redom 1 1 1 (to je prva funkcija), zatim 1 1 2 (druga), 1 1 3 (trec´a), pa (d)

1 2 1

1 2 2

1 2 3

1 3 1

1 3 2

1 3 3

2 1 1

2 1 2

2 1 3

2 2 1

2 2 2

2 2 3

3 1 1

3 1 2

3 1 3

i na koncu 3 2 1 , 3 2 2 , 3 3 3 (dvadeset sedma funkcija). (b) Sve surjekcije iz konacˇnog skupa u samoga sebe su bijekcije, tj. kao u (d). (c) Svaka injekcija iz A u A , gdje je A konacˇan skup, je bijekcija. (d) Svih bijekcija iz A u A ima ukupno 6 : f1 , f2 ,: : : , f6 : A A . Na pr. f1 preslikava 1 2 3 redom u 1 2 3 (identitet), f2 preslikava 1 2 3 redom u 1 3 2 , f3 redom u 2 1 3 , f4 u 2 3 1 , f5 u 3 1 2 , a f6 u 3 2 1 . 3. Konstruiraj formulom neku bijekciju f : N 2N 1 , gdje je 2N 1 skup svih neparnih brojeva, 2N 1 = 1 3 5 : : : . Na pr. f (k) = 2k 1 . 4. Elementi skupa A = 3 8 13 18 : : : su oblika 5k + 3 , gdje je k N 0 , tj. A = 5 (N 1) + 3 . Dakle jedna prirodna bijekcija je oblika f (n) = 5(n 1) + 3 . 5. Neka je f : N A iz prethodnog zadatka, i na slicˇan nacˇin konstruiramo bijekciju g:N B , g(n) = 3(n 1) + 2 . Onda je h = g f ;1 = 3x5+1 . Mozˇ e i ovako: definiramo

!

!; ; ; ; f g f g  ; ; 2 f g ! ! ;  1 x 3 3 n;1 2 , tj. za x 5 n;1 3 5n ; 2 je n 2 . Dakle, h 5 n;1 5 3 3x + 1 3n ; 1 5 x 2 ; 1 . hx 5 x jx j , y sgn y jy j , gdje 6. Za x y 2 Z  Z mozˇ emo pisati x je sgn x 1 za x > 1 , a sgn x ;1 za x 0sgn . Prema tome mozˇ emo definirati na ( (

)+ ) =

( )=

=

(

)+

=

( + )

(

)

=

(

)+

=

=

( +

)

=

=

= (

)

= (

)


0 . Za 1 bn , ako dva reda iz X kazˇ emo da su ekvivalentna, i pisˇemo n1=1 an  n=1 an postoji l = limn!1 bn i l 6= 0 1 . Pokazuje se da vrijedi ovaj vazˇ an teorem o usporedivanju redova: ako su dva reda iz X ekvivalentna, onda ili oba konver1 1 . Buduc´i da drugi red giraju, ili oba divergiraju. Na pr. n1=1 n2n+1  n=1 n divergira (harmonijski red), onda divergira i prvi.

P

P

P

P

P

2.3. RAZREDI EKVIVALENCIJE , PARTICIJA SKUPA

19

Primjedba 1. Primijetimo da u relaciji ekvivalencije poredak elemenata nije vazˇ an: zbog simetricˇ nosti je svejedno pisˇemo li x ρ y ili y ρ x . U literaturi je vrlo cˇ esto obicˇ aj relaciju ekvivalencije oznacˇ avati i sa  umjesto sa ρ , tako da mozˇ emo pisati x  y .

2.3. Razredi ekvivalencije, particija skupa U ovom odjeljku c´emo pokazati sljedec´u vrlo jednostavnu, ali iznimno vazˇ nu cˇ injenicu: svakoj relaciji ekvivalencije pripada tocˇ no odreden rastav skupa X na disjunktne podskupove (particija skupa X ) i obratno. Ti disjunktni podskupovi zovu se razredi (klase) ekvivalencije.

Definicija. Neka je ρ relacija ekvivalencije na X . Razred (klasa) ekvivalencije x ] elementa x 2 X je skup svih elemenata iz X koji su u relaciji s x . Dakle x ] je podskup od X definiran sa x ] = fy 2 X : y ρ x g: Zbog x ρ x je uvijek x 2 x ] . Bilo koji element y iz x ] zove se reprezentant razreda x ] . Teorem 1. Neka je ρ relacija ekvivalencije na X . Onda za sve x y 2 X vrijedi ili x ] = y ] ili x ] \ y ] =  . Pritom je x ρ y onda i samo onda ako je x ] = y ] .

DOKAZ . Pretpostavimo da je x ] \ y ] 6=  . Trebamo dokazati da je x ] = y ] . Ako postoji z 2 X , z 2 x ] \ y ] , onda je x ρ z i z ρ y . Zbog tranzitivnosti dobivamo da je x ρ y , tj. x 2 y ] . Prema tome je opet zbog tranzitivnosti x ]  y ] . Na isti nacˇ in se pokazuje i y 2 x ] , tj. y ]  x ] . Dakle x ] = y ] . X [x]

[y]

x

y

Sl. 2.2. Particija skupa odredena relacijom ekivalencije.

Primjedba 1. Svi elementi u istom razredu su medusobno “ravnopravni” s obzirom na relaciju ekvivalencije. Drugim rijecˇ ima, kada govorimo o razredu ekvivalencije x ] , onda njegov element x nije ni na koji nacˇ in “glavni” reprezentant razreda, nego samo jedan od ravnopravnih predstavnika u skupu x ] . U sljedec´oj definiciji pojavljuje se pojam familije, koji c´e kod nas biti nisˇta drugo nego sinonim za pojam skupa. Rabi se obicˇ no kada je rijecˇ o skupu indeksa (familija indeksa) ili o nekom skupu cˇ iji su elementi skupovi (familija skupova). Razlog za uvodenje ovog pojma je visˇe jezicˇ ne naravi: da se izbjegne nezgrapan izraz “skup skupova”, radije se govori o “familiji skupova”. Definicija. Kazˇ emo da familija podskupova fAi gi2I od X cˇini particiju (disjunktni rastav) skupa X ako vrijedi

20

2. BINARNE RELACIJE

X = i2I Ai , Ai \ Aj =  za sve i j 2 I , i 6= j , tj. familija podskupova je disjunktna. Ponekad c´emo i sam prikaz skupa X = i2I Ai kao disjunktne unije podskupova Ai zvati particijom od X . Primjedba 2. Neka je ρ relacija ekvivalencije na X . Teorem 2 kazˇ e upravo to da je familija podskupova fx ]gx 2X particija skupa X . Sljedec´i stavak predstavlja obrat prethodnoga teorema. On pokazuje da svaka particija skupa X na prirodan nacˇ in odreduje relaciju ekvivalencije cˇ iji razredi ekvivalencije se podudaraju s podskupovima iz particije. (i) (ii)

Teorem 2. Neka je fAi gi2I particija skupa X . Definirajmo relaciju ρ na skupu X tako da je x ρ y onda i samo onda ako x i y pripadaju istom skupu iz particije, tj. postoji i 2 I tako da je x y 2 Ai . Onda je ρ relacija ekvivalencije. Pripadni razredi ekvivalencije podudaraju se sa skupovima Ai .

DOKAZ . Tvrdnja je ocˇ evidna. X A1

A2 x

A3 y

Sl. 2.3. Relacija ekvivalencije odredena particijom: x ρ y .

Definicija. Ako je ρ relacija ekvivalencije na skupu X , onda skup svih pripadnih razreda ekvivalencije zovemo kvocjentni skup od X s obzirom na relaciju ρ i oznacˇ avamo sa X=ρ : X=ρ = fx ]gx 2X Prema prethodnom teoremu vidimo da je kvocjentni skup zapravo isto sˇto i particija skupa X s obzirom na relaciju ekvivalencije ρ . Pocˇetniku je pri prvom susretu vjerojatno tesˇko naviknuti se da razred ekvivalencije x ] , koji je podskup u X , gleda kao jedan jedini element kvocjentnog skupa. Elementi u X se zapravo “grupiraju” u disjunktne skupine (razrede) prema nekom zajednicˇkom svojstvu. U istom razredu nalaze se samo medusobno “srodni” (ekvivalentni) elementi. Na pr. ako je X skup ucˇenika neke sˇkole i ρ relacija “pohadati isti razred”, onda je X=ρ skup svih razreda u sˇkoli. Razred ekvivalencije x ] jednak je razredu u kojem je ucˇenik x .

Primjer 1. Neka je X skup svih ljudi na kugli zemaljskoj. Za dva cˇovjeka x i y rec´i c´emo da su u relaciji ρ ako su drzˇ avljani iste drzˇ ave (pretpostavljamo da nitko nema dvojno drzˇ avljanstvo, te da se granice ne mijenjaju s vremenom 1 ). Razred x ] je skup svih drzˇ avljana one drzˇ ave kojoj pripada osoba x . Kvocjentni skup X=ρ mozˇ e se poistovjetiti sa skupom D svih drzˇ ava u svijetu (svakom razredu x ] pridruzˇ imo onu drzˇ avu cˇ iji je x drzˇ avljan; pridruzˇ ivanje je ocˇ evidno bijektivno): X=ρ ' D . 1 Kada je u jednoj anketi znameniti matematicˇar Steinhaus iz Lavova (1887–1972, Lviv, Ukrajina) bio upitan koliko puta je putovao preko granice, odgovorio je: “Niti jednom. Ali je granica mene presˇla tri puta!”

2.3. RAZREDI EKVIVALENCIJE , PARTICIJA SKUPA

21

Primjer 2. Kvocjentni skup doista mozˇ e biti i beskonacˇan. Uzmimo X = C i definirajmo relaciju ρ ovako: z1 ρ z2 ako je Re z1 = Re z2 . Lako se vidi da je to relacija ekvivalencije, a kvocjentni skup C=ρ jednak je familiji pravaca u kompleksnoj ravnini, koje su paralelne s imaginarnom osi. Primjer 3. Promatrajmo sada iznimno vazˇ nu relaciju kongruencije  modulo n na skupu Z i odredimo kvocjentni skup Z= . Da bi odredili razred ekvivalencije x ] , podijelimo x sa n . Neka je kvocijent pri dijeljenju jednak q , a ostatak jednak r : x = qn + r . Znamo da je ostatak r sadrzˇ an u skupu f0 1 : : : n ; 1g . Buduc´i da je x  r (mod n) , onda je x ] = r] . Prema tome je Z = 0] 1] : : : n ; 1]:

Ova unija je disjunktna, jer niti koja dva razlicˇ ita ostatka iz skupa f0 1 : : : n ; 1g nisu kongruentna modulo n (razlika im je manja od n po apsolutnoj vrijednosti, pa nije djeljiva sa n ). Prema tome vrijedi ovaj jednostavan, ali vazˇ an rezultat: Propozicija 3. Kvocjentni skup na skupu cijelih brojeva po relaciji kongruencije

 modulo n jednak je sljedec´em n -cˇlanom skupu: Z = f0] 1] n ; 1]g  =

:::

Taj skup zove se kvocjentni skup ostataka modulo n , ili skup razreda ostataka pri dijeljenju sa n . Razredi ekvivalencije izgledaju ovako: 0] = 1 ] =

.. .

fqn : q 2 Zg fqn + 1 : q 2 Zg

; 1] = fqn + (n ; 1) : q 2 Zg Razred r] , gdje je r 2 f0 1 n ; 1g , sadrzˇ i skup svih onih cijelih brojeva koji dijeljenjem sa n daju ostatak jednak r , tj. brojeve oblika qn + r , q 2 Z . Korisno je definirati skup nZ svih cjelobrojnih visˇekratnika broja n sa nZ = fkn : k 2 Zg . n

:

:::

Onda particiju (rastav) skupa cijelih brojeva u Propoziciji 3 mozˇ emo pisati i ovako: Z = nZ fnZ + 1g : : : fnZ + (n ; 1)g:

Primijetimo da su dva broja x y 2 Z u relaciji, tj. x ] = y ] , onda i samo onda ako je x ; y 2 nZ . Na pr. buduc´i da je (;1) ; (n ; 1) = ;n 2 nZ , onda je ;1] = n ; 1] , i slicˇ no ;2] = n ; 2] itd. Za n = 2 imamo Z= = f0] 1]g , doticˇ no Z = 0] 1] , pri cˇ emu je 0] = f: : : ;4 ;2 0, 2, 4, : : :g skup svih parnih cijelih brojeva, a 1] = f: : : ;3 ;1 1, 3, 5, : : :g skup svih neparnih. Ovdje je na pr. ;1] = 1] .

22

2. BINARNE RELACIJE

2.4. Josˇ neki primjeri Neke relacije ekvivalencije poznajemo iz osnovne i srednje sˇkole (provjerite): ρ = “biti paralelan sa”, na skupu X svih pravaca u ravnini. Ako je p neki pravac, onda je  p] familija (snop) svih pravaca paralelnih sa p . Skup svih takvih snopova medusobno paralelenih pravaca  p] cˇ ini kvocjentni skup X=ρ . (b) ρ = “biti koncentricˇ an sa” – na skupu svih kruz ˇ nica u zadanoj ravnini R2 . Ako je k neka kruzˇ nica, onda je k] skup kruzˇ nica u ravnini koje su s njom koncentricˇ ne. Kvocjentni skup X=ρ ima za elemente upravo takve familije koncentricˇ nih kruzˇ nica. Relacija “biti okomit na” definirana na skupu svih pravaca u ravnini (ili prostoru) nije refleksivna, simetricˇ na je, i nije tranzitivna. Primjedba 1. Neobicˇno je vazˇ no pitanje mozˇ e li se kvocjentni skup na neki nacˇ in jednostavnije opisati, tako da se njegovi elementi bijektivno poistovjete s elementima nekog drugog, jednostavnijeg skupa. Ovo bijektivno poistovjec´ivanje (relaciju ekvipotentnosti) medu skupovima oznacˇ avamo sa ' . Ilustrirajmo to na prethodnom primjeru (vidi takoder i gornji primjer s drzˇ avama): (a’) Neka je u ravnini R2 zadan koordinatni sustav i X skup svih pravaca u ravnini. Svakoj familiji  p] paralelnih pravaca mozˇ emo pridruzˇ iti kut kojega pravac p (ili bilo koji drugi reprezentant doticˇ nog razreda) zatvara s pozitivnim smjerom x -osi. Moguc´e vrijednosti toga kuta su iz intervala 0 π ) , i pridruzˇ ivanje je ocˇ evidno bijektivno: svakom razredu pripada jednoznacˇ no odreden kut i svakom kutu pripada jednoznacˇ no odreden razred paralelnih pravaca. Tom bijekcijom mozˇ emo poistovjetiti kvocjentni skup X=ρ s intervalom 0 π ) . Dakle X=ρ ' 0 π ) . (b’) Bilo koja familija koncentricˇ nih kruz ˇ nica k] u skupu X svih kruzˇ nica u ravnini je jednoznacˇ no odredena svojim zajednicˇ kim sredisˇtem. Jasno je da svakoj tocˇ ki u ravnini odgovara tocˇ no jedna familija koncentricˇ nih kruzˇ nica i obratno. Prema tome postoji bijekcija sa skupa X=ρ na ravninu R2 . Svaku familiju koncentricˇ nih kruzˇ nica k] mozˇ emo poistovjetiti sa zajednicˇ kim sredisˇtem u ravnini koje doticˇ nu familiju odreduje. Dakle X=ρ ' R2 . (a)

Primjer 1. Kvocjentni skup Z= = f0] 1] : : : n ; 1]g , gdje je  kongruencija modulo n medu cijelim brojevima, mozˇ e se ocˇ evidno poistovjetiti s n -cˇ lanim skupom f0 1 : : : n ; 1g sljedec´om bijekcijom: 0] 7! 0 , 1] 7! 1 , itd. Dakle: Z= ' f0 1 : : : n ; 1g: Primjer 2. Na skupu realnih brojeva R promatrajmo relaciju  definiranu sa x  y ako je x ; y 2 Z . Razredi ekvivalencije su x ] = x + Z . Kvocjentni skup se mozˇ e poistovjetiti sa jedinicˇ nom kruzˇ nicom S1 = fz 2 C : jzj = 1g u kompleksnoj ravnini: svakom x ] 2 R= pridruzˇ imo kompleksni broj e2π xi . Pridruzˇ ivanje ϕ : R= ! S1 , ϕ (x ]) = e2π xi je dobro definirano: ako je x ] = y ] onda je x ; y = k 2 Z , tj. e2π xi = e2π yi e2kπ i = e2π yi , dakle ϕ (x ]) = ϕ (y ]) . Slicˇ no se dokazuje injektivnost: ako je ϕ (x ]) = ϕ (y ]) onda je e2π xi = e2π yi , doticˇ no e2π (x ;y )i = 1 , dakle x ; y 2 Z , ili x ] = y ] . Surjektivnost je ocˇ evidna.

2.4. JOSˇ NEKI PRIMJERI

23

;!

Primjer 3. Oznacˇimo sa X skup svih usmjerenih duzˇ ina AB u R3 , tj. skup svih

poredanih dvojaca tocˇ aka A i B u prostoru. Tocˇ ku A zovemo pocˇ etak, a B docˇ etak

;!

;!

ili kraj usmjerene duzˇ ine. Definirajmo relaciju  na X ovako: AB  CD onda i samo onda ako se polovisˇte duzˇ ine AD podudara s polovisˇtem duzˇ ine BC (ako tocˇ ke A B C D ne lezˇ e na istom pravcu, onda je to isto sˇto i rec´i da je cˇ etverokut ABDC paralelogram). Vrlo lako se vidi da je  relacija ekvivalencije medu usmjerenim ;! duzˇ inama (provjerite). Razredi ekvivalencije  AB ] zovu se vektori, tj. X= je skup

;!

vektora. Vektor  AA ] (pocˇ etak i docˇ etak su isti za svaki reprezentant razreda) zove se

;!

nul-vektor. Obicˇ aj je razred  AB ] oznacˇ iti samo s pomoc´u nekog svog reprezentanta, ;! ;! ;! ;! ;! na pr. upravo sa AB . Cˇ injenicu da je AB  CD pisˇemo obicˇ no kao AB = CD ,

;!

;!

iako to nije sasvim ispravno (bilo bi bolje  AB ] =  CD ] ).

;!

;!

Primjedba 2. U razredu  AB ] usmjerenih duzˇ ina ekvivalentnih sa AB postoji

;!

;!

i reprezentant OD s pocˇ etkom u ishodisˇtu O u R3 (vektor OD zove se radij-vektor tocˇ ke D s obzirom na ishodisˇte O ). Lako se vidi da je tako definirano pridruzˇ ivanje ;!  AB ] 7! D bijekcija iz kvocjentnog skupa X=ρ na skup tocˇ aka iz R3 . Prema tome

skup vektora mozˇ e se poistovjetiti sa skupom tocˇ aka u prostoru (odnosno sa skupom radij-vektora tocˇ aka), tj. X=ρ ' R3 : Zadatci za vjezˇ bu 1. Nadi najmanji cijeli broj r > 0 takav da je ;132  r (mod 3) . 2. Na skupu Z svih cijelih brojeva zadana je relacija ρ sa x ρ y onda i samo onda ako je x ; y djeljiv s 3 . (a) Dokazˇ ite da je ρ relacija ekvivalencije. (b) Nac´i sve razrede ekvivalencije x ] tako da je reprezentant x > 0 i minimalan. (c) U kojem razredu je broj 170 ? 3. Na skupu svih nepraznih podskupova skupa f1 : : : ng zadana je relacija ρ sa A ρ B onda i samo onda ako postoji bijekcija f : A ! B . (a) Dokazˇ i da je ρ relacija ekvivalencije. (b) Koliko ima razreda ekvivalencije? Obrazlozˇ i. (c) Koliko elemenata ima razred A] ako je A = f1g ? 4. Na skupu fz1 : : : z6 g svih sˇestih korijena iz 1 u C zadana je relacija zi ρ zj onda i samo onda ako je zi = zj ei2kπ =3 za neki cijeli broj k . (a) Dokazˇ i da je to relacija ekvivalencije. (b) Koliko ima razreda ekvivalencije? Obrazlozˇ i. (c) Koliko elemenata ima svaki razred? 5. Na skupu X svih pravaca u trodimenzionalnom prostoru zadana je relacija paralelnosti ρ medu pravcima. (a) Pokazˇ i da je to relacija ekvivalencije. (b) Nadi razred od z -osi. (c) Pokazˇ i da postoji prirodna bijekcija sa skupa X na skup svih ravnina kroz ishodisˇte. 6. Na skupu Z  Z zadana je relacija ρ sa (a b) ρ (c d) onda i samo onda ako je a + b = c + d . (a) Dokazˇ i da je to relacija ekvivalencije na Z  Z . (b) Dokazˇ i da postoji bijekcija s kvocjentnog skupa Z  Z=ρ (tj. skupa svih razreda ekvivalencije) na skup Z .

24

2. BINARNE RELACIJE

7. Na skupu A = f1 2 : : : 10g zadana je relacija ρ sa x ρ y onda i samo onda ako je b 6x c = b 6y c , gdje je bx c najvec´i cijeli broj koji je ? x . (a) Dokazˇ i da je ρ relacija ekvivalencije na A . (b) Nadi sve razrede ekvivalencije. Naputci i rjesˇenja

;

2f

g

;

1. Zbog 137 = 3q + r , r 0 1 2 , treba pronac´i ostatak r pri dijeljenju 137 s 3 . 2. (b) Imamo ukupno tri razreda ekvivalencije: 0] = 3Z (svi cijeli brojevi djeljivi s 3 ), 0] = 3Z + 1 (svi cijeli brojevi koji pri dijeljenju s 3 daju ostatak 1 ), 0] = 3Z + 2 (svi cijeli brojevi koji pri dijeljenju s 3 daju ostatak 2 ); (c) Vrijedi 170ρ r , gdje je r ostatak pri dijeljenju 170 s r , jer je 170 = 3q + 3 , tj. 170 r = 3q je djeljivo s 3 . 3. Skupovi A i B su u relaciji onda i samo onda ako A i B imaju isti broj elemenata. (b) Znacˇi razreda ekvivalencije ima ukupno n (svi jednocˇlani podskupovi, pa svi dvocˇlani, itd.). (c) Razred  1 ] sadrz ˇ i sve jednocˇlane podskupove, tj. n elemenata: 1 : : : n . 4. Svi sˇesti korijeni iz 1 leze na jedinicˇnoj kruzˇ nici sa sredisˇtem u ishodisˇtu Gaussove ravnine, u vrhovima pravilnog sˇesterokuta koji sadrzˇ i kompleksni broj 1 (nacrtajte sliku). Ekvivalentni su oni vrhovi kojima je razlika argumenata cjelobrojni visˇekratnik od 2π =3 = 120 . Kut izmedu dva uzastopna vrha je 26π = 60 . Prema tome, u relaciji s 1 je svaki drugi vrh pocˇevsˇi od njega, dakle

;

fg

fg

f1 ei2

2π 6

2π

g

f

π

2π

;

6π

8π

fg

g

ei4 6 i ei 6 ] = ei 6 ei 6 = 1 ei 6 . 5. (c) Svaki pravac jednoznacˇno odreduje ravninu kroz ishodisˇte koja je na nju okomita (vektor normale je vektor smjera pravca). 6. (a) Refleksivnost, tj. (a b) ρ (a b) , vrijedi jer je a + b = a + b ; simetricnost vrijedi, jer iz (a b) ρ (c d) slijedi a + b = c + d , tj. c + d = a + b , dakle (c d) ρ (a b) ; tranzitivnost: iz (a b) ρ (c d) i (c d) ρ (e f ) slijed a + b = c + d i c + d = e + f , dakle a + b = e + f , tj. (a b) ρ (e f ) (b) Ocˇevidno je (a b)] = (c d) : a + b = c + d . To znacˇi da je sa (a b)] a + b dobro definirana funkcija f , tj. ne ovisi o izboru reprezentanta (a b) iz razZ je injekcija, jer ako je f ((a b)]) = f ((c d)]) , to znacˇi da je reda. Funkcija f : Z Z=ρ a + b = c + d , pa je (a b) ρ (c d) , dakle (a b)] = (c d)] . Funkcija f je i surjekcija, jer za svaki zadani k Z je f ((k 0)]) = k + 0 = k . 6 (vec´e od) i < (manje od) potjecˇ u iz 17. st. (T. Harriot, London, 1631). 1ee2

Nemoguc´e je biti matematicˇar, a da nisi u dusˇi i pjesnik. — Sofia KOVALEVSKAYA (1850.-1891.)

3.

Uvod u kombinatoriku

3.1. Produktno pravilo Kombinatorika je grana matematike koja se medu inim bavi i problemom nalazˇ enja kardinalnog broja konacˇ nih skupova, zadanih na vrlo razlicˇ ite nacˇ ine. Pogledajmo nekoliko najjednostavnijih primjera prebrojavanja.

Primjer 1. Neka su m i n cijeli brojevi i m ? n . Cijelih brojeva izmedu m i n ukljucˇ ivo (tj. svih i takvih da je m ? i ? n ), ima ukupno n ; (m ; 1) = n ; m + 1:

DOKAZ . Ako je m = 1 onda je tvrdnja jasna: brojeva i takvih da je 1 ? i ? n ima ukupno n , sˇto je u skladu s tvrdnjom. U nejednakosti m ? i ? n oduzimljemo m ; 1 , nakon cˇ ega dobivamo 1 ? j ? n ; m + 1 , gdje je j = i ; (m ; 1) . Broj i -ova u prvom ‘intervalu’ jednak je broju j -ova u drugom, dakle n ; m + 1 . Na pr. cijelih brojeva izmedu 10 i 20 ukljucˇ ivo ima ukupno 20 ; 9 = 11 . Izmedu ;5 i 8 ukljucˇivo ima ih 8 ; (;6) = 14 . Najvec´i cijeli dio zadanog realnog broja x oznacˇ avamo s bx c . To je najvec´i cijeli broj koji je ? x . Na pr. b3c =3, b3:14c = 3 , a b;3:14c = ;4 . Najvec´e cijelo od x se cˇ esto pojavljuje prigodom prebrojavanja elemenata raznih skupova.

Primjer 2. Neka su k i n zadani prirodni brojevi. Onda svih cjelobrojnih visˇekratnika od k sadrzˇ anih izmedu 1 i n ukljucˇ ivo, ima ukupno b nk c .

DOKAZ . Ako je 1 ? kq ? n za neki prirodni broj q , onda je 1k ? q ? q -ova jednak je najvec´em cijelom broju koji je ? nk , dakle b nk c .

n k

. Broj takvih

Primjer 3. Neka su m i n cijeli brojevi, m ? n , i k zadani prirodni broj. Onda svih cjelobrojnih visˇekratnika od k koji su izmedu m i n ukljucˇ ivo, ima ukupno n ; m ;k 1 : k

j k 



26

3. UVOD U KOMBINATORIKU

DOKAZ . U intervalu m n] postoji isti broj visˇekratnika broja k kao i u intervalu translatiranom za kq , tj. u m + kq n + kq] , gdje je q bilo koji cijeli broj. Stoga mozˇ emo bez gubitka opc´enitosti pretpostaviti da su m > 1 i n > 1 . Primijetite da se izraz b nk c ; b m;k 1 c ne mijenja ako zamijenimo m sa m + kq i n sa n + kq . Prema Primjeru 2 u intervalu 1 n] postoji ukupno b nk c visˇekratnika od k , dok 1 ih u intervalu 1 m ; 1] ima b m; k c . Prema tome u intervalu m n] ima ih ukupno b nk c ; b m;k 1 c , jer u otvorenom intervalu (m ; 1 m) ne postoji niti jedan cjelobrojni visˇekratnik od k .

Primjer 4. Koliko ima parnih brojeva izmedu 12 i 50 ukljucˇivo? Ima ih

b c ; b 112 c = 25 ; 5 = 20 . 50 2

Kardinalni broj nekog skupa A oznacˇ avamo sa jAj . Najjednostavniji kombinatoricˇ ki princip jest pravilo zbrajanja:  ako su konacˇni skupovi A i B disjunktni, onda vrijedi jA Bj = jAj + jBj . Ovo ocˇ evidno svojstvo c´e kasnije biti poopc´eno na slucˇ aj unije skupova koji nisu nuzˇ no disjunktni (Odjeljak 3.4). Spomenimo josˇ pravilo komplementa: ako je X konacˇ an skup s n elemenata i A njegov podskup s k elemenata, onda komplement A = X n A ima n ; k elemenata. Pravilo bijekcije smo vec´ vidjeli: ako su A i B konacˇ ni skupovi medu kojima postoji bijekcija f : A ! B , onda A i B imaju isti broj elemenata. Jedan od temeljnih rezultata na kojem se zasniva prebrojavanje skupova jest da je broj elemenata u Kartezijevu produktu A1  A2 dvaju skupova jednak umnosˇku jA1j jA2j . A1 A 2 A2

A1

Sl. 3.1. Kardinalni broj Kartezijeva produkta skupova.

j  A2 j =

Propozicija 1. Neka su A1 i A2 konacˇ ni skupovi. Onda vrijedi A1

jA1j jA2j .

DOKAZ . Da bi prebrojili koliko ima poredanih dvojaca (x 1 x 2 ) , ucˇ vrstimo element x 2 = a2 2 A2 . Onda je broj elemenata oblika (x 1 a2 ) isti kao i broj elementa x 1 2 A1 , dakle jA1 j . Buduc´i da je taj broj dvojaca (x 1 a2 ) isti za svaki a2 2 A2 , onda je ukupan broj dvojaca (x 1 x 2 ) jednak jA1 j jA2 j . Ova se tvrdnja mozˇ e razumjeti i ovako: ako se neki postupak mozˇ e obaviti na m nacˇ ina, a svaki od postupaka ima n moguc´ih ishoda, onda je ukupan broj moguc´ih ishoda jednak m n . Poopc´enje gornjeg rezultata predstavlja sljedec´i vazˇ an stavak koji govori o kardinalnom broju Kartezijeva produkta skupova.

3.1. PRODUKTNO PRAVILO

27

Teorem 2. (Produktno pravilo) Neka su A1 : : : An neprazni skupovi s konacˇ no mnogo elemenata. Onda je jA1  : : :  Anj = jA1j : : : jAnj () n n ili krac´e j k=1 Ak j = k=1 jAk j .

Q

Q

DOKAZ . Rabit c´emo matematicˇ ku indukciju po n . Za n = 1 tvrdnja je istinita: jA1j = jA1j (baza indukcije). Prepostavimo da tvrdnja () vrijedi za neki prirodan broj n (induktivna pretpostavka). Dokazˇ imo da onda vrijedi i za n + 1 , tj. jA1  : : :  An  An+1 j = jA1j : : : jAnj jAn+1j (induktivni korak). Ocˇ evidno Kartezijev produkt A1  : : :  An  An+1 mozˇ emo poistovjetiti s Kartezijevim produktom dvaju skupova A1  : : :  An i An+1 , tj. sa (A1  : : :  An )  An+1 . Doista, svaki poredani n + 1 -terac (x 1 : : : x n x n+1 ) mozˇ emo poistovjetiti sa poredanim dvojcem (x 1 : : : x n ) x n+1 elementa (x 1 : : : x n ) iz A1 : : :An i x n+1 iz An . Prema prethodnoj propoziciji je onda j(A1  : : :  An )  An+1 j = jA1  : : :  An j jAn+1 j . Tvrdnja slijedi odmah iz induktivne prepostavke, jer je onda izraz na desnoj strani jed+1 jA j . nak (jA1 j : : : jAn j) jAn+1 j = nk= 1 k

;



Q

Neka su A i B dva neprazna, konacˇ na skupa. Oznacˇ imo sa BA skup svih funkcija f : A ! B.

Primjer 5. Za A = f1 2g i B = fa b cg mozˇ emo definirati na pr. funkcije f g h : A ! B sa f (1) = a , f (2) = a , g(1) = a , g(2) = b , h(1) = a , h(2) = c . Funkcije f , g , h su elementi iz BA , ali ima ih josˇ (ukupno devet). Postavlja se pitanje koliko elemenata ima opc´enito skup BA ? Sljedec´i stavak daje odgovor na to pitanje, a ujedno daje i objasˇnjenje za neobicˇ nu oznaku BA . Teorem 3. Neka su A i B konacˇ ni skupovi, tako da prvi ima n elemenata a drugi m . Onda svih funkcija f : A ! B ima ukupno mn , tj. vrijedi jBA j = mn .

DOKAZ . Bilo koja funkcija f : A ! B mozˇ e vrijednost f (a1 ) poprimiti na jBj = m nacˇ ina, f (a2 ) takoder, itd. do f (an ) . Prema produktnom pravilu onda funkciju f mozˇ emo zadati na m m : : : m = mn nacˇ ina, tj. jBA j = mn . 32

Primjer 6. Na pr. svih funkcija iz dvocˇlanog skupa u trocˇlani ima ukupno =

9 . Pokusˇajte ih sve ispisati.

Korolar 4. Broj poredanih n –teraca sastavljenih od 0 i 1 (ili neka druga dva razlicˇ ita elementa) jednak je 2n .

DOKAZ . Tvrdnja slijedi neposredno iz prethodnog teorema uz A B = f0 1g .

Primjer 7. (a) Za n

=

fa1

:::

an g i

4 dobivamo da postoji 24 = 16 poredanih cˇ etveraca nula i jedinica, a za n = 10 dobivamo vec´ 210 = 1024 poredanih deseteraca nula i jedinica. Za n = 270 imamo 2270 poredanih 270 -teraca nula i jedinica. To je visˇe od 1080 , koliko iznosi procijenjeni broj atoma u vidljivom svemiru! Vidimo da problem prebrojavanja n -teraca nula i jedinica, opisan funkcijom poput 2n (eksponencijalna funkcija), ima kombinatornu eksploziju. =

28

3. UVOD U KOMBINATORIKU

(b) U glavnoj memoriji racˇ unala podatci se smjesˇtavaju u memorijske c´elije. Svaka c´elija ima svoju adresu. Kod nekih racˇ unala adresa se sastoji od osam znakova koji se zovu bitovi, a vrijednost znaka (bita) je nula ili jedan. Naziv ‘bit’ dolazi od engl. binary digit, tj. binarna znamenka 0 ili 1 , a uveo ga je Claude Shannon (1916.–2001.). Svaki takav osmerac bitova, tj. poredani slijed od osam nula i jedinica, zove se bajt (engl. byte). Ukupan broj bajtova iznosi prema produktnom pravilu 28 = 256 . Prema tome postoji ukupno 256 memorijskih c´elija u koje se informacije mogu smjestiti. Neka racˇ unala rabe dvo–bajtno adresiranje, tj. adresa memorijske c´elije sastoji se od 2 uzastopna bajta. Za njih je ukupan broj adresa jednak 256 256 = 65 536 . Neka racˇ unala pak koriste adresiranje c´elija sa cˇ etiri bajta, pa je ukupan broj adresa dostupnih za pohranjivanje informacija u memorijske c´elije jednak 2564 = 4 294 967 296 .

Primjer 8. Automobilske tablice sadrzˇ e ime grada, zatim tri znamenke i josˇ dva slova abecede. Koliko je takvih tablica moguc´e napraviti za Vukovar i Dubrovnik zajedno? Svaka od tri znamenke mozˇ e imati neku od 10 vrijednosti 0 1 2 : : : 9 . Svako od dva preostala slova mozˇ e imati jedno od 22 vrijednosti: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, R, S, T, U, V, Z. Prema produktnom pravilu je broj moguc´ih tablica samo za jedan grad jednak 103 222 = 484 000 . Za dva grada c´e vrijednost biti dvostruka. Kao i obicˇ no, za zadani skup X definiramo skup 2X svih podskupova od X (dakle ukljucˇ ujuc´i i  i X ). Zovemo ga partitivni skup od X . Oznaka 2X za partitivni skup od X je posljedak sljedec´eg vazˇ nog stavka: Teorem 5. Neka je X konacˇ an skup od n elemenata. Onda on ima ukupna 2n

podskupova, tj. vrijedi j2X j = 2n .

DOKAZ . a) Neka je X = fx 1 : : : x n g Dokazˇ imo da postoji bijekcija iz partitivnog skupa 2X na skup f0 1gn svih poredanih n –teraca nula i jedinica. Definirajmo F : 2X ! f0 1gn kodiranjem podskupa A 2 2X skupa X na sljedec´i nacˇ in. Ako je A =  stavljamo F (A) = (0 : : : 0) . Ako je A 6=  , onda neka je F (A) n –terac u kojem jedinice dolaze na k –tom mjestu u n –tercu onda i samo onda ako je x k 2 A (a inacˇ e nula). Na pr. za A = fx 1 x 3 x 4 g stavljamo F (A) = (1 0 1 1 0 : : : 0) . Vrijednost F (A) je n –terac koji predstavlja kˆod skupa A . Funkcija F je ocˇ evidno injektivna, jer ako su A B 2 2X i F (A) = F (B) onda je A = B . Funkcija je surjektivna jer za svaki n –terac iz f0 1gn mozˇ emo ocˇ itati skup A koji je n –tercem kodiran (ako je na k -tom mjestu jedinica, onda je x k 2 A , a ako je nula onda x k 2 = A ). b) Buduc´i da je F : 2X ! f0 1gn bijekcija, onda je

j2X j = jf0 1gnj = 2n

gdje smo u predzadnjoj jednakosti rabili Teorem 2.

Primjedba 1. Vrlo detaljan dokaz koji smo sproveli svodi se ukratko na sljedec´e: broj podskupova n -cˇ lanog skupa jednak je broju poredanih n -teraca nula i jedinica. Buduc´i da na svakom mjestu u n -tercu dolaze po dvije moguc´e vrijednosti ( 0 ili 1 ), ukupan broj n -teraca iznosi prema produktnom pravilu 2n .

3.1. PRODUKTNO PRAVILO

29

Primjedba 2. Kodiranje skupa A obavili smo u dokazu prethodnog stavka s pomoc´u konacˇ nog slijeda nula i jedinica. Taj slijed se mozˇ e gledati i kao funkcija kA : X ! f0 1g , definirana sa

1

ako je x 2 A , 0 ako je x 2 = A: Ova funkcija zove se karakteristicˇna funkcija skupa A . To je funkcija koja ‘raspoznaje’ skup A . Primjedba 3. Dobro je poznato da za sve prirodne brojeve n vrijedi nejednakost 2n > n (to se lako dokazuje indukcijom). Drugim rijecˇ ima, za bilo koji konacˇ ni skup X vrijedi j2X j > jX j . Ova tvrdnja je ocˇ evidna, jer partitivni skup 2X sadrzˇ i medu inim i sve jednocˇ lane podskupove od X , kojih ima upravo jX j . Podsjetimo se pojma Booleove funkcije n varijabla. To je funkcija koja bilo kojem poredanom n -tercu nula i jedinica pridruzˇ uje nulu ili jedinicu, tj. funkcija F : f0 1gn ! f0 1g . kA (x )

=

Propozicija 6. Neka je zadan prirodan broj n . Svih Booleovih funkcija n varin 0 1 , ima ukupno 22 . jabla, F : 0 1 n

f g !f g

DOKAZ . Oznacˇ imo B = f0 1g . Onda je F 2 BA . Trazˇ imo dakle jBA j , gdje je A = Bn . Zbog Teorema 2 je jAj = 2n . Iz Teorema 5 dobivamo da je jBAj = jBjjAj = 22n . 2

Primjer 9. Booleovih funkcija s dvije varijable ima ukupno 22

24 = 16 , s tri varijable 2 = 28 = 256 , a s cˇ etiri varijable ima 2 = 216 = 65 536 . Booleovih funkcija s osam varijablˆa ima visˇe od 1077 , a s devet varijablˆa visˇe od 10154 . Vec´ smo spomenuli procjenu fizicˇ ara da ukupni broj atoma u vidljivom svemiru iznosi oko n 1080 . Kao sˇto vidimo, imamo kombinatornu eksploziju. Funkcija 22 raste mnogo brzˇ e od eksponencijalne funkcije 2n , pa cˇ ak i od faktorijelne n! . 23

24

=

Primjer 10. Zadan je broj n = 5200 . Koliko ima djelitelja od n ? Koliko ima parnih, a koliko nepanih djelitelja od n ? Rjesˇenje. Rastavim n na proste faktore. Vrijedi n = 52 100 = 26 2 50 2 = 4 2 α β γ : : : = 2 5 13 . Svi djelitelji od n su oblika 2 5 13 , gdje su α 2 f0 1 2 3 4g , β 2 f0 1 2g , γ 2 f0 1g . Prema produktnom pravilu svih djelitalja od n ima ukupno 5 3 2 = 30 . Parni djelitelji su oblika 2α 5β 13γ , gdje su α 2 f1 2 3 4g (zbog parnosti od n mora potencija od 2 biti barem 1 ), β 2 f0 1 2g , γ 2 f0 1g . Zato parnih djelitelja ima 4 3 2 = 24 . Neparni djelitelji su oblika 20 5δ 13ε , gdje su δ 2 f0 1 2g , ε 2 f0 1g pa ih ima 3 2 = 6 . Ili krac´e, prema pravilu komplementa, neparnih djelitelja ima 30 ; 24 = 6 . Primjedba. Iz prethodnog primjera vidimo da c´e opc´enito vrijediti ovo: ako je α α n = p1 1 : : : pk k prirodan broj rastavljen na proste faktore, onda je broj svih pozitivnih djelitelja od n jednak (α 1 + 1) : : : (α k + 1)

30

3. UVOD U KOMBINATORIKU

Primjer 11. Koliko dijagonala ima konveksni n -terokut u ravnini. Za skup S kaˇzemo da je konveksan ako za bilo koje dvije njego toˇcke A i B vrijedi da je i duˇzina AB sadrˇzana u S . Rjesˇenje. Toˇcku Ti dijagonale Ti Tj moˇzemo odabrati na n naˇcina. Potom, toˇcku Tj moˇzemo odabrati na n ; 3 naˇcina, jer to ne moˇze biti toˇcka Ti niti dvije susjedne toˇcke od Ti . Zbog Ti Tj = Tj Ti umnoˇzak n (n ; 3) treba podijeliti s 2 , rezultat je n(n;3) . 2 2?

Primjer 12. Koliko ima prirodnih brojeva od 1 do 10n koji sadrˇze znamenku

Ima 9n ; 1 brojeva koji ne sadrˇze znamenku 2 , jer za svaku od n znamenaka imamo 9 mogu´cnosti, i izuzimamo sluˇcaj kada su sve znamenke nula. Dakle, onih koji sadrˇze znamenku 2 ima 10n ; 9n + 1 .

Primjer 13. Koliko ima n-znamenkastih brojeva koji sadrˇze znamenku 2 ?

Svih n -znamenkastih brojeva ima 10n ; 10n;1 = 9 10n;1 . n -znamenkastih brojeva koji ne sadrˇze znamenku 2 ima 8 9n;1 , jer prva znamenka smije biti it skupa f1 3 4 5 6 7 8 9g , a sve ostale znamenke iz skupa f0 1 3 4 5 6 7 8 9g . Stoga, n -znamenkastih brojeva koji sadrˇze znamenku 2 ima 9 10n;1 ; 8 9n;1 . a) b) c) d)

Primjer 14. Koliko ima n-znamenkastih brojeva s:

barem jednom parnom znamenkom? toˇcno jednom parnom znamenkom? najviˇse jednom parnom znamenkom? toˇcno jednom neparnom znamenkom? Rjesˇenje. a) Od svih n -znamenkastih brojeva oduzmimo one koji na svih n mjesta imaju samo neparne znamenke 1 3 5 7 9 :

9 10n;1 ; 5n : b) Za odabir parne znamenke ima pet mogu´cnosti: 0 2 4 6 8 i moˇzemo je smjestiti na n mjesta. Na ostalih n ; 1 mjesta dolaze neparne 1 3 5 7 9 . Od svih ovako izgeneriranih brojeva joˇs moramo izbaciti samo one koji na prvom mjestu imaju znamenku 0 (jer takvi nisu n-znamenkasti): 5n 5n;1 ; 5n;1 = (5n ; 1) 5n;1 : c) Ovdje moramo prebrojiti sve n-znamenkaste brojeve bez parnih znamenki i s toˇcno jednom parnom znamenkom:

5n + (5n ; 1) 5n;1 = (5n + 4) 5n;1 : d) Za odabir neparne znamenke ima pet mogu´cnosti: 1 3 5 7 9 i moˇzemo ih smjestiti na n mjesta. Na ostalih n ; 1 mjesta dolaze parne 0 2 4 6 8 . Od svih ovako izgeneriranih brojeva moramo izbaciti one koji na prvom mjestu imaju znamenku 0 , a kod takvih za odabir mjesta neparne znamenke ostaje n ; 1 mjesto: 5n 5n;1 ; (n ; 1) 5n;1

= ( 4n + 1) 5

;

n 1

:

3.2. VARIJACIJE , PERMUTACIJE I KOMBINACIJE

BEZ PONAVLJANJA

31

3.2. Varijacije, permutacije i kombinacije bez ponavljanja Opisat c´emo najprije neke osnovne metode prebrojavanja za dvije vrste objekata: a) varijacije (koje ukljucˇ uju i permutacije kao specijalan slucˇ aj), tj. poredane n – terce elemenata nekog konacˇ nog skupa, u kojima je dakle poredak bitan, b) kombinacije, gdje se prebrojavaju skupovi i tzv. multiskupovi, kod kojih poredak elemenata nije bitan. Svaki od ovih objekata mozˇ e biti dvojak: Varijacije i kombinacije bez ponavljanja, i varijacije i kombinacije s ponavljanjem.

A. Varijacije bez ponavljanja, permutacije.

Definicija. Varijacijom bez ponavljanja reda k n -cˇlanog skupa An = fa1 : : : , an g , k ? n , zovemo bilo koji poredani k -terac razlicˇ itih elemenata iz An . U slucˇ aju kada imamo k = n , tj. kada gledamo poredane n -terce n -cˇ lanog skupa, onda takve varijacije zovemo permutacijama n -cˇ lanog skupa. Svaku permutaciju skupa An mozˇ emo poistovjetiti sa nekom bijekcijom f : An ! An . Primjer 1. Ako je na pr. A3 = f1 2 3g , onda za k = 2 imamo sˇest poredanih dvojaca: (1 2) , (1 3) , (2 1) , (2 3) , (3 1) , (3 2) (pisˇemo ih u leksikografskom poretku, tj. u “rastuc´em” slijedu). Za k = 3 imamo ovih sˇest poredanih trojaca tj. permutacija: (1 2 3) , (1 3 2) , (2 1 3) , (2 3 1) , (3 1 2) , (3 2 1) . Na pr. permutaciji (3 2 1) odgovara bijekcija f : A3 ! A3 definirana sa f (1) = 3 , f (2) = 2 , f (3) = 1 . Opsˇirnije o permutacijama bit c´e rijecˇ i kasnije.

Teorem 1. Broj varijacija reda k ? n skupa od n elemenata, tj. broj poredanih k -teraca razlicˇ itih elemenata iz n -cˇ lanog skupa, jednak je n! n(n ; 1) : : : (n ; k + 1) = : (n ; k)! Ukupan broj permutacija n -cˇ lanog skupa jednak je n! .

DOKAZ . Ako smo u nekom k -tercu na prvo mjesto stavili neki od n elemenata, onda na drugo mjesto mozˇ emo staviti bilo koji od preostalih n ; 1 elemenata, na trec´e bilo koji od preostalih n ; 2 , itd., na zadnje bilo koji od preostalih n ; k + 1 . Prema produktnom pravilu onda imamo ukupno n(n ; 1)(n ; 2) : : : (n ; k + 1) varijacija bez ponavljanja reda k . Odavde za k = n dobivamo odmah i broj permutacija.

Primjedba 1. Broj n! raste mnogo brzˇ e nego bilo koja eksponencijalna funkn cija, jer vrijedi na pr. 2n! ! 0 kad n ! 1 . Broj 10! = 3 628 800 jednak je zacˇ udo tocˇ no broju sekunda u sˇest tjedana. Broj 11! vec´i je od broja sekunda u godini, a 13! je vec´i od broja sekunda u stoljec´u. Broj 60! vec´i je od 1080 , koji, kao sˇto smo vec´ rekli, predstavlja procjenu broja atoma u vidljivom svemiru! Prema tome, broj permutacija n -cˇ lanog skupa, tj. broj n! , ima kombinatornu eksploziju.

32

3. UVOD U KOMBINATORIKU

Primjer 2. Neka je A = fa1 : : : ak g , B = fb1 : : : bn g i k ? n . Onda je broj svih injektivnih funkcija f : A ! B jednak n(n ; 1) : : : (n ; k + 1) . Rjesˇenje. Doista, za injektivnu funkciju f mozˇ emo vrijednost f (a1 ) birati na n nacˇ ina, zatim f (a2 ) na n ; 1 nacˇ ina,: : : , f (ak ) na n ; k + 1 nacˇ ina, pa tvrdnja slijedi iz produktnog pravila. Ako je k > n onda ocˇ evidno nema niti jedne injektivne funkcije iz A u B . Primjer 3. Na koliko se naˇcina 6 putnika moˇze rasporediti u autobus s 15 sjedala? Rjesˇenje. Putnike razlikujemo: prvog moˇzemo smjestiti na 15 naˇcina, drugog na 14 naˇcina (jer ne moˇze sjesti na mjesto gdje ve´c sjedi prvi putnik), tre´ceg na 13 naˇcina,: : : , sˇ estog na 10 naˇcina. Rijeˇc je o varijacijama bez ponavljanja 15 elemenata, reda 6 , dakle na 15 14 13 12 11 10 = 3 603 600 naˇcina. Primjer 4. Na koliko se naˇcina 30 uˇcenika moˇze rasporediti u uˇcionici s 30

mjesta?

Rjesˇenje. Rijeˇc je o permutacijama 30 elemenata, dakle na 30! naˇcina.

 2 65 1032 :

Primjer 5. Na koliko naˇcina n ljudi moˇze sjesti za okrugli stol? Pretpostavka je da zarotirane rasporede smatramo istima. Rjesˇenje. Za bilo koji raspored imamo n istih zarotiranih. Zato ukupan broj rasporeda (koji ukljuˇcuje i zarotirane) treba podijeliti sa n . Rezultat je n! n = ( n ; 1) ! . Ili na drugi naˇcin, uoˇcimo jednog cˇ ovjeka, i rasporedimo ga na bilo koje od n mjesta. Nadalje rasporedujemo u niz ljude koji redom sjede njemu slijeva. A to se moˇze na (n ; 1)! naˇ cina.

B. Kombinacije bez ponavljanja.

fa1

Definicija. Kombinacija bez ponavljanja reda k n -cˇlanog skupa An

=

an g je bilo koji njegov k -cˇ lani podskup. Dakle kombinacija bez ponavljanja je samo drugi naziv za podskup skupa. :::

Teorem 2. Broj k -cˇ lanih podskupova n -cˇ lanog skupa (doticˇ no broj kombinacija bez ponavljanja reda k , k ? n ) jednak je n n(n ; 1) : : : (n ; k + 1) := : k! k



DOKAZ . Prema prethodnom stavku svih poredanih k -teraca ima n(n ; 1) : : : (n ; k + 1) . Neka je (a1 : : : ak ) neki takav k -terac. Svaka od njegovih k! permutacija definira isti skup fa1 : : : ak g . To znacˇ i da skup od ukupno n(n ; 1) : : : (n ; k + 1) poredanih k -teraca mozˇ emo grupirati u mnozˇ ine od po k! varijacija od kojih svaka n(n;1):::(n;k+1) odreduje isti skup. Dakle ukupan broj k -cˇ lanih podskupova iznosi . k!

3.2. VARIJACIJE , PERMUTACIJE I KOMBINACIJE

33

BEZ PONAVLJANJA

Primjedba ;  2. Tvrdnja vrijedi i za k = 0 , kojemu odgovara prazan skup, jer je n 0 =

po definiciji

1.

;n = n! . Odavde k ; k!(n;;k)!  n odmah dobivamo svojstvo simetricˇ nosti binomnih koeficijenata: nk = n; k . To se ;  n mozˇ e lako dokazati i kombinatoricˇ ki. Doista, svakom od k k -cˇ lanih podskupova skupa; fa1 an g mozˇ emo bijektivno pridruzˇ iti (n ; k) -cˇ lani komplement, a njih ima n . Zbog bijektivnosti je njihov broj isti. Primjedba 3. Kao sˇto znamo, za 0 ? k

? n vrijedi

:::

;

n k

Propozicija 3. Za sve n k

2 N k ? n vrijedi

;n = ;n;1 + ;n;1 k

;

k 1

k

DOKAZ . 1) Prvi nacˇ in. Tvrdnju je lako dokazati algebarski:

n k



= =

n! n! n;k k = + k!(n ; k)! k!(n ; k)! n n (n ; 1)! (n ; 1)! + = k!(n ; k ; 1)! (k ; 1)!(n ; k)!



n ; 1 n ; 1 + k;1

k

2) Dokazˇ imo istu tvrdnju na drugi nacˇ in - kombinatoricˇ ki. Ucˇ vrstimo jedan od n elemenata (recimo prvi) u n -cˇ lanom skupu. Izbor k od ukupno n elemenata mozˇ emo provesti na jedan od sljedec´a dva nacˇ ina:

; 

a) ili odabiremo k elemenata razlicˇitih od prvog, a to je isto sˇto i odabrati k elemenata medu preostalih n ; 1 elemenata; to mozˇ emo ucˇ initi na n;k 1 nacˇ ina; b) ili odabiremo k elemenata tako da je medu njima i prvi. Tome ocˇ evidno odgovara zapravo odabir k ; 1 elemenata medu preostalih n ; 1 elemenata, sˇto se mozˇ e ;1 nacˇina. izvrsˇiti na nk; 1 3) U Odjeljku 3.6 o funkcijama izvodnicama vidjeti i trec´i, vrlo jednostavan dokaz ove tvrdnje. (vidi Primjer 3.6.5).

; 

;

S pomoc´u gornje relacije izmedu binomnih koeficijenata gradi se znameniti Pascalov trokut brojeva nk (bilo bi ga ispravnije zvati Kineski trokut, jer su ga Kinezi znali davno prije Pascala):

;4

;3 0

0

;2 0

;4

;1 0

;3 1

1

:::

1

;2 1

;4

;1 1

;3 2

2

:::

;2 2

;4

;3 3

3

:::

;4 4

:::

1

1 :::

1 4

1 3 :::

1 2 6

1 3 :::

1 4

1 :::

1

;

Nije tesˇko vidjeti da graf diskretne funkcije f : f0 1 : : : ng ! N , f (k) = nk , ima oblik zvonolike krivulje, a svoj maksimum dostizˇ e na sredini zvona, tj. za k = bn=2c (najvec´i cijeli broj koji je ? n=2 ). Binomni koeficijenti su povezani s izracˇ unom produkta od n binoma (x + y )n za bilo koje x y 2 R .

(x + y )(x + y ) : : : (x + y ) ,

=

34

3. UVOD U KOMBINATORIKU Propozicija 4. (Binomna formula) Za sve x y n (x + y ) =

n   X n k

k

k=0

2 R vrijedi

x y n;k :

DOKAZ . Tvrdnja se mozˇ e dokazati indukcijom po n , pri cˇ emu onda treba rabiti i prethodnu propoziciju. Ovdje c´emo dati vrlo jednostavan kombinatoricˇ ki dokaz. Doista, u izrazu n (x + y ) = (x + y )(x + y ) : : : (x + y )

c´e nakon mnozˇ enja opc´i cˇ lan imati oblik ck x k y n;k , gdje je ck konstanta koju zˇ elimo odrediti. Produkt x k y n;k mozˇ e se dobiti tako da uzmemo k elemenata x iz ukupno n binoma x + y u umnosˇku (x + y )n . Tih k elemenata mozˇ emo odabrati na bilo koji nacˇ in medu n binoma, dakle na nk nacˇ ina. Element y se nakon toga uzimlje iz preostalih n ; k binoma. Prema tome je ck = nk .

;

;

Primjedba 4. Vazˇ an specijalan slucˇaj dobivamo za x = y = 1 : 2

n

=

n n +

+

:::

+

n

:

n 0 1 Na desnoj strani imamo zapravo zbroj broja k -cˇ lanih podskupova n -cˇ lanog skupa za k = 0 (cˇ emu odgovara prazan skup), k = 1 (svi jednocˇ lani podskupovi) itd. do n . Vidimo da su tu zapravo ukljucˇ eni svi podskupovi n cˇ lanog skupa. Dakle gornja relacija pokazuje da partitivni skup n -cˇ lanog skupa ima 2n elemenata, sˇto znamo vec´ od prije (vidi Teorem 3.1.5). Iz Propozicije 4 za x = ;1 i y = 1 dobivamo n X

; ; ;

;1)k

(

n k

=

k=0 n n n = 1 + 3 + 5 + :::,

; ; ;

0

tj. n0 + n2 + n4 + : : : tj. broj podskupova n -cˇlanog skupa s parnim brojem elemenata jednak je broju podskupova s neparnim brojem elemenata. Ta je tvrdnja ocˇ evidna ako je n paran broj, zbog svojstva simetricˇ nosti binomnih koeficijenata (vidi Pascalov trokut).

Primjer 6. Na koliko se naˇcina u razredu od 30 uˇcenika mogu odabrati trojica predstavnika? Rjesˇenje. Predstavnici su ravnopravni, dakle biramo troˇclani podskup iz 30 -ˇcla302928 = 4060 naˇ cina. nog skupa. To se moˇze na 30 3 = 3!

; 

Primjer 7. U ravnini je zadano n razliˇcitih toˇcaka od kojih nikoje 3 nisu na istom pravcu. Koliko ima a) duˇzina, b) trokuta, s vrhovima u zadanim toˇckama? Duˇzinu odreduju bilo koje dvije toˇcke, bez obzira na poredak. Moˇzemo ih odabrati na n2 = n(n2;1) naˇcina. Sliˇcno trokuta s vrhovima u zadanim toˇckama ima koliko i troˇclanih podskupova tog skupa od n tocˇ aka, tj. n3 = n(n;16)(n;2) .

;

;

3.2. VARIJACIJE , PERMUTACIJE I KOMBINACIJE

35

BEZ PONAVLJANJA

Primjer 8. Koliko kombinacija ima u a) LOTU 6 od 45 ; b) LOTU 7 od 39 ? Rjesˇenje. Poredak izvuˇcenih kuglica u LOTU nije bitan, pa je rijeˇc o kombinacijama bez ponavljanja: 454443424140 = 8145060 , a) 45 6 = 6! 39383736353433 = 15380937 . b) 39 = 7 7!

;  ; 

Primjer 9. Sˇ esnaest umjetnika javilo se na likovni natjeˇcaj. Od toga su devetorica predala po 2 rada, a sedmorica po 1 rad. Dodjeljuju se 1 glavna i 3 ravnopravne utjeˇsne nagrade. Na koliko je to naˇcina mogu´ce ako: a) svakom umjetniku moˇze biti nagraden samo jedan rad? b) svaki rad svakog umjetnika moˇze dobiti nagradu? Rjesˇenje. Nazovimo umjetnike koji su predali po 2 rada skupinom A, a one koji su predali po 1 rad skupinom B. a) Ima 91 2 naˇcina da glavnu nagradu dobije rad umjetnika iz skupine A. Potom 3 utjeˇsne nagrade mogu na sljede´ci naˇcin biti rasporedene izmedu skupine A (bez umjetnika koji je dobio glavnu nagradu) i skupine B: 0 + 3 , 1 + 2 , 2 + 1 , 3 + 0 . Prebrojimo redom sve cˇ etri mogu´cnosti. 7 8 7 8 7 8 + + + 23 : 2 22 3 1 2 2 1 3

;

 

 

  ;

Da glavnu nagradu dobije rad umjetnika iz skupine B ima 71 naˇcina. 3 utjeˇsne nagrade zatim mogu na sljede´ci naˇcin biti rasporedene izmedu skupine A i skupine B (bez umjetnika koji je dobio glavnu nagradu): 0 + 3 , 1 + 2 , 2 + 1 , 3 + 0 . Prebrojimo redom sve cˇ etri mogu´cnosti. 6 9 6 9 6 9 + + + 23 : 2 22 3 1 2 2 1 3 Ukupno je dakle 9 7 7 8 7 8 8 + 2+ 22 + 23 2 1 3 2 1 1 2 3 7 6 6 9 6 9 9 + + 2+ 22 + 23 1 3 2 1 1 2 3 = 42266: b) U ovom sluˇcaju je znatno lakˇse prebrojiti sve mogu´cnosti, jer sve radove gledamo zajedno bez obzira je li ih predao umjetnik iz skupine A ili B. Glavna nagrada se moˇze dodijeliti na 25 naˇcina, potom 3 utjeˇsne na 24 3 , ukupno na

 

 

      

  

      

25

 

24 3

  

 

 

; 

=

50600:

Primjer 10. Od 7 zˇ ena i 4 muˇskarca treba izabrati delegaciju. Na koliko se naˇcina to moˇze uˇciniti ako se ta delegacija sastoji od: a) petero ljudi i to 3 zˇ ene i 2 muˇskarca;

36

3. UVOD U KOMBINATORIKU

bilo kojeg broja ljudi, ali jednako zˇ ena i muˇskaraca; petero ljudi, od kojih su barem dvije zˇ ene; petero ljudi s tim da jedan od njih bude ve´c unaprijed odredena zˇ ena; sˇ estoro ljudi, po troje oba spola, s tim da u delegaciju ne mogu u´ci zajedno po jedan unaprijed odredeni muˇskarac i zˇ ena. Rjesˇenje. ˇ a) Zene u delegaciji moˇzemo izabrati na 73 naˇcina, a muˇskarac na 42 . Ukupno delegaciju moˇzemo odabrati na 73 42 = 210 naˇcina. b) Prebrojimo posebno sve delegacije od 1 zˇ ene + 1 muˇskarca, zatim 2 zˇ ene + 2 muˇskarca, 3 zˇ ene + 3 muˇskarca, 4 zˇ ene + 4 muˇskarca. Ukupno to je 7 4 7 4 7 4 7 4 + + + = 329: 1 1 2 2 3 3 4 4 b) c) d) e)

;

; ;

;

           

c) Prebrojimo posebno sve delegacije s toˇcno 2 , 3 , 4 ili 5 zˇ ena 7 4 7 4 7 4 7 + + + = 455: 2 3 3 2 4 1 5

          

;  ;  ; ; 

d) Ako je u delegaciji jedna ve´c unaprijed odredena zˇ ena, preostaje odabrati cina. joˇs cˇ etvoro ljudi bez obzira na spol. To se moˇze na 7+4 3 = 10 4 = 210 naˇ 7 4 ˇ e) Od svih delegacija s 3 zene i 3 muˇskarca (kojih ima 3 3 ) oduzmimo one u kojima je zabranjeni par (kojih ima 62 32 ). Rezultat je

; ;  74 63 3

3

;

2

2

=

95:

3.3. Permutacije, varijacije i kombinacije s ponavljanjem

A. Permutacije s ponavljanjem.

Definicija. Zadan je skup od k elemenata Ak = fa1 : : : ak g . Promatramo sve poredane n -terce elemenata tog skupa u kojima se element a1 pojavljuje n1 puta, a2 n2 -puta itd., pri cˇ emu je dakako n1 + n2 + : : : + nk = n . Takve n -terce zovemo permutacijama n -tog reda s ponavljanjem. Permutirati znacˇ i premjestiti, permutacija je premjesˇtaj. Primjer 1. Neka je zadan dvocˇlani skup A2 = f0 1g (tj. k = 2 , a1 = 0 , a2 = 1 ) i neka je n = 3 , n1 = 1 , n2 = 2 . Skup svih permutacija trec´eg reda s ponavljanjem ima tri elementa: (0 1 1) , (1 0 1) , (1 1 0) . Vidimo da se ovdje radi zapravo o broju dvocˇ lanih podskupova trocˇ lanog skupa (prisjetite se kodiranja u dokazu Teorema 3.1.5), kojih ima 32 = 3 . Na isti nacˇ in za skup f0 1g je odgovarajuc´i broj permutacija n -toga reda, uz n1 = k i n2 = n ; k , jednak k!(nn!;k)! = n n! !n ! .

;

1

2

3.3. PERMUTACIJE , VARIJACIJE

37

I KOMBINACIJE S PONAVLJANJEM

Teorem 1. Broj permutacija n -tog reda k -cˇ lanog skupa fa1 : : : ak g , u kojima se element ai pojavljuje ni puta, i = 1 : : : k , n = n1 + : : : + nk , jednak je

n! : n1 ! : : : nk !

DOKAZ . Zamislimo da je zadano n mjesta koja u slijedu popunjavamo na zˇ eljeni nacˇ in s elementima skupa fa1 : : : ak g . Prvih n1 kopija elementa a1 mozˇ emo na n mjesta razmjestiti na nn nacˇ ina. Uz bilo koji takav razmjesˇtaj pogledajmo preostalih n ; n1

; 

;



n1 mjesta za n2 kopija elementa a2 . Njih mozˇ emo razmjestiti na n; nacˇ ina. Zatim n2 uz bilo koji zadani razmjesˇtaj n1 elemenata a1 i n2 elemenata a2 preostaje n ; n1 ; n2 mjesta. Razmjesˇtaj n3 kopija elementa a3 na ta mjesta mozˇ emo obaviti na n;nn1 ;n2 3 nacˇ ina, itd. Prema produktnom pravilu, ukupni broj zˇ eljenih razmjesˇtaja (permutacija s ponavljanjem) iznosi 1

;



 n   n ; n  n ; n ; n   n ; n ; ; n  1 1 2 1 k;1 =

=

:::

:::

n2 n3 nk n! (n ; n1 )! (n ; n1 ; n2 )!) (n ; n1 ; : : : ; nk;1 ) ::: : n1 !(n ; n1 )! n2 !(n ; n1 ; n2 )! n3 !(n ; n1 ; n2 ; n3 )! nk !(n ; n1 ; : : : ; nk )! n1

Nakon skrac´ivanja svih parova zagrada dobivamo rezultat u teoremu.

Primjedba 1. Kao sˇto smo vidjeli iz dokaza binomnog teorema, u potenciji

y )n , tj. u (x + y )(x + y ) : : : (x + y ) , broj nacˇ ina na koji mozˇ emo odabrati k x -ova (i time n ; k y -a) jednak je upravo koeficijentu uz x k y n;k u binomnom razvoju, tj. broju nk . Slicˇ no vrijedi i za trinome x + y + z i opc´enito, za multinome x1 + x2 + : : : + xk : (x +

;

Teorem 2. (Multinomni teorem) Broj nacˇ ina na koji u potenciji (x 1 + x 2 +

:::

n

+ xk )

mozˇ emo odabrati n1 puta varijablu x 1 , n2 puta varijablu x 2 ,: : : , nk puta varijablu x k , i to po jednu iz svakog od n faktora, n1 + n2 + : : : nk = n , jednak je n! : n1 !n2 ! : : : nk ! n

n

n

To je upravo multinomni koeficijent uz x 11 x 22 : : : x k k u razvoju (x 1 + x 2 + : : : + x k )n , tj.: n! n n n n (x 1 + x 2 + : : : + x k ) = x 11 x 22 : : : x k k : n ! n ! : : : n ! k n +n +:::+n =n 1 2

X

1

2

k

Zbrajamo po svim k -tercima cijelih brojeva n1 n2 : : : + nk = n . DOKAZ . Tvrdnja slijedi neposredno iz Teorema 1.

:::

nk

> 0 takvim da je n1 + n2 +

38

3. UVOD U KOMBINATORIKU

Primjedba 2. Za k = 2 dobivamo upravo binomni teorem: n (x 1 + x 2 ) =

=

=

X

n1 +n2 n

X

n! n1 n2 x1 x2 =n n1 !n2 !

= eliminiramo n2 =

n1 =0 n

n! n n;n x 1x 1 n1 !(n ; n1 )! 1 2

n ; n1 ]

= preimenujmo varijablu n1

u k]

X n k k=0

k

x 1 x 2n;k :

Primjedba 3. Multinomna formula mozˇ e se zapisati vrlo sazˇ eto i pregledno s pomoc´u tzv. multiindeksa. Uvedimo oznaku x := (x 1 x 2 : : : x k ) , zatim multiindeks α := (α1 α2 : : : αk ) 2 Nk0 , duljina multiindeksa jα j := α1 + α2 + : : : + αk , α α α x α := x 1 1 x 2 2 : : : x k k , multinomni koeficijent αn := α !α n!!:::α ! . Onda po multino1 2 k mnom teoremu vrijedi: n α n (x 1 + x 2 + : : : + x k ) = x : α

;

X 

jα j=n

gdje se zbraja po svim multiindksima α = (α1 : : : αk ) duljine n . Multinomna formula bit c´e nam vazˇ no sredstvo u rjesˇavanju kombinatoricˇ kih problema s pomoc´u funkcija izvodnica, vidi nizˇ e. (vidi Primjer 3.6.3).

Primjer 2. (a) Kvadrat trinoma jednak je: 2

(x 1 + x 2 + x 3 )













2 2 2 = x 21 + x 22 + x2 2,0,0 0,2,0 0,0,2 3 2 2 2 + x1x2 + x1x3 + x x 1,1,0 1,0,1 0,1,1 2 3 2! 2 2! 2 2! 2 = x1 + x2 + x 2!0!0! 0!2!0! 0!0!2! 3 2! 2! 2! + x x + x x + x x 1!1!0! 1 2 1!0!1! 1 3 0!1!1! 2 3 2 2 2 = x 1 + x 2 + x 3 + 2x 1 x 2 + 2x 1 x 3 + 2x 2 x 3 :













; 

Zadan je polinom (a + b + c)3 trec´eg stupnja u varijablama a b c . Koeficijent 3! = 3. uz a2 c u njegovu razvoju jednak je 2 30 1 = 2!0!1!

(b )

Koeficijent uz a3 b2 c23 u razvoju polinoma (a + b + c)28 jednak je 2827262524 = = 982 800 . 62

(c)

28! 3!2!23!

;



28 3 2 23 =

Primjer 3. Koliko se razliˇcitih rijeˇci moˇze napraviti od slova rijeˇci MATEMATIKA? Rjesˇenje. Ovdje je rijeˇc je o permutacijama s ponavljanjem. Imamo 3 slova A , po 2 slova M i T , po jedno M , I , K ; ukupno 10 slova. Broj razliˇcitih rijeˇci je 10! 3!2!2! = 151200 .

3.3. PERMUTACIJE , VARIJACIJE

39

I KOMBINACIJE S PONAVLJANJEM

Primjer 4. U koliko permutacija rijeˇci MATEMATIKA samoglasnici dolaze abecednim redom? Rjesˇenje. Na raspolaganju imamo 10 mjesta za upis slova rijeˇci MATEMATIKA Odaberimo 5 mjesta na koje c´ emo upisati samoglasnike abecednim redom AAAEI i potom na preostala mjesta ispermutirajmo slova MMTTK. To se moˇze na ukupno 10 5! cina. 5 2!2! = 7560 naˇ Ili pak broj svih permutacija rijeˇci MATEMATIKA podijelimo s brojem svih per10! mutacija samoglasnika AAAEI. Rezultat je opet 3!2!2! : 5! 3! = 7560 .

; 



Primjer 5. U ravnini je zadana cjelobrojna koordinatna mrezˇ a i tocˇka T (m n) , gdje je m n 2 N . Koliko ima razlicˇ itih stepenastih uzlaznih staza od tocˇ ke O(0 0) do T duzˇ koordinatne mrezˇ e? Svakom stazom pomicˇ emo se za jedno mjesto u desno (D) ili za jedno mjesto gore (G). T(3,2)

T(3,2)

0

D G

D G

D

0

D

G

D

D G

Sl. 3.2. Stepenaste staze od O do T .

Svaka takva staza od tocˇ ke O do T mozˇ e se jednoznacˇ no opisati slijedom poput DGDDG : : : , u kojem se nalazi tocˇ no m koraka D i tocˇ no n koraka G , da bi se dosˇlo do tocˇ ke T . Na pr. za T (3 2) od O do T mozˇ e se doc´i stazama DDDGG , DGDGD , GGDDD , GDDDG itd. (vidi Sliku 3.2.). Prema tome ukupan broj staza jednak je broju poredanih (m + n) -teraca sastav+n)! . Na pr. za m = 3 , n = 2 je ljenih od m D -ova i n G -ova. On je jednak (mn!m! 5! trazˇ eni broj staza jednak 3!2! = 10 .

B. Varijacije s ponavljanjem.

fa1

Definicija. Varijacija s ponavljanjem k -tog reda n -cˇlanog skupa An

=

an g je svaki poredani k -terac elemenata iz An . Bilo koji element u k tercu mozˇ e se i ponavljati. Na pr. za A2 = f0 1g i k = 3 imamo ovih osam varijacija s ponavljanjem trec´eg reda: (0 0 0) , (0 0 1) , (0 1 0) , (0 1 1) , (1 0 0) , (1 0 1) , (1 1 0) , (1 1 1) . Zapisali smo ih u leksikografskom poretku. :::

Teorem 4. Poredanih k -teraca n -cˇ lanog skupa ima ukupno nk .

DOKAZ . Skup svih varijacija s ponavljanjem jednak je An  : : :  An (Kartezijev produkt k skupova). Prema Teoremu 3.1.2 vrijedi jAn  : : :  An j = jAn jk = nk .

40

3. UVOD U KOMBINATORIKU

Primjer 6. Koliko je mogu´cih ishoda bacanja 8 razliˇcitih kocaka? (Pretpostavimo da su razliˇcitih veliˇcina ili razliˇcitih boja.) Rjesˇenje. Za svaku kocku imamo 6 mogu´cih ishoda bacanja, a za 8 kocaka 68 = 1679616 , odnosno rijeˇc je o varijacijama s ponavljanjem 6 elemenata, 8 -og reda. Primjer 7. Na koliko se naˇcina moˇze 5 vo´caka: 1 jabuka, 1 kruˇska, 1 breskva, 1 naranˇca, 1 marelica, podijeliti izmedu 30 ljudi ako: a) svaki cˇ ovjek moˇze dobiti najviˇse jednu vo´cku, b) svaki cˇ ovjek moˇze dobiti bilo koji broj vo´caka? Rjesˇenje. Imamo varijacije, i to: a) varijacije s ponavljanjem 30 elemenata, reda 5 , 30 29 28 27 26 = 17100720 , b) varijacije bez ponavljanja 30 elemenata, reda 5 , 305 = 24300000 . Primjer 8. Na koliko naˇcina se moˇze 12 putnika ukrcati u a) 4 vagona, b) kao pod a), ali uz uvjet da su u 1. vagonu toˇcno 3 putnika, c) kao pod a), ali uz uvjet da su u svakom vagonu toˇcno 3 putnika? Rjesˇenje. a) Svaki putnik ima 4 mogu´cnosti za odabir vagona. Ukupno 412  16:78 106 . b) Odaberimo 3 od 12 putnika koji idu u 1. vagon. Od preostalih 9 putnika svaki 9 cina. ima 3 mogu´cnosti za odabir vagona. To je ukupno 12 3 3 = 4330260 naˇ c) Odaberimo 3 od 12 putnika koji idu u 1. vagon, pa 3 od preostalih 9 putnika koji idu u 2. vagon, i 3 od preostalih 6 koji idu u 3. vagon. Preostala 3 idu u 4. 9 6 3 vagon. Ukupno 12 3 3 3 3 = 369600 .

; 

; ; ; ; 

Primjer 9. Na koliko naˇcina moˇze kralj iz donjeg lijevog polja sˇahovske ploˇce, do´ci u gornje desno polje, ako smije i´ci: a) samo desno i samo gore, b) desno, gore i dijagonalno (gore+desno)? Rjesˇenje. a) Svaki put iz donjeg lijevog u gornje desno polje sˇ ahovske ploˇce moˇze se prikazati 14! nizom od 7 slova G i 7 slova D, a takvih nizova ima 7!7! = 3432 . b) Prebrojimo sve puteve koji sadrˇze toˇcno k dijagonalnih pomaka. Osim tih k dijagonalnih pomaka, kralj se mora joˇs (7 ; k) puta pomaknuti desno i (7 ; k) puta gore. Ukupno to je k + (7 ; k) + (7 ; k) = 14 ; k poteza od kojih je k , ! 7 ; k , 7 ; k istih, odnosno k!(7(;14k);!(k7); ze biti najmanje 0 , a k)! . Buduc´i da k moˇ najviˇse 7 , rjeˇsenje je 7 X k=0

(14 ; k)! k! ( 7 ; k) ! ( 7 ; k) !

=

48639:

Primjer 10. Koliko na sˇahovskoj ploˇci ima pravokutnika?

3.3. PERMUTACIJE , VARIJACIJE

41

I KOMBINACIJE S PONAVLJANJEM

Rjesˇenje. Od devet vodoravnih linija biramo dvije za gornji i donji rub pravokutnika, i od devet vertikalnih dvije za lijevi i desni rub pravokutnika. Zato na sˇahovskoj ploˇci ima 92 92 = 1296 pravokutnika.

; ; 

Primjer 11. (a) Na koliko se naˇcina moˇze 8 topova iste boje razmjestiti na sˇ ahovsku ploˇcu tako da se nikoja dva ne napadaju (topovi se medusobno napadaju ako se nalaze u istome redu ili istome stupcu). Rjesˇenje. Na 82 naˇcina moˇzemo izabrati mjesto za prvog topa. Drugi ne smije biti u retku niti u stupcu gdje se nalazi prvi top, pa za njega preostaje 72 mjesta (izbor jednog od preostalih 7 redaka i jednog od preostalih 7 stupaca). Sliˇcno, za tre´ceg preostaje 62 mjesta, za cˇ etvrtog 52 , za petog 42 , za sˇ estog 32 , za sedmog 22 i za osmog 1 mjesto. Topove medusobno ne razlikujemo pa rezultat treba podijeliti sa 8! . Ukupno se mogu razmjestiti na 8!8!8! = 8! naˇcina.

C. Kombinacije s ponavljanjem.

Definicija. Neka je An = fa1 : : : an g . Kombinacija s ponavljanjem k -tog reda n -cˇ lanog skupa An je bilo koji neporedani k -terac elemenata iz An . Cˇ lanovi k -teraca mogu se ponavljati. Broj kombinacija s ponavljanjem jednak je broju nacˇ ina biranja k predmeta od ukupno n , s koliko god ponavljanja istog predmeta u kombinaciji. Primjer 12. Neka je A4 = fa1 a2 a3 a4 g i k = 6 . “Neporedan” sˇesterac mozˇ emo interpretirati kao blok (tzv. multiskup), na pr. a1 a1 a2 a4 a4 a4 . “Neporedanost” znacˇ i da sˇesterac poistovjec´ujemo (identificiramo) sa a4 a1 a4 a4 a2 a1 , tj. vazˇ an nam je samo broj pojavljivanja elemenata, a ne i njihov poredak. Primijetimo da multiskup a1 a1 a2 a4 a4 a4 , tj. “skup” u kojem su moguc´a visˇestruka pojavljivanja nekog elementa (kratnici, multipli), nije isto sˇto i pripadni skup a1 a2 a4 .

f

g

Zgodno je kombinacije s ponavljanjem zapisivati i ovako. Skupimo iste elemente u kombinaciji u grupe, jedan za drugim, i odijelimo grupe vertikalnom crtom. U gornjem primjeru je pripadni sˇesterac moguc´e zapisati kao a1 a1 j a2 j j a4 a4 a4 Element a3 se ne pojavljuje, pa njemu odgovara prazna grupa, odijeljena uzastopnim pregradama.

je

Teorem 5. Broj kombinacija s ponavljanjem k -tog reda n -cˇ lanog skupa jednak

n + k ; 1 k

:

DOKAZ . Svaki element skupa An u kombinaciji s ponavljanjem oznacˇ it c´emo zvjezdicom. Da bismo znali tocˇ no o kojem elementu je rijecˇ , koristit c´emo i pregrade. Odaberimo dakle k zvjezdica i n ; 1 pregradu (ukupno k + n ; 1 mjesta), izmedu

42

3. UVOD U KOMBINATORIKU

kojih c´emo stavljati zvjezdice. Na pr. kombinacija a1 a1 a2 a4 a4 a4 je jednoznacˇ no odredena sa

  j  jj   

Broj ponavljanja zvjezdica odijeljenih susjednim pregradama odgovara kratnosti pripadnog elementa. Razmjesˇtaj k zvjezdica na bilo koje od k + (n ; 1) mjesta (preostala mjesta su za pregrade) mozˇ e se obaviti na k+nk;1 nacˇ ina, jer toliko ima k -cˇ lanih podskupova (k + n ; 1) -cˇ lanog skupa.

;

;



 ; ;

U gornjem primjeru imamo ukupno 4+66;1 = 96 = 93 = 918273 = 84 kombinacija sˇestog reda skupa od cˇ etiri elementa. Primjedba 4. Sasvim drugacˇiji dokaz Teorema 5 bit c´e dan u Primjeru 3.5.7 s pomoc´u metode funkcije izvodnice. Svakoj kombinaciji s ponavljanjem k -tog reda odgovara poredani k -terac cijelih brojeva x 1 : : : x n > 0 , za koji je x i jednak broju pojavljivanja elementa ai u kombinaciji, i = 1 : : : n , i vrijedi x 1 + : : : + x n = k: () Na gornjem primjeru je x 1 = 2 , x 2 = 1 , x 3 = 0 , x 4 = 3 . Obratno, svakom poredanom k -tercu (x 1 : : : x n ) 2 Nn0 za koju je ispunjen uvjet () odgovara neporedani k -terac u kojem se ai pojavljuje x i puta. Prema tome, broj kombinacija s ponavljanjem reda k skupa od n elemenata jednak je broju cjelobrojnih, nenegativnih rjesˇenja jednadzˇ be () , doticˇ no broju poredanih k -teraca (x 1 : : : x n ) 2 Nn0 za koje vrijedi () .

Primjer 13. Koliko cjelobrojnih rjeˇsenja ima nejednakost x1 + x2 + x3