Kombinacije bez ponavljanja

Pogledajte sljedeću animaciju.

Prije nego što odgovorimo na pitanje s kraja animacije prisjetimo se pojma i svojstava binomnih koeficijenata.

Broj u obliku

(\begin{array}{l} n \\ r \end{array}) = \frac{n (n - 1) \cdot . . . \cdot (n - r + 1)}{r!}

nazivamo

,

gdje je

\geq r \geq

.

null

Povežite svojstva binomnih koeficijenata s pripadajućim matematičkim zapisom.

Pascalova formula	$(\begin{array}{l} n \\ r \end{array}) = (\begin{array}{l} n \\ n - r \end{array})$
Svojstvo simetrije	$(\begin{array}{l} n \\ r \end{array}) = (\begin{array}{l} n - 1 \\ r - 1 \end{array}) + (\begin{array}{l} n - 1 \\ r \end{array})$
Prikaz s pomoću faktorijele	$(\begin{array}{l} n \\ 0 \end{array}) = (\begin{array}{l} n \\ n \end{array}) = 1$
Rubne vrijednosti	$(\begin{array}{l} n \\ r \end{array}) = \frac{n!}{r! (n - r)!}$

null

Vratimo se na animaciju i prisjetimo kako smo dobili broj mogućih izvlačenja triju kuglice iz skupa od $15$ elemenata, $\frac{15 \cdot 14 \cdot 13}{3 \cdot 2 \cdot 1},$ što kraće zapisujemo:

\frac{15!}{3!}

(\begin{array}{l} 15 \\ 3 \end{array})

(\frac{15}{3})!

\frac{15!}{12!} .

null

Općenito, broj izvlačenja $r$ elemenata iz skupa od $n$ elementa, gdje redoslijed nije važan, jednak je:

\frac{n!}{r!}

\frac{n (n - 1) (n - 2)}{r!}

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

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

null

Zanimljivost

Binomni koeficijet možemo definirati i u kontekstu s kombinatorikom, a ne kao koeficijent iz raspisa binomne formule.

Neka skup ima $n$ elemenata. Binomni koeficijent, $(\begin{array}{l} n \\ r \end{array})$ jednak je broju načina na koji se iz danog skupa može odabrati podskup od elemenata.

Kombinacije bez ponavljanja

Kombinacija $r$ -tog razreda od $n$ elemenata je svaki podskup od $r$ elemenata $n$ -članog skupa.

Ukupan broj kombinacija bez ponavljanja $r$ -tog razreda od $n$ elemenata jednak je $K_{n}^{r} = (\begin{array}{l} n \\ r \end{array}) .$

Primjer 1.

U snopu od $52$ karte su četiri boje s po $13$ karata: tref, pik, srce i karo.

Na koliko načina možemo odabrati $6$ karata iz snopa?

Koliko je različitih načina u kojima je svih šest karata pik?

Na koliko načina možemo odabrati $6$ karata od kojih su tri karo, dvije tref i jedna srce?

Koliko je različitih odabira $6$ karata u kojima je barem jedan tref?

Koliko je različitih načina odabira svih $6$ karata crvene boje?

Igraće karte

S obzirom na to redoslijed odabira karata nije važan, riječ je o kombinacijama bez ponavljanja gdje je $n = 52,$ $r = 6$ pa je ukupan broj odabira bilo kojih $6$ karata jednak
$(\begin{array}{l} 52 \\ 6 \end{array}) = \frac{52!}{6! \cdot 46!} = \frac{52 \cdot 51 \cdot 50 \cdot 49 \cdot 48 \cdot 47}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} =$ $20 358 520 .$
Pikova ima $13$ pa je ukupan broj odabira $6$ pikova od $13$ jednak
$(\begin{array}{l} 13 \\ 6 \end{array}) = \frac{13!}{6! 7!} = 1 716 .$
Tražimo ukupan broj odabira triju kartata od $13$ kara, dviju od $13$ trefova te jednu od $13$ srca. Prema načelu umnoška, ukupan broj odabira jednak je
$(\begin{array}{l} 13 \\ 3 \end{array}) \cdot (\begin{array}{l} 13 \\ 2 \end{array}) \cdot (\begin{array}{l} 13 \\ 1 \end{array}) = \frac{13 \cdot 12 \cdot 11}{3 \cdot 2 \cdot 1} \cdot \frac{13 \cdot 12}{2 \cdot 1} \cdot 13 =$ $290 004 .$
To je događaj suprotan događaju da nema nijednog trefa, pa najprije izračunajmo koliko ima kombinacija od $6$ karata među kojima nema nijedan tref. Biramo $6$ karata između $52 - 13 = 39$ što je jednako $(\begin{array}{l} 39 \\ 6 \end{array}) .$

