Dr Duška Pešić
Sremska Mitrovica, 2012.
1
Sadržaj
3
4
1
KOMBINATORIKA
Matematička disciplina čiji je glavni zadatak određivanje broja elemenata nekog konačnog skupa
(broj podskupova posmatranog skupa, koji zadovoljavaju neki uslov) naziva se
kombinatorika.
Kombinatorika (koja se u širem smislu smatra sinonimom «diskretne matematike») vekovima je
bila marginalna grana matematike. U drugoj polovini XX veka je postala jedna od grana matematike koja
se najbrže razvijala, naročito u smislu njene široke primene u prirodnim naukama (statička fizika),
ekonomiji (istraživanja), inženjerskim naukama, a posebno u računarstvu.
Kombinatorika otkriva probleme, različite od ranije razmatranih, i pruža nove načine za njihovo
rešavanje. Mnogi istaknuti matematičari su priznali da je kombinatorika interesantna i korisna, ali su
smatrali da ona obuhvata posebne probleme, koji su interesantni sami za sebe, ali ne predstavljaju
dovoljno značajnu i ozbiljnu problematiku. U okviru kombinatorike su se kasnije razvile teoreme i oblasti
koje pariraju klasičnoj matematici
1.1
Varijacije
Primer1.1.
Na
koliko
načina
se
može
napisati
trocifreni
broj
od
cifara:
1, 2, 3 i 4?
Rešenje: Na mestu stotina mogu stajati sve 4 cifre. Isti je slučaj sa brojem cifara na mestu
desetica i jedinica. Dakle, broj mogućih trocifrenih brojeva je
3
4 4 4
4 =64
.
Ako se modifikuje prethodno pitanje i dozvoli da se svaka od datih cifara koristi samo jedanput, na
mestu stotina mogu se pojaviti sve 4 cifre, dok se na mestu desetica mogu pojaviti 3 cifre (izuzev
korišćene), a na mestu jedinica samo 2. Tada su moguća samo
4 3 2 = 24
takva broja.
Problem pronalaženja broja
k
- tocifrenih brojeva ispisanih pomoću
n
cifara, daje rešenje:
k
n
.
Ukoliko se cifre mogu ponavljati, dok se bez ponavljanja cifara dobija:
(
1)(
2)
(
1)
n n
n
n k
.
Navedeni rasporedi se nazivaju varijacije sa i bez ponavljanja.
Varijacije
* uzima se deo skupa, bitan je redosled elemenata
Varijacije sa ponavljanjem
(od
n
elemenata klase
k
)
,
k
k
n
n
k
N
V
Varijacije bez ponavljanja
(od
n
elemenata klase
k
)
!
= (
1)(
2)
(
1)
,
(1
)
!
k
n
n
n n
n
n k
k
n
n k
V
!
n
- čita se kao
en-faktorijel
i predstavlja oznaku za proizvod svih prirodnih brojeva do
n
(uključujući
n
). Npr.
4! 1 2 3 4
24
. Da bi se olakšalo traženje vrednosti faktorijela za velike brojeve,
koristi se Stirlingov obrazac:
!
2
n
n
n
n
e
.
1.2
Permutacije
Primer1.2.
Na koliko načina se može devet različitih knjiga poređati na polici?
Rešenje:
Na prvoj poziciji se može naći svaka od 9 knjiga, na drugoj poziciji može biti preostalih 8, na
trećoj 7, ...., na devetoj poziciji samo jedna preostala knjiga. Dakle, oni se mogu rasporediti na
9 8 7 6 5 4 3 2 1 = 9!
načina.
Ako su od 9 knjiga 2 međusobno iste, 4 međusobno iste i 3 međusobno iste, mogu se rasporediti
na
9!
2!4!3!
načina.
6
Primer1.4.
Napisati sve permutacije od elemenata:
a
,
b
,
c
,
d
.
Rešenje: Ima ukupno 20 različitih permutacija (4!=20)
Koje počinju na slovo a (ima ih 3!=6): abcd, abdc, acbd, acdb, adbc, adcb
Koje počinju na slovo b (ima ih 3!=6): bacd, badc, bcad, bcda, bdac, bdca
Koje počinju na slovo c (ima ih 3!=6): cabd, cadb, cbad, cbda, cdab, cdba
Koje počinju na slovo d (ima ih 3!=6): dabc, dacb, dbac, dbca, dcab, dcba
Primer1.5.
Koliko se petocifrenih brojeva može napisati pomoću cifara: 2,3,4,4,4.
Rešenje:
Radi se o permutacijama sa ponavljanjem:
1,1,3
5!
20
1!1!3!
P
Primer1.6.
Broj permutacija od
2
n
elementa je 56 puta veći od broja permutacija od
n
elemenata.
Koliko je
n
?
Rešenje:
2
2 ! 56
!
2
1
56
3
54
0
6
n
n
n
n
n
n
n
Napomena: uzima se samo rešenje iz skupa prirodnih brojeva.
Primer1.7.
Na koliko načina mogu sesti u red 5 devojaka i 5 momaka ako naizmenično sede momci i
devojke?
Rešenje:
Prvo može biti momak ili devojka, a u svakom od ta dva slučaja devojke i momci se razvrstavaju
kao permutacije od 5 elemenata. Zato je konačno rešenje:
2 5! 5!
.
Primer1.8.
Koliko ima trocifrenih brojeva sa različitim ciframa?
Rešenje:
Na prvom mestu se bira od devet cifara (nula ne može da dođe na prvo mesto jer mora biti
trocifren broj), na drugo mesto može doći i nula ali ne i broj postavljen na prvom mestu, dok na trećem
mestu može biti jedan od preostalih osam brojeva. Rešenje je:
9 9 8
.
Primer1.9.
Formirati sve varijacije sa ponavljanjem klase 3 od elemenata skupa
a
,
b
,
c
,
d
.
Rešenje:
Kako se elementi mogu ponavljati dobija se ukupno
3
4
64
elemenata. Prateći redosled kao u
rečnicima, dobija se sledeći niz varijacija:
aaaa, aaab, aaac, aaad, aaba, aabb, aabc, aabd, aaca, aacb, aacc, aacd,abaa, abab, abac, abad, abba,
abbc, abbd, abca, abcb, abcc, abcd, abda, abdb, abdc, abdd, ..., dddd.
Primer1.10.
Od 15 proizvoda treba odabrati 3. Na koliko načina je moguće izvršiti izbor?
Rešenje:
Radi se o kombinacijama bez ponavljanja
3
15
15
3
C
.
Ovaj materijal je namenjen za učenje i pripremu, ne za predaju.
