Matematička analiza 1

Prijava

HrvatskihrEnglishen

Pristupačnost

Veličina slova:A A

Izgled stranice Uobičajen izgled Jednostavni izgled stranice

Kontrast stranice: Normalno Visoki kontrast Inverzni visoki kontrast

Očisti sve

Bilješke uz Matematičku analizu 1

Poštovani i dragi studenti,

dobro došli na Sveučilište u Zagrebu, na FER.

Ovim ćemo bilješkama dati popis najvažnijih oznaka, pojmova i rezultata u kolegiju Matematička analiza 1. Može poslužiti za ponavljanje gradiva, ali ne može zamijeniti skriptu.

Držat ćemo se naše skripte Matematička analiza 1, koju je pripremila grupa auktora na Zavodu za primijenjenu matematiku (ZPM) FER-a. PDF-ovi pojedinih poglavlja dostupni su Vam na ovoj mrežnoj stranici.

Za matematiku (kao i za bilo koju drugu struku) je veoma bitno da pojmovi budu jasni. Također, dobro je za svaki matematički rezultat (lemu, propoziciju ili teorem) pred očima imati neki vrlo jednostavan primjer, koji možete i sami smisliti. Štoviše, opći se rezultati najbolje razumiju kroz konkretne primjere.

Isto vrijedi i za opće pojmove, kojih će već u ovom kolegiju biti ne mali broj.

Pogledajte popis tvrdnji čiji se dokazi ispituju na ispitima iz Matan 1 akademske godine 2020/21. Taj popis možete naći i na mrežnoj stranici predmeta pod Materijali $\rightarrow$ SKRIPTA.

Sadržaj:

Skupovi, matematička logika i realni brojevi
Kompleksni brojevi
Funkcije i relacije
Uvod u kombinatoriku

1. Skupovi, matematička logika i realni brojevi [PDF]

1.1 Uvod

Najvažniji skupovi u ovom kolegiju su