Sada od ukupnog broja svih kombinacija odabira $6$ karata iz špila oduzmemo sve kombinacije u kojima nema trefa kao bismo dobili sve kombinacije od $6$ karata u kojima je barem jedan tref:
$(\begin{array}{l} 52 \\ 6 \end{array}) - (\begin{array}{l} 39 \\ 6 \end{array}) =$ $\frac{52 \cdot 51 \cdot 50 \cdot 49 \cdot 48 \cdot 47 - 39 \cdot 38 \cdot 37 \cdot 36 \cdot 35 \cdot 34}{6!} =$ $17 095 897 .$

Zadatak se može riješiti tako da promatramo sve moguće kombinacije s brojem trefova te prema načelu zbroja dobijemo konačan rezultat. Kada bismo izvukli jedan tref od $13$ karata, istodobno ostalih pet karata treba biti iz špila od preostalih $39$ karata pa ima ukupno $(\begin{array}{l} 13 \\ 1 \end{array}) (\begin{array}{l} 39 \\ 5 \end{array})$ kombinacija itd.
Dakle, ukupan broj kombinacija od kojih je barem jedna od šest izvučenih karata tref, jednak je
$(\begin{array}{l} 13 \\ 1 \end{array}) (\begin{array}{l} 39 \\ 5 \end{array}) + (\begin{array}{l} 13 \\ 2 \end{array}) (\begin{array}{l} 39 \\ 4 \end{array}) + (\begin{array}{l} 13 \\ 3 \end{array}) (\begin{array}{l} 39 \\ 3 \end{array}) + (\begin{array}{l} 13 \\ 4 \end{array}) (\begin{array}{l} 39 \\ 2 \end{array}) + (\begin{array}{l} 13 \\ 5 \end{array}) (\begin{array}{l} 39 \\ 1 \end{array}) + (\begin{array}{l} 13 \\ 6 \end{array}) (\begin{array}{l} 39 \\ 0 \end{array}) = 17 095 897 .$
Crvene boje su herc i karo pa ih je ukupno $26 .$ Broj različitih načina odabira $6$ karata od $26$ jednak je
$(\begin{array}{l} 26 \\ 6 \end{array}) = \frac{26 \cdot 25 \cdot 24 \cdot 23 \cdot 22 \cdot 21}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 230 230 .$

Riješite sljedeće zadatke s kombinacijama bez ponavljanja.

Kolekcija zadataka #1

U kutiji se nalazi $8$ bijelih, $7$ crvenih i $5$ crnih kuglica. Izvlačimo $5$ kuglica.

Na koliko načina možemo izvući $5$ kuglica?
Koliko ima izvlačenja u kojima su tri bijele?
Koliko ima izvlačenja u kojima nema crnih kuglica?
Koliko ima izvlačenja u kojima je jedna bijela, dvije crvene i dvije crne kuglice?

$(\begin{array}{l} 20 \\ 5 \end{array})$
$(\begin{array}{l} 8 \\ 3 \end{array}) (\begin{array}{l} 12 \\ 2 \end{array})$
$(\begin{array}{l} 15 \\ 5 \end{array})$
$(\begin{array}{l} 8 \\ 1 \end{array}) (\begin{array}{l} 7 \\ 2 \end{array}) (\begin{array}{l} 5 \\ 2 \end{array})$

U igri LOTO $6 / 45,$ odnosno $7 / 39$ izvlači se $6$ brojeva između $1$ i $45,$ odnosno $7$ brojeva između $1$ i $39 .$ Na koliko načina je moguće izvući te kombinacije?

Šest kombinacija od

45

moguće je izvući na

(\begin{array}{l} 45 \\ 6 \end{array})

načina

Sedam kombinacija od

39

moguće je izvući na

(\begin{array}{l} 39 \\ 7 \end{array})

načina.

Pomoć:

Izračunajte binomne koeficijente i upišite dobiveno rješenje na predviđeno mjesto u zadatku.

null

Iz snopa od $52$ karte izvlačimo $8$ karata. Na koliko načina možemo izvući $4$ karte crne boje? Na koliko načina možemo izvući točno jednog kralja i dvije dame? Na koliko načina možemo izvući od svake boje (tref, karo, srce i pik) po dvije karte.

Od osam izvučenih karata možemo izvući točno četiri crne boje na

(\begin{array}{l} 26 \\ 4 \end{array}) (\begin{array}{l} 26 \\ 4 \end{array})

načina.

Od osam karata točno jednog kralja i dvije dame možemo izvući na

(\begin{array}{l} 4 \\ 1 \end{array}) (\begin{array}{l} 4 \\ 2 \end{array}) (\begin{array}{l} 44 \\ 5 \end{array})

načina.

