Kombinatorika

Društvo matemati

č

ara Srbije 

Republi

č

ki seminar 

KOMBINATORIKA  

U SREDNJOJ ŠKOLI 

Vojislav Petrovi

ć

([email protected]) 

Departman za matematiku i informatiku 

Novi Sad 

Niš 2008. 

1.  

Č

IME SE BAVI KOMBINATORIKA? 

 Grubo 

govore

ć

i, razmeštanjima elemenata nekog skupa u tzv. diskretne struk-

ture (šeme, konfiguracije) koje zadovoljavaju odre

đ

ene uslove. Pritom se sre

ć

u slede-

ć

i tipovi problema. 

 
 1. 

Egzistencija

  (

postojanje

) 

strukture

. Da li je traženi razmeštaj izvodljiv, 

mogu

ć

? Ako nekad jeste, a nekad nije, pod kojim uslovima jeste? Na primer. Da li 

postoji magi

č

ni kvadrat reda 

n

 za svaki prirodan broj 

n

? Da li se iz svakog skupa iz 

familije 

A

1

, ... , 

A

n

 može izabrati po jedan element 

−

 predstavnik, tako da svi predstav-

nici budu razli

č

iti?  

 
 2. 

Prebrajanje ili klasifikacija struktura.

 Ako je tražena konfiguracija mogu-

ć

a, može ih biti više. Koliko ih ima? Kako in prebrojati? Na primer, na koliko na

č

ina 

se 

n

 osoba može rasporediti na 

n

 numerisanih stolica? Na turniru je u

č

estvovalo 

n

 ig-

ra

č

a i svaki sa svakim odigrao po jednu partiju. Koliko je partija odigrano? Koliko re-

šenja ima jedna

č

ina 

x

 + 

y

 + 

z

 = 10 u skupu nenegativnih celih brojeva? 

 3. 

Izu

č

avanje poznatih struktutra.

 Nakon utvr

đ

ivanja da odre

đ

ena struktura 

postoji, pristupa se izu

č

avanju njenih svojstava. Svrha je prebrajanje, odnosno klasifi-

kacija ili primena za rešavanje drugih problema. 
 
 4. 

Konstrukcija optimalne strukture.

 Ako traženih struktura ima više, mogu 

biti od interesa one koje se u odre

đ

enom smislu optimalne, najbolje. Na primer. Iz 

skupa od 

n

 elemenata može se izabrati više podskupova, tako da nijedan od njih nije 

sadržan u nekom drugom. Takva kolekcija zove se antilanac. Koliko maksimalno 
podskupova može da ima antilanac na skupu od 

n

 elemenata? 

Kako se srednjoškolska kombinatorika isklju

č

ivo bavi prebrajanjima skupova, 

problemom 2, tome 

ć

e biti posve

ć

eno ovo izlaganje.  

2.  OSNOVNI PRINCIPI PREBRAJANJA 

Osnovno pitanje je: "Koliko elemenata ima dati skup 

A

?" Taj broj se zove 

kardinalni broj

 skupa 

A

 i obeležava sa |

A

|. Kako 

ć

e isklju

č

ivo biti re

č

 o kona

č

nim 

skupovima, njihovi kardinalni brojevi su prirodni brojevi.  
 

Ako je skup 

A

 glomazan, komplikovan ili i jedno i drugo, pri njegovom 

prebrajanju 

č

esto su prisutne greške koje vode neta

č

nom kardinalnom broju |

A

|. 

Naj

č

eš

ć

a su dva tipa. Prvi je što se jedan ili više elemenata iz 

A

 se "presko

č

i", ne 

broji. A drugi, što se jedan ili više elemenata broji dva ili više puta. U oba slu

č

aja re-

zultat je pogrešan. Istina, mogu

ć

e je se na

č

ine greške oba tipa koje se me

đ

usobno 

kompenzuju (potiru). Na primer, jedan element se presko

č

i, a neki drugi se broji dva-