skup prirodnih brojeva $\mathbb N=\{1,2,3,\dots\}$
skup cijelih brojeva $\mathbb Z=\{\dots,-2,-1,0,1,2,\dots\}$
skup racionalnih brojeva $\mathbb Q=\{a/b:a,b\in\mathbb Z,\,\,b\ne0\}$
skup realnih brojeva $\mathbb R$ (koji nastaje `popunjavanjem' skupa racionalnih brojeva $\mathbb Q$)
skup kompleksnih brojeva $\mathbb C=\{z=x+iy:x,y\in\mathbb R\}$, gdje je $i$ imaginarna jedinica, koja se množi sama sa sobom ovako: $i^2=-1$.

Realni brojevi koji nisu racionalni, zovu se iracionalni brojevi. Takvi su na primjer $\sqrt2$, $\sqrt3$, $\pi$, $e$ i mnogi drugi.

1.2 Skupovi i operacije sa skupovima

Na skupovima definiramo operacije unije $\cup$ i presijeka $\cap$ skupova. Presijek $A\cap B$ dvaju skupova $A$ i $B$ sadrži sve elemente koji su u $A$ i u $B$ (tj. koji su zajednički za oba skupa). Unija $A\cup B$ dvaju skupova $A$ i $B$ sadrži sve elemente koji su u $A$ ili $B$.

Kao što vidimo, presijeku $A\cap B$ odgovara veznik i, a uniji $A\cup B$ odgovara veznik ili.

Komplement skupa $A$ sadržanog u nekom zadanom univerzalnom skupu $U$ označujemo s $\overline A=U\setminus A$. Ovdje smo sa $\setminus$ označili razliku skupova (ili skupovnu razliku). Skup $\overline A=U\setminus A$ sadrži sve elemente iz $U$ koji nisu u $A$, tj. one koji su izvan skupa $A$.

Važan nam je tzv. prazan skup $\emptyset$, koji ne sadrži niti jedan element.

Broj elemenata konačnog skupa $A$ zovemo kardinalnim brojem tog skupa. Za broj elemenata skupa $A$ koristimo oznaku $|A|$.

Za dva skupa $A$ i $B$ kažemo da su disjunktni, ako nemaju zajedničkih elemenata, tj. ako im je presijek prazan: $A\cap B=\emptyset$. Pogledajte Vježbe 1.1, 1.2 i 1.3.

Za više od dva skupa (tj. za skupove $A$, $B$, $C$, \dots) kažemo da čine disjunktnu familiju skupova, ako su svaka dva od njih međusobno disjunktna.

Kartezijev umnožak $A\times B$ dvaju nepraznih skupova $A$ i $B$ sastoji se od svih poredanih dvojaca $(a,b)$ elemenata iz prvog i drugog skupa. Kao što vidimo, predak elemenata nam je bitan. Pogledajte Primjer 1.1. Nije teško vidjeti da je kardinalni broj (tj. broj elemenata) skupa $A\times B$ jednak umnošku kardinalnih brojeva od $A$ i $B$. Ovo je sadržaj poznatog produktnog pravila u kombinatorici. To je ujedno i razlog za oznaku $A\times B$ Kartezijeva produkta skupova.

Osnovna svojstva skupovnih operacija navedena su u Teoremu 1.2.1. Obratite pozornost osobito na zakone distribucije i na De Morganove formule.

Pogledajte pitanja u Odjeljku 1.8.1.

1.3 Uvod u matematičku logiku i pravila zaključivanja

1.3.1 Sudovi

Sud $A$ je tvrdnja koja je ili istinita ili lažna. Pišemo $A\equiv T$ ili $A\equiv F$, gdje su nam $T$ (istina) i $F$ (laž) dvije moguće istintosne vrijednosti.

Na skupu sudova imamo operacije konjunkcije $\land$ i disjunkcije $\lor$. Sud $A\land B$ je istinit jedino ako su oba suda $A$ i $B$ istinita. Sud $A\lor B$ je lažan jedino ako su oba suda $A$ i $B$ lažna.

Sud $A\land B$ čitamo kao $A$ i $B$.
Sud $A\lor B$ čitamo kao $A$ ili $B$.

Također imamo i operaciju negiranja suda $A$: negirani sud $\lnot A$ je istinit onda i samo onda ako je sud $A$ lažan, i obratno.

Za dva zadana suda $A$ i $B$ definiramo implikaciju $A\Rightarrow B$. Taj sud (po definiciji) lažan jedino ako je sud $A$ istinit, a $B$ lažan.

Implikaciju $A\Rightarrow B$ čitamo i ovako:

$A$ implicira $B$
iz $A$ slijedi $B$
$A$ je dovoljan uvjet za $B$
$B$ je nuždan uvjet za $A$.

Pogledajte vježbe 1.4, 1.5, 1.6, kao i Teorem 1.3.1. Obratite pozornost na zakone distribucije za sudove, kao i na De Morganove formule, koji su potpuno analogni kao i za skupove. To pokazuje da se operacije presijeka, unije i komplementa za skupove, ponašaju isto kao i operacije konjunkcije, disjunkcije i negacije za sudove.

Konjunkcija $\land$ i disjunkcija $\lor$ sudova $A$ i $B$ se računa za dva zadna suda, pa kažemo da su to binarne operacije (tj. imaju dvije varijable, sudove $A$ i $B$).

S druge strane, negacija $\lnot$ je unarna operacija, jer ima samo jednu varijablu: sud $A$.

Slično tome, za skupove su presijek $\cap$ i unija binarne operacije, a komplementiranje skupa, unutar zadanog univerzalnog skupa, je unarna operacija.

Nije teško zamisliti i složenije sudne forme (ili Booleove funkcije), koje imaju bilo koji konačan broj sudova kao varijable, povezane osnovnim sudnim operacijama. Na primjer, sudna forma $A\Rightarrow (B\land\lnot C)$ ima tri (sudne) varijable.

Sudne forme koje su uvijek istinite (neovisno o istinitostnim vrijednostima pojedinih sudnih varijabala) zovu se tautologije. Na primjer, sudna forma $\lnot(A\lor B)\Leftrightarrow(\lnot A\lor \lnot B)$ je tautologija, a to je upravo jedna od dviju De Morganovih formula za sudove, tj. $\lnot(A\lor B)\equiv(\lnot A\lor \lnot B)$.

Često se koristi ova tautologija, koja se zove pravilo kontrapozicije: $$ (A\Rightarrow B)\Leftrightarrow (\lnot B\Rightarrow\lnot A), $$ ili u kraćem zapisu, $$\lnot(A\Rightarrow B)\equiv(\lnot B\Rightarrow\lnot A).$$

Pozor! Općenito nije istina da je $\lnot(A\Rightarrow B)\equiv(\lnot A\Rightarrow\lnot B)$.

Još neke poznate tautologije su navedne u Propoziciji 1. Ne morate ih pamtiti, ali je korisno razumjeti njihov sadržaj na nekim konkretnim primjerima sudova $A$ i $B$, koje si možete sami odabrati.

Dodatak možete preskočiti.

Pogledajte pitanja u Odjeljku 1.8.1.

1.3.2 Predikati i kvantifikator

Predikat je izjava $P(x)$, koja za svaki $x$ iz nekog nepraznog skupa $U$ postaje sud. Prema tome, predikat $P(x)$ možemo gledati i kao skup sudova $P(a)$, za sve $a\in U$. Taj skup može biti i beskonačan, ako je univerzalni skup $U$ beskonačan.

Svakom predikatu $P(x)$ možemo pridružiti sud $$ \forall x\, P(x) $$ (čitaj: za svaki $x$ vrijedi $P(x)$). Taj sud je po definiciji istinit onda i samo onda ako su pojedini sudovi $P(a)$ istiniti, za sve $a\in U$.

Znak $\forall$ zove s univerzalnim kvantifikatorom, a dolazi od obrnutog slova A, od njemačkog Alle (svi).

Svakom predikatu $P(x)$ pridružujemo još jedan sud: $$ \exists x\, P(x) $$ (čitaj: postoji $x$ za vrijedi $P(x)$). Taj sud je po definiciji istinit onda i samo onda ako postoji barem jedan $a\in U$ takav da je sud $P(a)$ istinit.

Znak $\exists$ zove s egzistencijalnim kvantifikatorom, a dolazi od obrnutog slova E, od njemačkog Existieren (postojati).

Dobro je pogledati primjer kada je $U=\{a_1,a_2\}$, tako da predikat $P(x)$ nad dvočlanim skupom možemo gledati kao skup od dva suda: $\{P(a_1),P(a_2)\}$. Onda je očevidno $$ \forall x\, P(x)\equiv P(a_1)\land P(a_2),\quad\exists x\, P(x)\equiv P(a_1)\lor P(a_2) $$ Prema tome, sud $\forall x\, P(x)$ je zapravo konjunkcija sudova $P(x)$ za $x\in U$, dok je sud $\forall x\, P(x)$ zapravo disjunkcija sudova $P(x)$ za $x\in U$.

Radi ovoga onda nije iznenađujuće da vrijede De Morganove formule za općenite predikate: $$ \lnot\forall x\, P(x)\equiv \exists x\,\lnot P(x),\quad \lnot\exists x\, P(x)\equiv \forall x\,\lnot P(x) $$ Pogledajte Primjere 1.6, 1.7, 1.8, 1.9, kao i Vježbe 1.7 i 1.8. Pogledajte pitanja u Odjeljku 1.8.3.

1.3.3 Matematički dokazi i metode dokazivanja

Pogledajte Lemu 1 i Lemu 3. Osobito je zanimljiva Lema 3, koja potječe iz Antičke Grčke. U njoj je metodom kontradikcije dokazano da je broj $\sqrt 2$ iracionalan, tj. ne može se napisati kao kvocijent cijelih brojeva.

Dodatak možete preskočiti.

Pogledajte pitanja u Odjeljku 1.8.1.

1.4 Prirodni brojevi. Matematička indukcija

U skripti pažljivo pročitajte o načelu matematičke indukcije ili Peanovo načelo. To se načelo može vrlo kratko formulirati ovako:

Neka je $A$ neki podskup skupa prirodnih brojeva $\mathbb N$, koji ima ova dva svojstva:

$1\in A$
ako je $n\in A$, onda je $n+1\in A$.

Onda je $A=\mathbb N$.

Načelo matematičke indukcije je 'očevidno': budući da je $1\in A$ , onda iz drugog svojstva slijedi da je $2\in A$. Budući da je $2\in A$, onda opet zbog drugog svojstva slijedi $3\in A$. Itd. Dakle doista je $A=\mathbb N$.

Pogledajte Primjere 1.10 i 1.11.

Oba dodatka možete preskočiti, kao i Primjer 1.12.

Pogledajte pitanja u Odjeljku 1.8.4.

1.5 Cijeli brojevi

Svaki student bi trebao dobro znati što to znači podijeliti neki cijeli broj sa zadanim prirodnim brojem. Također bi trebalo razmijeti što je kvocijent, a što ostatak prilikom dijeljenja. O tome govori Propozicija 2 (Stavak o dijeljenju cijelih brojeva). Pogledajte i sliku 1.11.

Sasvim kratko, da bismo podijelili cijeli broj $m$ s prirodnim brojem $n$, to znači pronaći cijeli broj $q$ (djelomični kvocijent) i broj $r\in\{0,1,\dots,n-1\}$ (ostatak pri dijeljenju $m$ s $n$), tako da vrijedi $$m=qn+r.$$

Brojevi $q$ i $r$ su u gornjem prikazu određeni jednoznačno. Broj $q$ je najveći cijeli broj takav da je $qn\le m$, a broj $r$ se definira kao udaljenost od $qn$ do $n$, tj. $r=n-qn$.

Dokaz možete preskočiti. Kad se brojevi $n$, $qn$ i $r$ nacrtaju na pravcu, tvrdnja odmah postaje očevidna.

Pogledajte Primjer 1.13.

Svaki bi trebao razmijeti pojam prostog broja (ili prim broja): to su oni prirodni brojevi veći ili jednaki $2$, koji imaju samo trivijalne djelitelje, tj. broj $1$ i njega samog. Prirodni brojevi koji nisu prosti zovu se složeni brojevi.

Na primjer, broj $6$ nije prost broj, jer ima netrivijalan djelitelj $2$ (i $3$). Drugim riječim, $6$ je složen broj.

Broj $7$ je prost broj, jer ima samo trivijalne djelitelje: $1$ i $7$.

Dobro je znati nekoliko prvih prostih brojeva:

$2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, ...

Koji je prvi sljedeći prim-broj iza $19$?

Već je Euklid znao da prostih brojeva ima beskonačno mnogo. Živio je s četvrtog na treće stoljeće prije Krista.

Student neka pogleda definiciju najmanjeg zajedničkog višekratnika dvaju (ili više) prirodnih brojeva, kao i njihove najveće zajedničke mjere.

Za dva prirodna broja kažemo da su relativno prosta, ako je jedini njihov zajednički djelitelj broj $1$.

Također pogledajte Teorem 1.5.1 o jednoznačnom rastavu prirodnih brojeva na proste djelitelje, jer će nam on biti važan u kombinatorici.

1.6 Racionalni brojevi

Svaki student mora znati kako se zbrajaju razlomci, u kojima su $a,b,c,d$ racionalni brojevi, takvi da su $b$ i $d$ različiti od nula: $$ \frac ab+\frac cd=\frac{ad+bc}{bd}. $$ Isto pravilo zbrajanja razlomaka vrijedi i za realne brojeve $a,b,c,d$, pa čak i za kompleksne brojeve.

Podsjetimo još i na pravilo računanja kvocijenta dvaju razlomaka: $$\frac{\,\,\frac ab\,\,}{\,\,\frac cd\,\,}=\frac{ad}{bc}.$$

Uz koje uvjete na brojeve $a,b,c,d$ vrijedi ova jednakost? Naravno, brojevi $b$ i $d$ moraju biti različiti od nula, da bi razlomci $a/b$ i $c/d$ bili dobro definirani. A da bi kvocijent tih razlomaka bio dobro definiran, mora biti $c$ različit od nula. Razlomak na desnoj strani jednakosti je dobro definiran, jer uz dobivene uvjete je nazivnik $bc$ različit od nula.

Pogledajte pitanja u Odjeljku 1.8.1.

1.7 Realni brojevi

1.7.1 Osnovno o realnim brojevima

Pogledajte definiciju supremuma i infimuma zadanog podskupa realnog pravca. Supremum skupa je njegova najmanja gornja međa, a infimum je najveća dolnja međa.

Također pogledajte definiciju maksimuma i minimuma (ne moraju postojati za bilo koji skup). Ako je supremum skupa u njemu sadržan, onda ga zovemo maksimumom skupa.

Slično tome, ako je infimum skupa u njemu sadržan, onda ga zovemo minimumom.

Najjednostavnije primjere nam daju skupovi koji su otvoreni i omeđeni intervali: oni imaju infimum i supremum, ali nemaju minimum i maksimum.

S druge strane, zatovreni omeđeni intervali na pravcu imaju minimum i maksimum.

Dodatak s opisom Cantorovog svojstva možete preskočiti.

Svaki bi trebao znati definiciju apsolutne vrijednosti $|x|$ realnog broja $x$: to je maksimum od brojeva $x$ i $-x$, tj. $$|x|=\max\{x,-x\}.$$ Svaki bi trebao znati kako izgleda graf te funkcije: za $x\geq 0$ je $|x|=x$ a za $x>0$ je $|x|=-x$. Prema tome, graf te funkcije ima u ishodištu šiljak, na kojem se dodiruju zrake $y=x$ (za $x\ge 0$) i $y=-x$ (za $x< 0$).

Pogledajte i definiciju dolnjeg cijelog dijela $\lfloor x\rfloor$ realnog broja $x$. To je najveći cijeli broj koji je manji ili jednak $x$. Na primjer, $\lfloor 3.14\rfloor=3$, a $\lfloor -3.14\rfloor=-4$. Jasno, $\lfloor 3\rfloor=3$. Na engleskom se vrijednost $\lfloor x\rfloor$ zove pod od $x$ (na engleskom, floor of $x$).

Dodatak možete preskočiti.

Realne brojeve koji su $\ge0$ zovemo nenegativnim brojevima. A koje realan broj $>0$, kažemo da je pozitivan. Ako je relan broj $>0$, kažemo da je negativan. Naravno, ova se definicija prenosi na racionalne i cijele brojeve.

1.7.2 Algebarski i transcendentni brojevi

Ovaj odjeljak možete preskočiti.

1.8 Zadatci za vježbu

Ovaj odjeljak nikako nemojte preskočiti.

U njemu su na kraju dana i rješenja nekih od zadataka. Prije nego ih pogledate, jako preporučujemo da učinite napor da ih svakako pokušate riješiti samostalno. Najprije treba razumjeti što se uopće traži u zadatku.

1.9 Povijesne crtice

Ovaj odjeljak možete preskočiti. Ali znamo da ga nećete preskočiti.

2. Kompleksni brojevi [PDF]

2.1 Operacije s kompleksnim brojevima

Svaki kompleksni broj možemo prikazati u Guassovoj (ili kompleksnoj) ravnini kao $z=x+iy$, gdje su $x$ i $y$ realni brojevi (realni i imaginarni dio kompleksnog broja $z$), a $i$ je imaginarna jedinica, za koju po definiciji stavljamo $i^2=-1$.

Kompleksni broj nula shvaćamo kao $0=0+i0$. Dva kompleksna broja su jednaka onda i samo onda ako imaju jednake realne dijelove i jednake imaginarne dijelove.

Kompleksnom broju $z$ pridružujemo njemu konjugirano kompleksni broj $\overline z=x-iy$, u kojem smo samo promijenili predznak imaginarnog dijela od $z$. Konjugiranje je zapravo zrcaljenje kompleksnog broja u odnosu na $x$-os.

Treba dobro znati zbrajanje, množenje i dijeljenje kompleksnih brojeva. Kod dijeljenja kompleksnih brojeva, brojnik i nazivnik množimo s konjugirano kompleksnim nazivnikom (naravno, nazivnik mora biti različit od nula).

Konjugiranje kompleksnih brojeva se dobro ponaša s obzirom na operacije zbrajanja, množenja i dijeljenja: konjugiranjem zbroja dvaju kompleksnih brojeva dobiva se isti rezultat kao kad zbrojimo oba kompleksna broja konjugirana: $\overline{z_1+z_2}=\overline z_1+\overline z_2$. Slično za množenje i dijeljenje:

$$\overline{z_1z_2}=\overline z_1\overline z_2,\quad \overline{z_1/z_2}=\overline z_1/\overline z_2.$$

Apsolutna vrijednost $|z|$ kompleksnog broja $z$ definira se kao njena udaljenost od ishodišta. Kvadrat apsolutne vrijednosti kompleksnog broja jednaka je umnošku tog kompleksnog broja s njemu konjugiranim:

$$|z|^2=z\cdot \overline z.$$

Jedno korisno svojstvo je da je apsolutna vrijednost umnoška kompleksnih brojeva jednaka umnošku apsolutnih vrijednosti (i slično za kvocijent):
$$
|z_1\cdot z_2|=|z_1|\cdot|z_2|.
$$

Pogledajte Primjere 2.1, 2.2, 2.3, 2.4.

Dodatak (s težištem trokuta) možete preskočiti.

Svaki bi trebao znati sadržaj Guassova osnovnog teorema algebre, vidi Teorem 2.1.1.

2.2 Trigonometrijski oblik kompleksnog broja

Svaki kompleksni broj $z$ određen je sa sljedeća dva podatka, koje zovemo njegovim polarnim koordinatama:

udaljenošću od $z$ do ishodišta (u oznaci $r$); naravno, $r=|z|$
priklonim kutom $\varphi$ između pozitivnog dijela $x$-osi i broja $z$ (gledanog kao radius-vektor s početkom u ishodištu), pri čemu pretpostavljamo da je /(z\ne0/).

Pozitivni dio $x$-osi zove se polarna os. Kut smatramo da je pozitivan, ako je smjer rotacije od polarne osi do $z$ pozitivan (tj. suprotan od smjera kazaljke na satu). Taj kut zovemo i argumentom kompleksnog broja $z$. Argument kompleksnog broja određen je jednoznačno do na cjelobrojni višekaratnik punog kuta. Drugim riječima, ako je $\varphi$ argument kompleksnog broja $z$, onda je i $\varphi+2k\pi$ argument od $z$ za bilo koji cijeli broj $k$.

Na primjer, kutove $\varphi_1=-\pi/2$ i $\varphi_1=3\pi/2$ poistovjećujemo, jer je $\varphi_1-\varphi_2=-2\pi$. Kutu $\varphi_1=-\pi/2$ odgovaraju kompleksni brojevi na pozitivnom dijelu imaginarne osi (tj. pozitivnom dijelu $y$-osi), kao i kutu $\varphi_1=-3\pi/2$.

Pogledajte Primjere 2.12 i 2.13.

Kompleksni broj $z$ se može ovako zapisati u polarnim koordinatama $(r,\varphi)$:
$$
z=r(\cos\varphi+i\sin\varphi).
$$
Tu jednakost zovemo i trigonometrijskim oblikom kompleksnog broja $z$. Euler je uveo vrlo zgodnu oznaku za gornji izraz u okrugloj zagradi:
$$
e^{i\varphi}=\cos\varphi+i\sin\varphi
$$
Tu jednakost zovemo Eulerovom formulom (opravdanje za tu oznaku daje nam teorija funkcija kompleksne varijable, u što se ovdje ne upuštamo). Na taj način, bilo koji kompleksni broj $z$ možemo zapisati ovako (Eulerov zapis kompleksnog broja):
$$
z=r\,e^{i\varphi}.
$$

Pogledajte Primjere 2.14, 2.15 i 2.16.

Krivulje $r=const.$ za bilo koju pozitivnu realnu konstantu predstavljaju koncentrične kružnice sa središtem u ishodištu. Krivulje $\varphi=const.$ za bilo koju realnu konstantu predstavljaju zrake iz ishodišta. Radi toga koordinatna mreže u polarnom sustavu nalikuje na paukovu mrežu oko ishodišta.

Dodatak možete preskočiti.

Argument umnoška kompleksnih brojeva jednak zbroju argumenata oba kompleksna broja (do na cjelobrojni višakratnik punog kuta, tj. od $2\pi$ radijana ):
$$
\mbox{arg}(z_1\cdot z_2)=\mbox{arg}(z_1)+\mbox{arg}(z_1)
$$
Slično, argument njihova kvocijenta jednak je razlici argumenata: $\mbox{arg}(z_1/ z_2)=\mbox{arg}(z_1)-\mbox{arg}(z_1)$, pri čemu se lijeva i desna strana smiju razlikovati za cjelobrojni višekratnik od $2\pi$.

2.3 Eksponencijalni ili Eulerov zapis kompleksnog broja

Kompleksni brojevi se u trigonometrijskom obliku množe vrlo jednostavno:
$$
r_1\,e^{i\varphi_1}\cdot r_2\,e^{i\varphi_2}=r_1r_2\,e^{i(\varphi_1+\varphi_2)}.
$$
Odatle odmah slijedi Moivreova formula, indukcijom po prirodnom broju $n$: $(e^{i\varphi})^n=e^{i(n\varphi})$, tj.
$$
(\cos\varphi+i\sin\varphi)^n=\cos (n\varphi)+i\sin(n\varphi).
$$
Pogledajte Primjere 2.17, 2.19, 2.20.

2.4 Korjenovanje kompleksnih brojeva

Pogledajte formulu (2.18), tj. (2.19), kao i Primjere 2.22, 2.23, 2.25(b).

Pogledajte i zadatke u Odjeljku 2.5.2.

3. Funkcije i relacije [PDF]

3.1 Funkcije

Svaki mora dobro razumijeti pojam funkcije $f:X\to Y$. Funkcija $f$, to su tri stvari:

polazni skup $X$ (neprazan),
dolazni skup $Y$ (neprazan), i
propis kojim svakom elementu $x\in X$ pridružujemo točno jedan (bilo koji) element $y\in Y$.

Pišemo

$$x\mapsto y\quad\mbox{ili}\quad y=f(x).$$

Polazni skup $X$ zove se domena funkcije $f$.

Skup $Im(f)=\{f(x)\in Y:x\in Z\}$ zove se slika funkcije $f$. Kao što vidimo, to je podskup skupa $Y$ koji se sastoji od svih onih $y\in Y$ koji su pogođeni s nekim $x\in X$, tj. za koje postoji barem jedan $x$ takav da je $y=f(x)$. Slika funkcije $f$ se nerijetko označuje i s $f(X)$.

Za funkciju $f:X\to Y$ kažemo da je injekcija, ako za svaka dva $x_1,x_2\in X$ vrijedi da, ako su $x_1$ i $x_2$ različiti, onda su i $f(x_1)$ i $f(x_2)$ različiti.

Kraće, funkcija $f:X\to Y$ je injekcija ako vrijedi (tj. istinit je) ovaj sud:

$$(\forall x_1,x_2\in X)(x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2)).$$

Obratom po kontrapoziciji, funkcija $f:X\to Y$ je injekcija ako vrijedi

$$(\forall x_1,x_2\in X)(f(x_1)= f(x_2)\Rightarrow x_1= x_2).$$

Upravo ovo najčešće koristimo u provjeri je li neka funkcija injekcija. Krećemo od jednakosti $f(x_1)= f(x_2)$, te ako iz toga računom uspijemo zaključiti da je $x_1= x_2$, onda je funkcija $f$ injekcija.

Pretpostavimo da je skup $X$ konačan, tj. da ima konačno mnogo elemenata. Ako je funkcija $f:X\to Y$ injekcija, onda njena slika $f(X)$ ima isti broj elemenata kao i skup $X$. Ta je tvrdnja očevidna.

Za funkciju $f:X\to Y$ kažemo da je surjekcija, ako vrijedi da za svaki $y\in Y$ postoji (barem jedan) $x\in X$, takav da je $y=f(x)$. Drugim riječima, funkcija $f:X\to Y$ je surjekcija ako joj je slika jednaka cijelom dolaznom skupu $Y$, tj.

$$Im(f)=Y,\quad\mbox{tj.}\quad f(X)=Y.$$

Za funkciju $f:X\to Y$ kažemo da je bijekcija, ako je injekcija u surjekcija.

Zovemo ju i obostrano jednoznačnim preslikavanjem. Naime, surjektivnosti za svaki $y\in Y$ postoji $x\in X$ takav da se $x$ preslika funkcijom $f$ u $y$. Zbog injektivnosti funkcije $f$ je taj $x$ određen s $y$ jednoznačno. Na taj način je onda za svaku bijektivnu funkciju $f:X\to Y$ dobro definirana njoj inverzna funkcija

$$f^{-1}: Y\to X$$

definirana ovako:
$$f^{-1}(y)=x\quad\Leftrightarrow\quad y=f(x).$$

Drugim riječima, vrijednost inverzne funkcije $f^{-1}$ na bilo kojem $y$ je onaj $x$ koji se u njega preslika funkcijom $f$. Naravno, inverzna funkcija $f^{-1}: Y\to X$ je također bijekcija.

Ako su skupovi $X$ i $Y$ konačni, tj. imaju konačno mnogo elemenata, te ako postoji bijekcija između njih, onda oni imaju isti broj elemenata. Štoviše, dva konačna skupa $X$ i $Y$ imaju isti broj elemenata onda i samo onda

Na primjer, ako $X$ ima dva elementa, a $Y$ tri elementa, onda funkcija $f:X\to Y$ nikako ne može biti surjekcija, jer je njena slika najviše dvočlana.

Slično tome, ako $X$ ima tri elementa, a $Y$ dva elementa, onda funkcija $f:X\to Y$ nikako ne može biti injekcija, jer je njena slika najviše dvočlana.

Funkcija $id_X:X\to X$ (primijetite da su polazni i dolazni skup isti) definirana sa $id_X(x)=x$ (tj. funkcija $id_X$ ostavlja sve elemente $x$ na miru), zove se identiteta na $X$.

Osnovna operacija s dvije ulančane funkcije $f:X\to Y$ i $g:Y\to Z$ (ulačane preko zajedničkog skupa $Y$) je kompozicija $g\circ f:X\to Z$. Kompozicija $g\circ f:X\to Z$ dviju ulančanih funkcija $f$ i $g$ je funkcija koja se definira ovako:

$$(g\circ f)(x)=g\left (f(x)\right).$$

Ako je funkcija $f:X\to Y$ bijekcija, onda je očevidno

$$f^{-1}\circ f=id_X,\quad f\circ f ^{-1}=id_Y.$$

Opća funkcija se u literaturi često zove i preslikavanjem (engl. mapping).

U literaturi se injektivna funkcija često zove i $1$ - $1$ funkcijom (engl. one-one function).

Surjetkivna funkcija se često zove funkcija koja je na (engl. onto function). Kad se kaže da neka funkcija preslikava skup $X$ na skup $Y$, onda to znači da je surjektivna.

Komponiranje dviju ulačanih funkcija općenito nije komutativno, tj. $f\circ g\neq g\circ f$. Međutim, za svake tri ulančane funkcije $f$, $g$ i $h$ (tj. $f:X\to Y$, $g:Y\to Z$, $h: Z\to W$), onda vrijedi zakon asocijativnosti za njihovo komponiranje:

$$h\circ(g\circ f)=(h\circ g)\circ f.$$

3.2 Relacije

U ovom odjeljku su od velike važnosti sljedeći pojmovi, koji se tiču zadanog nepraznog skupa $A$, ne nužno konačnog (tj. ne nužno s konačno mnogo elemenata).

Binarna relacija $\rho$ na skupu $A$ (definirana kao bilo koji neprazan podskup $\rho$ skupa $A\times A$. Ako je $(x,y)\rho$, onda pišemo $x\,\rho\,y$ i čitamo "$x$ je u relaciji s $y$".

Pogledajmo neke specijalne tipove relacija:

Refleksivna relacija $\rho$ na skupu $A$ po definiciji mora sadržavati $(x,x)$ za sve $x\in A$, tj. za sve $x\in A$ mora vrijediti $x\,\rho\,x$. Drugim riječima, refleksivna relacija mora sadržavati dijagonalu $\{(x,x)\: x\in A\}$ skupa $A\times A$.
Za binarnu relaciju $\rho$ na skupu $A$ kažemo da je simetrična, ako za sve $x,y\in A$ vrijedi da iz $x\,\rho\,y$ slijedi $y\,\rho\,x$.
Za binarnu relaciju $\rho$ na skupu $A$ kažemo da je tranzitivna, ako za sve $x,y,z\in A$ vrijedi da iz $x\,\rho\,y$ i $y\,\rho\,z$ slijedi $x\,\rho\,z$.

Za binarnu relaciju $\rho$ na skupu $A$ kažemo da je relacija ekvivalencije, ako je

refleksivna,
simetrična i
tranzitivna.

U tom slučaju za svaki zadani element $x\in A$ imamo definiran odgovarajući njegov razred ekvivalencije (engl. equivalence class)

$$[x]:=\{y\in A:y\,\rho\, x\}.$$

Bilo koji odabran element $y\in[x]$ zovemo reprezentatnom razreda $[x]$. Naravno, za svaki takav reprezentant vrijedi $[y]=[x]$.

Ako je $\rho$ relacija ekvivalencije na skupu $A$, onda ona definira particiju skupa $A$. Drugim riječime, za svaka dva elementa $x_1,x_2\in A$ su razredi $[x_1]$ i $[x_2]$ ili jednaki, ili disjunktni. Drugim riječima, relacijom ekvivalencije je dobiven disjunktni rastav skupa $A$ na odgovarajuće razrede ekvivalencije.

Skup svih razreda ekvivalencije koji odgovaraju relaciji ekvialencije $\rho$ na skupu $A$, zove se kvocijentni skup. Oznaka kvocijentnog skupa je $X/\rho$. Elementi kvocijentnog skupa su razredi ekvivalencije.

Obratno, ako je na skupu $A$ zadana neka njegova particija (tj. rastav na međusobno disjunktne podskupove), onda je tim rastavom jednoznačno definirana relacija ekvivalencije $\rho$ na skupu $A$, kojoj odgovara zadana particija skupu $A$.

Drugim riječima, zadati relaciju ekvivalencije na skupu $A$, isto je što i zadati odgovarajuću particiju na tom skupu.

Za relaciju $\rho$ na skupu $A$ kažemo da je antisimetrična, ako za sve $x,y\in A$ vrijedi da iz pretpostavke $x\,\rho\,y$ i $y\,\rho\,x$ slijedi $x=y$. Na primjer, relacija "manje ili jednako", tj. $\leq$, na skupu realnih brojeva je antisimetrična na $\leq$.

Za relaciju $\rho$ na skupu $A$ kažemo da je relacija djelomičnog poretka (ili parcijalnog poretka), ako vrijedi da je

refleksivna,
antisimetrična i
tranzitivna.

Na primjer, ako je zadan bilo koji skup $X$, te ako je $\mathcal P(X)$ skup svih njegovih podskupova (uključujući i prazan skup i cijeli skup $X$), onda je relacija $\subseteq$ relacija parcijalnog poretka.

Skup $\mathcal P(X)$ zovemo partitivnim skupom od $X$. U uporabi je još jedna oznaka za partitivni skup skupa $X$:

$$2^X.$$

Razlog je taj, što ako skup $X$ ima $n$ elemenata, onda njegov partitivni skup ima $2^n$ elemenata. To ćemo vidjeti u sljedećem poglavlju (Kombinatorika).

3.3 Ekvipotentnost skupova

Za dva (neprazna) skupa $X$ i $Y$ kažemo da su ekvipotentni, ako postoji bijekcija $f:X\to Y$. Naravno, ako postoji bijekcija $f:X\to Y$, onda su $X$ i $Y$ također ekvipotentni. Ekvipotentnost dvaju skupova intuitivno znači njihovu "jednakobrojnost".

Ako su dva skupa ekvipotentna, onda kažemo da imaju isti kardinalni broj (tj. imaju isti "broj elemenata").

Za skup $X$ kažemo da je prebrojiv, ako je ekvipotentan skupu $\mathbb N$ prirodnih brojeva. Drugim riječima, skup $X$ je prebrojiv ako postoji bijekcija $f:X\to\mathbb N$, ili bijekcija $f:\mathbb N\to X$.

Skup prirodnih brojeva $\mathbb N$ je očevidno prebrojiv, jer je funkcija $id:\mathbb N\to\mathbb N$ (tj. identiteta) bijekcija.

Kardinalni broj skupa prirodnih brojeva zove se alef nula, s oznakom $\aleph_0$. Naziv alef potječe od prvog slova hebrejskog pisma, $\aleph$.

Jasno je da konačan skup $X$ ne može biti ekvipotentan svojem pravom podskupu $Y$ (tj. podskupu od $X$ koji je od njega različit). Na primjer, tročlani skup $X$ ne mo\e biti ekvipotentan svojem dvočlanom podskupu.

Međutim kod beskonačnih skupova to se može lako dogoditi da je skup ekvipotentan nekom svojem pravom podskupu.

Na primjer, skupovi $\mathbb N=\{1,2,3,\dots\}$ i $\mathbb N+1=\{2,3,4,\dots\}$ su ekvipotentni, jer je funkcija $f:\mathbb N\to\mathbb N+1$, zadana sa $f(n)=n+1$ ("pomak" za broj jedan), bijekcija. Primijetite da je $\mathbb N+1=\{2,3,4,\dots\}$ pravi podskup od $\mathbb N$ (razlikuju se za element $1$.)

Skupovi $\mathbb N=\{1,2,3,\dots\}$ i njegov pravi podskup $\mathbb 2N=\{2,4,6,\dots\}$ (skup parnih brojeva) su ekvipotentni, jer je funkcija $f:\mathbb N\to\mathbb 2N$, zadana sa $f(n)=2n$, bijekcija. Na sličan se način vidi da je skup $\mathbb N$ ekvipotentan sa skupom neparnih brojeva $\mathbb 2N-1=\{1,3,5,\dots\}$

Nije teško vidjeti da je skup cijelih brojeva $\mathbb Z$ također prebrojiv, tj. ekvipotentan s $\mathbb N$. Bijektivnu funkciju $f:\mathbb Z\to \mathbb N$ konstruiramo tako da negativne cijele brojeve preslikamo bijektivno u neparne prirodne brojeve, a pozitivne brojeve i nulu bijektivno u parne prirodne brojeve.

Dosta je nevjerojatno da je i skup $\mathbb Q$ svih racionalnih brojeva također prebrojiv.

Pokazuje se da skup svih realnih brojeva $\mathbb R$ nije prebrojiv, tj. ne postoji bijekcija s njega na skup prirodnih brojeva $\mathbb N$. To je sadržaj poznatog Cantorova teorema (nazvanog po Georgu Cantoru).

Kardinalni broj skupa realnih brojeva $\mathbb R$ zove se kontinuum, s oznakom $c$. Prema tome, imamo za sada dva beskonačna kardinalna broja, alef nula i kontinuum, za koje vrijedi $\aleph_0<c$. Beskonačnih kardinalnih brojeva ima jako mnogo (toliko mnogo da velika većina njih nema niti svoja imena niti svoje oznake).

Iracionalni brojevi se definiraju kao realni brojevi koji nisu racionalni, tj. kao elementi skupa $\mathbb R\setminus\mathbb Q$. Takvi su na primjer $\sqrt2,\, \sqrt3, \,\pi,\, e$ i mnogi drugi. Budući da je skup $\mathbb R$ neprebrojiv (kardinaliteta $c$, kontinuum), a $\mathbb Q$ prebrojiv (kardinaliteta $\aleph_0$, onda je iz toga lako zaključiti da je skup iracionalnih brojeva $\mathbb R$ neprebrojiv (kardinaliteta $c$ neprebrojiv, kardinaliteta $c$. Prema tome, iracionalnih brojeva ima bitno više od racionalnih brojeva. To se dade naslutiti iz sljedećeg: svaki racionalni broj u decimalnom zapisu ima periodički prikaz (i obratno), dok iracionalni brojevi u decimalnom zapisu nemaju periodički prikaz.

Dosta je nevjerojatno da skup kompleksnih brojeva $\mathbb C$ ima kardinalni broj $c$, tj. postoji bijekcija s $\mathbb C$ na $\mathbb R$. Primijetite da je $\mathbb R$ pravi podskup od $\mathbb C$.

Budući da skup kompleksnih brojeva možemo gledati kao ravninu $\mathbb R\times\mathbb R=\mathbb R^2$ , onda postoji i bijekcija s ravnine $\mathbb R^2$ na pravac $\mathbb R^2$. Durgim riječima, skupovi točaka ravnine i pravca su "jednakobrojni". Iznenađujuće, zar ne?

4. Uvod u kombinatoriku [PDF]

Pogledati osnovna pravila prebrojavnja: pravilo zbrajanja, pravilo komplementa i pravilo bijekcije.

4.1 Produktno pravilo

U ovom odjeljku najvažniji je Teorem 4.1.2, koji nam daje broj svih funkcija iz zadanog $n$-članog skupa u zadani $m$-člani skupa. Taj broj jednak je $m^n$.

Korolar 4.1.3 nam daje broj svih poredanih $n$-teraca sastavljenih od nula i jedinica. Taj broj jednak je $2^n$.

To je ujedno i broj svih podskupova $n$-članog skupa (uključujući i prazan podskup). Vidi Teorem 4.1.4.

Skup svih podskupova $n$-članog skupa $X$ (uključujući i prazan podskup) zovemo partitivnim skupom skupa $X$. Označujemo ga s $2^X$, jer je broj njegovih elemenata jednak $2^n$.

Dodatak možete preskočiti.

Propozicija 2 daje nam broj djelitelja zadanog prirodnog broja $n$. Da bismo taj broj izračunali, broj $n$ treba rastaviti na proste faktore.

Drugi dodatak također možete preskočiti.

4.2 Varijacije i kombinacije bez ponavljanja

4.2.1. Varijacije bez ponavljanja

Varijacije bez ponavljanja su poredani $k$-terci zadanog $n$-članog skupa, gdje se elementi ne ponavljaju (tj. svi su različiti). Naravno, mora biti $k\leq n$, jer u suprotnom nema niti jednog poredanog $k$-terca. Njihov broj jednak je

$$n(n-1)\dots (n-k+1).$$

Ovo je padajući umnožak točno $k$ uzastopnih prirodnih brojeva, počevši od $n$.

Posebno, broj permutacija (premjestba) $n$-članog skupa jednak je $n!$ (tj. umnošku svih prirodnih brojeva od $1$ do $n$). Vidi Teorem 4.2.1.

Broj svih injektivnih funkcija iz $k$-članog skupa u $n$-člani skup, gdje je $k\leq n$, iznosi

$$n(n-1)\dots (n-k+1).$$

Vidi Teorem 4.2.2.

Posebno, broj bijektivnih funkcija iz $n$-članog skupa u $n$-člani skup iznosi $n!$.

Bijektivne funkcije iz $n$-članog skupa u samog sebe zovu se također permutacije (premjestbe) tog skupa.

4.2.2 Kombinacije bez ponavljanja

Ovdje prebrojavamo $k$-člane podskupove $n$-članog skupa (naravno, mora biti $k\leq n$). Njihov broj jednak je

$$\binom nk:=\frac{n(n-1)\dots (n-k+1)}{k!}.$$

Prirodan broj $\binom nk$ zove se binomni koeficijent.

Definirmo također $\binom n0=1$. Kao što vidimo $\binom n1=n$. Broj

$$\binom n2=\frac{n(n-1)}{2!}$$

predstavlja broj dvočlanih podskupova $n$-članog skupa, itd.

Iz definicije binomnog koeficijenta vidimo da je

$$\binom nk:=\frac{n!}{k!(n-k)!}.$$

Odatle odmah slijedi svojstvo simetrije: $\binom nk=\binom n{n-k}$.

Za zadani prirodan broj $n$ imamo ukupno $n+1$ binomnih koeficijenata:

$$\binom n0,\,\binom n1,\,\binom n2,\,\dots,\binom nn.$$

Dodatak na str. 21 možete preskočiti.

Pogledajte značajno svojstvo binomnih koeficijenata u Propoziciji 3. Ta propozicija kaže da je zbroj dvaju uzastopnih binomnih koeficijenata (u odnosu na $k$) opet binomni koeficijent, točnije,

$$\binom n{k-1}+\binom nk=\binom{n+1}k,$$

gdje je $k\le n$. Iz ove se formule dobiva Pascalov trokut binomnih koeficijenata $\binom nk$ (navedenim redcima odgovaraju vrijednosti $n=0,1,2,3,4$):

1 1

1 2 1

1 3 3 1

1 4 6 4 1

....

Na primjer, $\binom30=1$, $\binom31=3$, $\binom32=3$, $\binom33=1$. Zbroj bilo koja dva uzasotopna binomna koeficijenta u nekom redku jednak je odgovarajućem binomnom koeficijentu u sljedećem redku.

Iznimno je važna binomna formula:

$$(1+x)^n=\binom n0+\binom n1x+\binom n2x^2+\dots+\binom nnx^n.$$

koja vrijedi za svaki realan broj $x$, pa i za svaki kompleksan broj $z$ (umjesto $x$). Pogledajte Teorem 4.2.4. Treba znati i opći oblik binomne formule, koja se lako dobiva iz gornjeg:

$$(x+y)^n=\binom n0x^n+\binom n1x^{n-1}y+\binom n2x^{n-2}y^2+\dots+\binom nny^n.$$

Pritom su $x$ i $y$ bilo koji realni (ili čak kompleksni) brojevi. Na primjer, iz Pascalova trokuta odmah vidimo da je

\begin{gathered}(x+y)^2=x^2+2xy+y^2\\(x+y)^3=x^3+3x^2y+3xy^2+y^3 \\(x+y)^4=x^4+4x^3y+6x^2y^2+4xy^3+y^4.\end{gathered}

Vrijednosti binomnih koeficijenata $\binom nk$ u ovisnosti o $k$ najprije rastu, sve do $k$ koji je najbliži $n/2$, a zatim vrijednosti $\binom nk$ padaju, sve do $k=n$. Vrijednosti binomnih koeficijenata $\binom nk$ u ovisnosti o $k$ imaju zvonoliku razdiobu.

Dodatak na str. 27 možete preskočiti.

4.3 Varijacije i kombinacije s ponavljanjem

Kod varijacija nam je poredak elemenata bitan, dok kod kombinacija nije. Pod varijacije uključujemo i permutacije.

4.3.1 Permutacije s ponavljanjem

Permutacija s ponavljanjem reda $n$ zadanog $k$-članog skupa $\{a_1,\dots,a_k\}$ je bilo koji poredani $n$-terac elemenata iz tog skupa, u kojem se element $a_i$ pojavljuje $n_i$ puta, pri čemu je $n=n_1+\dots+n_k$. Broj permutacija s ponavljanjem jednak je generaliziranom binomnom koeficijentu (ili multinomnom koeficijentu)

$$\binom n{n_1,\dots,n_k}=\frac{n!}{n_1!\dots n_k!}.$$

Vidi Teorem 4.3.1. U slučaju dvočlanog skupa $\{a_1,a_2\}$, gdje se u permutaciji element $a_1$ pojavljuje $n_1=r$ puta, a $a_2$ se pojavljuje $n_2=n-r$ puta, broj permutacija s ponavljanjem postaje uobičajen binomni koeficijent:

$$\binom n{r,\,n-r}=\frac{n!}{r!(n-r)!}=\binom nr.$$

Iz Teorema 4.3.1 odmah slijedi multinomni teorem, koji predstavlja poopćenje binomnog teorema:

$$(x_1+\dots+x_k)^n=\sum_{\quad n_1,\dots,n_k\ge0\phantom{aa} \\ \phantom{a}n_1+\dots+n_k=n}\frac{n!}{n_1!\dots n_k!}x_1^{n_1}\dots x_k^{n_k}.$$

Pritom na desnoj strani zbrajamo po svim poredanim $k$-tercima nenegativnih cijelih brojeva $n_1,\dots,n_k$ takvih da je $n_1+\dots+n_k=n$. Pogledajte Teorem 4.3.2.

Na primjer, u razvoju multinoma $(a+b+c)^4$ je koeficijent uz $a^2bc$ jednak $\frac{4!}{(2,1,1)}=\frac{4!}{2!1!1!}=\frac{24}2=12$. Koeficijent uz $b^2c^2$ jednak je $\frac{4!}{(0,2,2)}=\frac{4!}{0!2!2!}=\frac{24}4=6$.

Koliko se riječi može složiti od slova KAPA, zadržavajući kratnost svakog slova? Slovo A se pojavljuje dvaput, a slova K i P jednom, pa je traženi broj jednak $\frac{4!}{2!1!1!}=12$. Od slova MAMA možemo složiti [est riječi: $\frac{4!}{2!2!}=\frac{24}4=6$. To su (u leksikografskom poretku) AAMM, AMAM, AMMA, MAAM, MAMA, MMAA.

Koliki je koeficijent uz $x^3$ u multinomu $(1+x+x^2)^4$? Iznos $x^3$ možemo u razvoju multinom dobiti na dva načina: tako da dvaput uzmemo $1$, po jednom $x$ i $x^2$, ili jednom uzemo $1$, triput $x$ i nijednom $x^2$. Traženi koeficijent iznosi $\frac{4!}{2!1!1!}+\frac{4!}{1!3!0!}=12+4=16$.

4.3.2 Varijacije s ponavljanjem

Varijacija s ponavljanjem je bilo koji $k$-terac elemenata iz zadanog $n$-članog skupa. Pritom se elementi $k$-terca smiju ponavljati.

Svih $k$-teraca elemenata iz $n$-članog skupa ima ukupno $n^k$.

To odmah dobivamo iz Produktnog pravila, jer na svako od $k$ mjesta smijemo staviti bilo koji od $n$ elemenata.

Primijetite da svaki $k$-terac elemenata iz zadanog $n$-članog skupa možemo poistovjetiti s funkcijom $f$ iz $k$-članog skupa $\{1,\dots,k\}$ u zadani $n$-člani skup. Znamo od prije da tih funkcija ima $n^k$. Podsjetimo se, $f(1)$ poprima bilo koju od $n$, vrijednosti,... , $f(k)$ također, pa tvrdnja slijedi iz Produktnog pravila.

Na koliko načina može pet muškaraca i tri žene ući u dva vagona tramvaja? Prvo rješenje. Smještavamo zapravo osam osoba u vagone. Svaka osoba može ući u bilo koji od dva vagona, pa je traženi broj jednak $2^8$. Drugo rješenje. Svako smještavanje možemo (prema Pravilu bijekcije) gledati i kao funkciju iz osmeročlanog skupa u dvočlani, pa je broj funkcija jednak $2^8$. Treće rješenje. Pet muškaraca možemo u dva vagona na $2^5$ načina, a tri žene na $2^3$ načina, pa je prema Produktnom pravilu ukupan broj smještavanja jednak $2^52^3=2^8$. Četvrti rješenje. Poredajmo sve osobe od prve do osme. Gledamo poredane osmerce brojeva $1$ ili $2$, ovisno o tome u koji je vagon ušla odgovarajuća osoba. Takvih osmeraca prema Produktnom pravilu ima $2^8$.

4.3.3 Kombinacije s ponavljanjem

Kombinacija s ponavljanjem je bilo koji neporedani $k$-terac elemenata iz $n$-članog skupa, koji se smiju ponavljati. Njihov broj jednak je

$$\binom{n+k-1}k.$$

To je sadržaj Teorema 4.3.4. Pogledajte dokaz. Drugi dokaz (u dodatku) možete preskočiti.

Ako u kombinaciji s ponavljanjem imamo kratnost $i$-tog elementa $n$-članog skupa jednaku $x_i$, gdje je $x_i\geq0$, onda je

$$x_1+\dots+x_n=k.$$

Prema tome, broj rješenja ove jednadžbe u nenegativnim cijelim brojevima $(x_1,\dots,x_n)$ jednak je $\binom{n+k-1}k$. Upravo je na ovaj (algebarski) način najbolje gledati odgovarajuće kombinatoričke zadaće.

Koliko rješenja u nenegativnim cijelim brojevima ima jednadžba $x_1+x_2+x_3+x_4=10$? Taj broj iznosi $\binom{4+10-1}{10}=\binom{13}{10}=\binom{13}{3}=\frac{13\cdot12\cdot11}6=286$.

Na koliko načina se deset jednakih lutaka može podijeliti među četiri djevojčice? Ako u $(x_1,\dots,x_4)$ sa $x_i$ označimo broj lutaka koje će dobiti dogovarajuća djevojčica, onda je $x_1+x_2+x_3+x_4=10$. Prema prethodnom zadatku je taj broj jednak $\binom{4+10-1}{10}=286$.

Na koliko se načina među četiri djevojčice može podijeliti deset jednakih lutaka i šest jabuka? Lutke možemo podijeliti na $\binom{4+10-1}{10}=286$ načina. Ako sa $(y_1,\dots,y_4)$ označimo broj dobivenih jabuka za svaku od djevojčica, onda je $x_1+x_2+x_3+x_4=6$. Broj razdioba jabuka iznosi $\binom{4+6-1}{6}=\binom 93=\frac{9\cdot8\cdot7}6=84$. Prema Produktnom pravilu je ukupan broj razdioba lutaka i jabuka jednak $286\cdot84=24\,024$.

Na koliko načina se deset jednakih lutaka može podijeliti među četiri djevojčice, tako da svaka dobije barem jednu lutku? Podijelimo odmah svakoj od djevojčica po jednu lutku. Onda nam je preostalo 6 lutaka za podjelu. Ako sa $(x_1,\dots,x_4)$ označimo broj lutaka koje će dobiti dogovarajuća djevojčica, onda je $x_1+x_2+x_3+x_4=6$. Taj broj jednak je $\binom{4+6-1}{6}=84$.

Koliko pribrojnika ima razvoj multinoma $(a+b+c)^8$? Članovi razvoja su oblika $\binom{8!}{n_1!n_2!n_3!}a^{n_1}b^{n_2}c^{n_3}$. Zbrajamo ih po svim trojcima nenegativnih cijelih brojeva $(n_1,n_2,n_3)$ takvih da je $n_1+n_2+n_3=8$. Prema tome, traženi broj pribrojnika jednak je broju rješenja ove jednadžbe, tj. $\binom{3+8-1}8=\binom {10}8=\binom{10}2=45$.

Pogledajte također i primjere 4.58 i 4.59 u Skripti.

4.4 Formula uključivanja i isključivanja

4.4.1 Sylvesterova formula

Formulu uključivanja i isključivanja (ili Sylvesterovu formulu) radimo samo za slučajeve $n=2$ i $n=3$:

$$|A\cup B|=|A|+|B|-|A\cap B|,\\|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|,$$

gdje su $A,\, B,\, C$ bilo koja tri konačna skupa, a s $|A|$ (itd.) smo označili broj elemenata (ili kardinalni broj) skupa $A$. Prva jednakost je očevidna, jer u zbroju $|A|+|B|$ su elementi iz presijeka $A\cap B$ uračunati dvaput, pa zato treba oduzeti $|A\cap B|$.

Slično se može pokazati i druga jednakost. Na primjer, elementi iz $A\cap B\cap C$ su u prva tri člana uračunati triput, u sljedeća tri člana su oduzeti triput (jer na primjer $A\cap B$ sadrži skup $A\cap B\cap C$, itd.), pa zato treba još dodati $|A\cap B\cap C|$.

Ako se skupovi $A,\, B,\, C$ nalaze u konačnom skupu $X$, onda iz De Morganove formule odmah dobivamo

$$|\overline A\cap \overline B|=|X|-|A|-|B|+|A\cap B|,\\|\overline A\cap \overline B\cap \overline C|=|X|-|A|-|B|-|C|+|A\cap B|+|A\cap C|+|B\cap C|-|A\cap B\cap C|,$$

gdje je $\overline A=X\setminus A$, itd.

Doista, prva jednakost slijedi odmah iz De Morganove formule $\overline A\cap \overline B=\overline{A\cup B}=X\setminus(A\cup B)$, jer je onda $|\overline A\cap \overline B|=|X|-|A\cup B|$, a slično i druga.

Pogledajte Primjere 4.60-4.62 u Skripti.

Preostali dio Odjeljka 4.4.1 ne radimo, kao niti Odjeljak 4.4.2 (Eulerova funkcija).

Dodatak

Brzina konvergencije sljedova i funkcija, oznake veliki $O$ i mali $o$

Darko Žubrinić