Dva trefa, dva pika, dva srca i dva kara možemo izvući na

(\begin{array}{l} 13 \\ 2 \end{array}) (\begin{array}{l} 13 \\ 2 \end{array}) (\begin{array}{l} 13 \\ 2 \end{array}) (\begin{array}{l} 13 \\ 2 \end{array})

načina.

null

...i na kraju

Sistematizirajmo na kraju uvjete iz kojih možemo lako odabrati način rješavanja kombinatornog problema.

	Odabir svih elemenata skupa	Važan poredak elemenata	Elementi se ponavljaju
Varijacije bez ponavljanja	NE	DA	NE
Varijacije s ponavljanjem	NE	DA	DA
Permutacije bez ponavljanja	DA	DA	NE
Permutacije s ponavljanjem	DA	DA	DA
Kombinacije bez ponavljanja	NE	NE	NE
Kombinacije s ponavljanjem	NE	NE	DA

Povežite nazive s pripadajućim formulama.

Varijacije s ponavljanjem	$\bar{K_{n}^{r}} = (\begin{array}{l} n + r - 1 \\ r \end{array})$
Permutacije s ponavljanjem	$P_{n} = n!$
Kombinacije s ponavljanjem	$\bar{V_{n}^{r}} = n^{r}$
Kombinacije bez ponavljanja	$V_{n}^{r} = \frac{n!}{(n - r)!}$
Varijacije bez ponavljanja	$K_{n}^{r} = (\begin{array}{l} n \\ r \end{array})$
Permutacije bez ponavljanja	$P_{n}^{n_{1}, n_{2}, . . ., n_{k}} = \frac{n!}{n_{1}! \cdot n_{2}! \cdot . . . \cdot n_{k}!}$

null

Procijenite svoje znanje

U kutiji se nalazi $12$ kuglica, pola je plavih, a pola crvenih. Biramo na sreću tri kuglice. Na koliko je načina moguće to učiniti ako je odabrana točno jedna crvena?

(\begin{array}{l} 12 \\ 3 \end{array})

(\begin{array}{l} 6 \\ 3 \end{array}) (\begin{array}{l} 6 \\ 3 \end{array})

(\begin{array}{l} 6 \\ 1 \end{array}) (\begin{array}{l} 6 \\ 2 \end{array})

(\begin{array}{l} 12 \\ 1 \end{array}) (\begin{array}{l} 12 \\ 2 \end{array})

null

U slastičarnici se nude četiri vrste kolača. Na koliko načina možemo odabrati 12 kolača?

Primjenjujemo formulu za

.

Ukupan broj elemenata je

n =

,

dok je

r =

.

Dvanaest kolača možemo odabrati na

načina.

null

Koliko je različitih permutacija slova $a,$ $b,$ $c,$ $d,$ $e$ gdje se slovo $a$ nalazi na prvom mjestu i slovo $e$ na posljednjemu?

Zadatak računamo s pomoću permutacija

s ponavljanjem ili bez ponavljanja

za

n =

Koliko slova permutiramo ako su dva već na svojemu mjestu?

pa

je

P_{n} =

3!

.

null

Pet učenika između sebe trebaju odabrati dvoje za prezentaciju svojega rada; prvi će prezentirati teorijski dio, a drugi pokazati praktični rad. Na koliko je načina to moguće učiniti?

Najprije definirajmo

n

i

r

pa izračunajmo traženi broj.

n =

ukupan broj učenika

i

r =

Koliko ih treba prezentirati?

.

Dva učenika od pet možemo odabrati na

V_{n}^{r} =

načina.

Ako nije važno tko će što prezentirati, tada je ukupan broj mogućnosti za izbor dvaju učenika jednak

K_{5}^{2} =

(\begin{array}{l} 5 \\ 2 \end{array})

.

null

Na koliko se načina mogu složiti riječi od slova riječi DIGITALIZACIJA pri čemu se koriste sva slova?

14!

\frac{14!}{7!}

(\begin{array}{l} 14 \\ 3 \end{array}) (\begin{array}{l} 14 \\ 4 \end{array})

\frac{14!}{3! \cdot 4!}

null

10.5 Kombinacije

Na početku...

Kombinacije bez ponavljanja

Zanimljivost

Kombinacije bez ponavljanja

Primjer 1.

Kolekcija zadataka #1

Kombinacije s ponavljanjem

Primjer 2.

Kolekcija zadataka #2

Kombinacije s ponavljanjem

Kolekcija zadataka #3

...i na kraju

Procijenite svoje znanje

MOJE ZNANJE

Uspješno ste usvojili sve odgojno-obrazovne ishode:

Potrudite se još malo kako biste bolje usvojili sljedeće odgojno-obrazovne ishode:

Trebali biste ponovno proći sljedeće jedinice: