Matematika 3 - 10.2 Osnovni princip prebrojavanja

Na početku...

Brojenje, prebrojavanje i razvrstavanje dio je našega svakidašnjeg života. Sjemenke, žitarice, tjesteninu i sl. razvrstavamo u posude; na računalu razvrstavamo dokumente u mape sa zajedničim sadržajem kako bismo ih lakše pronašli. U školi se razvrstavaju novoupisani učenici u razredne odjele, a političari se dijele u interesne skupine po stranačkim opredjeljenjima.

Razne vrste sjemenki u vrećicama — Razne vrste sjemenki

Elemente organiziramo u određene skupine koje imaju neka zajednička svojstva. Sve te skupine, masu, mnoštvo, grupe nazivamo jednim imenom skupovi. Skupovi se sastoje od članova ili elemenata. Za te pojmove u matematici ne postoji stroga definicija nego se oni intuitivno podrazumijevaju.

Kombinatorika

Kombinatorika je grana matematike koja se bavi prebrojavanjem elemenata konačnih skupova, odnosno prebrojavanjem načina da se elementi konačnih skupova poredaju, rasporede, izaberu.

Zanimljivost

Elemente kombinatorike susrećemo još kod starih civilizacija (Indijaca, Kineza, Arapa), koji su već tada djelomično poznavali tablicu binomnih koeficijenata. Pretpostavlja se da su indijski matematičari proučavali kombinacije u vezi s primjenom u poeziji.

Tri su poznata matematičara zaslužna za uvođenje kombinatorike tijekom 17. stoljeća u Europi. To su: Paul Guldin, Jakob Bernoulli te Gottfried Leibniz koji i uvodi naziv kombinatorika.

U kombinatorici razlikujemo tri osnovna načina kako se elementi konačnih skupova redaju, raspoređuju ili izabiru: permutacije, kombinacije i varijacije.

Prije nego što se upustimo u prebrojavanje elemenata, ponovimo osnovna svojstva skupova i računske radnje sa skupovima.

Ponovimo

Zadavanje skupova.

Skupove možemo zadavati na više načina. Povežite primjer skupa s načinom kako je zadan.

$A = \{naranča, mandarina, grejp\}$
$B = \{n : n \leq 25, n = 2 k, k \in N\}$
$C = \{mjeseci s trideset dana\}$

null

Skupove označujemo velikim slovima, a njihove elemente malim, npr. $x$ je element skupa $A (x \in A) .$ Uz oznaku za pripadnost skupu, imamo još nekoliko oznaka kojima se koristimo u računskim radnjama sa skupovima.

Pridružite oznaku njezinu značenju.

komplement skupa $A$	$\emptyset$
$x$ nije element skupa $A$	$x \notin A$
$A$ je podskup skupa $B$	$\bar{A}$
kardinalni broj skupa $A$	$A \subseteq B$
prazan skup	$card (A)$

null

Definirajte računske radnje sa skupovima.

$A \cup B =$	$\{x : x \in A ili x \in B\}$
$A \cap B =$	$\{x : x \in A i x \in B\}$
$A \ B =$	$\{x : x \in A i x \notin B\}$

null

Ponovimo oznake koje smo naučili u prethodnoj jedinici.
Broj

n!

čitamo:

n

kojim

računamo umnožak prvih

n

Koji skup brojeva?

brojeva.

Definiramo

0! =

Faktorijele upotrebljavamo u računanju brojeva oblika

(\begin{array}{l} n \\ r \end{array}),

gdje su

n, r \in N_{0} .

Broj oblika

(\begin{array}{l} n \\ r \end{array})

nazivamo

n i r

vrijedi da je od ta dva broja uvijek veći broj

Koji je broj veći,

n

ili

r

ili

mogu biti jednaki. Prema definiciji je

(\begin{array}{l} n \\ 0 \end{array}) =

null

Jednakost skupova

Dva su skupa jednaka ako je svaki element prvog skupa ujedno element drugog skupa, i obrnuto.

$A = B \Leftrightarrow (x \in A i x \in B)$

Zadatak 1.

Jesu li skupovi $A = \{1, 3, 5, . . .\} i B = \{n : n = 2 k + 1, k \in N\}$ jednaki?

null

Jesu li skupovi $A = \{3, 6, 9, 12, . . .\} i B = \{svi višekratnici broja 3\}$ jednaki?

null

Jesu li skupovi brojeva $N i Z$ jednaki?

null

Jesu li skupovi $A = \{skup svih paralelograma s jednakim stranicama\}$ i $B = \{skup svih rombova\}$ jednaki?

null

Načelo zbroja

Dva su osnovna načela prebrojavanja kojima možemo riješiti veliki broj kombinatornih problema: načelo zbroja i načelo umnoška.

Primjer 1.

Krenuli ste po doručak. Još se premišljate hoćete li uzeti sendvič, burek ili kroasan. U najbližoj pekari danas nude: četiri vrste sendviča (šunku i sir, pršut i sir, mozzarelu s rajčicom, piletinu sa salatom), dvije vrste bureka (sa sirom i s jabukama) te tri vrste kroasana (punjen marmeladom, punjen čokoladom i prazan). Koliko imate doručaka na raspolaganju? Odnosno, na koliko načina možete za doručak odabrati jedno od ponuđenoga?

