G
RAFI
Č
KI FAKULTET
,
KISELJAK
2010
KOMBINATORIKA
Seminarski rad “Vjerovatno
ć
a i statistika“
Ilhan Hadžimejli
ć
U N I V E R Z I T E T
U
T R A V N I K U
1.
UVOD
1
Brojanje i prebrojavanje dio je našeg svakodnevnog života.
Kombinatorika je grana matematike koja se bavi prebrojavanjem elemenata kona
č
nih
skupova i prebrojavanjem broja na
č
ina da se ti elementi poredaju.
Faktorijeli
Umnožak prvih n prirodnih brojeva ozna
č
avamo
n
! i
č
itamo "n faktorijela".
Po definiciji stavljamo
0!=1.
Faktorijeli zadovoljavaju rekurzivnu formulu
.
Binomni koeficijenti
Neka je
n
prirodan broj i
k
prirodan broj ili 0,
,
binomni
koeficijent ozna
č
avamo
,
č
itamo "iznad (ili povrh)
k
" i definiramo:
,
,
,
.
Princip uzastopnog prebrojavanja
Ako možemo
birati prvi
element
na
na
č
ina,
drugi
element
na
na
č
ina, ...,
r
-ti
element
na
na
č
ina,
tada je ukupan broj na
č
ina na koji možemo birati ure
đ
enu
r
-torku jednak
Primjer: Koliko ima
č
etveroznamenkastih brojeva s razli
č
itim znamenkama?
Prvu znamenku možemo birati po volji, 9 je mogu
ć
ih izbora (na prvom mjestu ne smije biti nula).
Bez obzira koju smo prvu znamenku izabrali, drugu znamenku biramo izme
đ
u 9 preostalih (sad
možemo uzeti i nulu).
Tre
ć
u znamenku biramo izme
đ
u 8 preostalih,
a
č
etvrtu izme
đ
u 7 preostalih.
Dakle,
č
etveroznamenkastih brojeva s razli
č
itim znamenkama ima
1
http://free-zg.t-com.hr/Vesna_Erceg/Kombinatorika/KOMB_uvod.htm
Rješavanje ovih primjera, kao i gotovo svakog problema kombinatorike temelji se na
jednostavnom, a važnom principu:
Primjer 3.
Koliko razli
č
itih produkata možemo napraviti s jednim slovom iz skupa
A
={a,b,c} te
jednim brojem iz skupa B={1,2,3,4}?
Rješenje:
Jedno slovo iz skupa
A
možemo odabrati na 3 razli
č
ita na
č
ina, jedan broj iz skupa
B
možemo odabrati na 4 razli
č
ita na
č
ina. Prema principu o uzastopnom prebrojavanju razli
č
itih
produkata ima 3
×
4 = 12.
Primjer 4.
Koliko razli
č
itih registarskih oznaka postoji u nekom gradu ako svaka nosi
č
etiri
znamenke te dva slova (od 22)?
Rješenje:
Primjetimo da nije važan razmještaj slova i znamenki unutar registarske oznake, jer
kakav god bio razmještaj, dva slova (iz skupa od 22) mo
ć
i
ć
emo odabrati na 22·22 = 484 razli
č
ita
na
č
ina, dok
ć
emo
č
etiri znamenke (od 10) mo
ć
i odabrati na 10·10·10·10 = 1000 razli
č
itih na
č
ina,
što daje 10
4
×
22
2
= 4 840 000 razli
č
itih mogu
ć
nosti..
Primjer
5. Koliko ima troznamenkastih brojeva?
Rješenje:
Od 100 do 999 ima 999 - 100 + 1 = 900 brojeva.
Pomo
ć
u teorema o uzastopnom prebrojavanju: prvu znamenku možemo birati na 9 razli
č
itih
na
č
ina (mora biti
≠
0), a druge dvije (smiju biti proizvoljne) na deset razli
č
itih na
č
ina. Ukupan broj
razli
č
itih mogu
ć
nosti je 9·10·10 = 900.
Primjer 6.
Koliko postoji troznamenkastih brojeva razli
č
itih znamenki?
Rješenje:
Prvu znamenku možemo birati na 9 razli
č
itih na
č
ina (znamenke od 1 do 9). Nakon što je
prva znamenka izabrana, za drugo mjesto imamo tako
đ
er 9 razli
č
itih mogu
ć
nosti (znamenke 0 do
2.2. Princip uzastopnog prebrojavanja
Ako biramo po jedan element iz svakog od
k
zadanih skupova
A
1
,...,A
k
pri
č
emu skup
A
1
ima
n
1
elemenata,
A
2
ima
n
2
elemenata, ... , skup
A
k
ima
n
k
elemenata, tada razli
č
itih odabira ima
n
1
×
n
2
×
.. .
×
n
k
.
ili
Ako u slijedu od
k
me
đ
usobno nezavisnih postupaka prvi možemo napraviti na
n
1
na
č
ina, drugi
možemo napraviti na
n
2
na
č
ina, ...,
k-ti
možemo napraviti na
n
k
na
č
ina tada je ukupan broj na
č
ina
na koji to možemo napraviti jednak
n
1
×
n
2
×
.. .
×
n
k
.