put. Tada se, uprkos pogrešnom brojanju, dobije ta

č

an rezultat. No to je malo verovat-

na slu

č

ajnost. 

Pricipi koji slede izme

đ

u ostalog služe da se navedene greške eliminišu. Me-

đ

utim, njihov zna

č

aj je daleko širi i ne svodi se samo na to. 

2

Primer 2. 

Gradovi 

A

, 

B

, 

C

 i 

D

 povezani su slede

ć

om mrežom puteva.  

A

B

C

D

Na koliko na

č

ina se može sti

ć

i iz 

A

 u 

D

? 

Rešenje.

 Iz 

A

 u 

B

 se može sti

ć

i na 3 na

č

ina, iz 

B

 u 

C

 na 5 i iz 

C

 u 

D

 na 2. Po 

principu proizvoda, iz 

A

 u 

D

 se može sti

ć

i na 3 

⋅

 5 

⋅

 2 = 30 na

č

ina. 

Primer 3. 

Koliko delitelja ima broj 600, uklju

č

uju

ć

i 1 i sam broj 600?

Rešenje. 

Rastavljanjem na proste faktore dobijamo 600 = 2

3

⋅

  3

1

⋅

  5

2

. Svaki 

delitelj broja 600 je oblika 2

x

⋅

 3

y

⋅

 5

z

, gde je 0 

≤

x

≤

 3, 0 

≤

y

≤

 1, 0 

≤

z

≤

 2. Broj 

razli

č

itih delitelja jednak je broju ure

đ

enih trojki (

x

, 

y

, 

z

), gde 

x

∈{

0, 1, 2, 3

}

, 

y

∈{

0, 

1

}

, 

z

∈{

0, 1, 2

}

. Po principu proizvoda, broj takvih trojki jednak je 4 

⋅

 2 

⋅

 3 = 24. 

Nije redak slu

č

aj da se principi zbira i proizvoda kombinuju. 

Primer 4. 

Koliko ima trojki brojeva (

a

, 

b

, 

c

), takvih da je 

a

 < 

b

, 

a

 < 

c

 i da      

a

, 

b

, 

c

∈{

1, 2, ... , 100

}

? 

Rešenje.

 Neka je 

S

 skup traženih trojki. Ozna

č

imo sa 

S

i

, 

i

 = 1, 2, ... , 99, trojku 

u kojoj je 

a

 = 

i

. Tada je 

S

 = 

S

1

∪

S

2

∪

 ... 

∪

S

99

 i 

S

i

∩

S

j

 = 

∅

 za 

i

≠

j

. Prema principu 

zbira je  
 
 

|

S

| = |

S

1

| + |

S

2

| + ... + |

S

99

|. 

  (1) 

 
Ako je 

a

 = 1, tada 

b

 i 

c

 mogu biti bilo koji od brojeva 2, 3, ... , 100 (dozvoljava se da 

su jednaki). Zna

č

i, za svaki po 99 = 100 

−

 1 mogu

ć

nosti. Na osnovu principa proizvo-

da dobijamo |

S

1

| =  99

2

. Z

a

a

 = 2 sledi 

b

, 

c

∈{

3, 4, ... , 100

}

, odnosno po 98 = 100 

−

 2 

mogu

ć

nosti za svaki. Sledi  |

S

2

| =  98

2

. Na isti na

č

in sledi da je |

S

3

| =  97

2

, ... , |

S

99

| =  

1

2

. Zamenjuju

ć

i u (1) dobijamo 

|

S

| = 99

2

 + 98

2

 +  ... + 2

2

 + 1

2

 . 

Koriste

ć

i poznatu formulu 1

2

 + 2

2

 + ... + 

n

2

 = 

6

)

1

2

)(

1

(

+

+

n

n

n

 dobijamo kona

č

no 

|

S

| = 

6

199

100

99

⋅

⋅

 = 328 350. 

Princip jednakosti (bijekcije) 

4