Pekarnica

Imamo tri vrste proizvoda (tri skupa) i za svaki imamo više izbora (elementi skupa). Očito je da možete odabrati jedan od četiri sendviča ili dva bureka ili tri kroasana, dakle $4 + 2 + 3 = 9 .$

Doručak možete odabrati na devet načina.

Načelo zbroja

Neka promatrana dva konačna skupa, $A$ i $B$ nemaju zajedničkih elemenata $(A \cap B = \emptyset) .$ Tada je ukupan broj elemenata unije $A \cup B$ jednak zbroju elemenata skupa $A$ i skupa $B .$

$card (A \cup B) = card (A) + card (B)$

Koliko smo skupova, koji nemaju zajedničkih elemenata, imali u 1. primjeru?

null

Koliko elemenata ima svaki skup?

Skup sendviča
Skup kroasana
Skup bureka

null

Zadatak 2.

Roditelji su vam za odličan uspjeh na kraju školske godine obećali novi mobitel. Pozitivno motivirani krenuli ste u potragu za mogućim modelima (naravno da ćete proći s odličnim uspjehom, pa tko bi propustio prigodu). U uži izbor ušla su tri modela jednog od najpoznatijih proizvođača i dva modela drugoga najpoznatijeg proizvođača mobitela. Zatim još dva modela proizvođača mobitela koji već imate i jedan model koji je trenutačno na vrhu najprodavanijih mobitela. Znate da će vjerojatno i cijena biti presudna za odabir mobitela, ali ste ipak sastavili svoj popis. Koliko mobitela imaju roditelji na raspolaganju s obzirom na vaš popis, odnosno na koliko načina mogu odabrati mobitel za vas?

Imamo $4$ skupa. S obzirom na to da skupovi nemaju zajedničkih elemenata, rješenje je: $3 + 2 + 2 + 1 = 8 .$

Načelo umnoška

Primjer 2.

Marta se priprema za školu. Izvadila je iz ormara tri majice, dvoje hlača i jednu suknju. Razmišlja također koje cipele, od dva para koja su u užem izboru, izabrati za današnju kombinaciju. Pomognite Marti u odabiru odjevne kombinacije. Na koliko je načina to moguće učiniti?

Zamijetimo da možemo kombinirati tri majice s tri donja odjevna predmeta (dvoje hlača ili jedna suknja) te dva para cipela.

Pogledajte kako s pomoću stabla možemo dobiti sve odjevne kombinacije i koliko ih ukupno ima.

Načelo umnoška

Ako skup $A$ ima $m$ elemenata, a skup $B n$ elemenata te $A$ i $B$ nemaju zajedničkih elemenata (neovisni su jedan o drugome), tada je broj mogućih kombinacija elemenata prvog i drugog skupa jednak $m \cdot n .$

Zadatak 3.

Antonio u cvjećarnici kupuje cvijet za prijateljicu koja mu je pomogla u pripremi za test iz matematike. Prodavačica mu je ponudila četiri vrste lončanica i ukrasni lončić za cvijeće u dvjema bojama. Kada se odluči za cvijet i lončić, dar može zapakirati u celofan koji se nudi u trima bojama. Na koliko načina Antonio može složiti dar za prijateljicu? Koliko načina ima ako odustane od zamatanja u celofan?

$4 \cdot 2 \cdot 3 = 24,$ $4 \cdot 2 = 8$

Dar može složiti na $24$ načina s celofanom, odnosno na $8$ bez zamatanja.

...i na kraju

Osim načela zbroja i umnoška, u kombinatorici upotrebljavamo i tri temeljna načela o redanju, raspoređivanju i odabiru elemenata konačnih skupova, to su: permutacije, varijacije i kombinacije. Koristimo se njima ovisno o tome upotrebljavamo li sve elemente skupa ili samo neki podskup zadanog skupa te ponavljaju li se elementi ili ne. Pri odabiru načela važno je znati dvije stvari: 1) treba li uzeti u obzir poredak elemenata ili on nije važan i 2) smiju li se elementi ponavljati. Sa svakim ćemo se načinom upoznati u idućim jedinicama.

Za kraj odgovorite na pitanje: koliko ima četveroznamenkastih palindroma?

Zanimljivost

Palindrom (grč. palindromos, koji trči natrag) ili obrtaljka je broj, riječ, rečenica koji se čita jednako s obiju strana. Takvi brojevi su, npr., $151,$ $2 332,$ $45 854$ ili riječi radar, Krk, oko, a može i rečenica: Evo love! ili Ana voli Milovana.

Na prvom mjestu može biti $9$ znamenki (nula ne može biti na prvom mjestu). Kada smo odredili prvo mjesto odmah znamo da je i na četvrtom isti broj, još su preostala dva u sredini koja moraju biti jednaka. S obzirom da se može na drugom mjestu pojaviti bilo koja znamenka (ista ili različita od prve) moguće je odabrati znamenku na $10$ načina (koliko ima znamenki) i time je odabir gotov. Dakle po principu umnoška broj četveroznamenkastih palindroma je $9 \cdot 10 = 90 .$

Istražimo

Koliko je palindroma u datumima koji prikazuju dan i mjesec u godini (s dvije znamenke svaka brojka)? Npr. $01.10 .$ je jedan palindrom.