Elementi kombinatorike

Zamislimo da u ormaru imamo 3 majice (belu, crnu i plavu) i 2 para pantalona (crne i sive).

Želimo da izaberemo jednu majicu i jedan par pantalona. Koliko različitih kombinacija odeće možemo napraviti?

Svaku od 3 majice možemo obući uz bilo koji od 2 para pantalona:

Majica	Crne pantalone	Sive pantalone
Bela	Bela + crne	Bela + sive
Crna	Crna + crne	Crna + sive
Plava	Plava + crne	Plava + sive

Ukupno imamo:

$$3\cdot 2=6$$

Dakle, možemo napraviti 6 različitih kombinacija.

Umesto da svaku kombinaciju pojedinačno nabrajamo, do rezultata smo došli množenjem broja mogućnosti.

Upravo se ovakvim problemima bavi kombinatorika, oblast matematike koja proučava na koliko načina možemo birati ili raspoređivati elemente prema određenim pravilima.

Sadržaj

1. Pravilo proizvoda
2. Pravilo zbira
3. Osnovni pojmovi kombinatorike
4. Primeri

1. Pravilo proizvoda

U prethodnom primeru morali smo da napravimo dva izbora:

1. Izaberemo jednu od 3 majice.
2. Izaberemo jedan od 2 para pantalona.

Za svaku izabranu majicu postoje 2 moguća izbora pantalona. Zato broj mogućnosti množimo.

Pravilo proizvoda: Ako se postupak sastoji od više uzastopnih koraka i svaki izbor u jednom koraku može da se kombinuje sa svakim izborom u sledećem, ukupan broj mogućnosti dobijamo množenjem broja izbora u svakom koraku.

Ako prvi korak možemo izvršiti na $n_1$ načina, drugi na $n_2$ načina, i tako redom, onda je

$$\boxed{N=n_1\cdot n_2\cdot\ldots\cdot n_k.}$$

Neka su $A_1,A_2,\ldots,A_n$ konačni skupovi. Broj elemenata Dekartovog proizvoda jednak je proizvodu brojeva elemenata pojedinačnih skupova:

$$\boxed{|A_1\times A_2\times\cdots\times A_n|=|A_1|\cdot|A_2|\cdots|A_n|.}$$

2. Pravilo zbira

Sada zamislimo drugačiju situaciju.

U školskoj kantini možemo kupiti 4 vrste sendviča ili 3 vrste peciva. Želimo da izaberemo samo jedan proizvod. Koliko različitih izbora imamo?

Možemo izabrati:

• Jedan od 4 sendviča, ili
• Jedno od 3 peciva.

Pošto biramo samo jedan proizvod, ne pravimo kombinacije sendviča i peciva. Zato broj mogućnosti sabiramo:

$$N=4+3=7.$$

Dakle, imamo 7 različitih mogućnosti.

Pravilo zbira: Ako se neki izbor može izvršiti na nekoliko različitih načina, odnosno kroz slučajeve koji se međusobno isključuju, ukupan broj mogućnosti dobijamo sabiranjem broja mogućnosti u svakom slučaju.

Ako prvi slučaj ima $N_1$ mogućnosti, drugi $N_2$ mogućnosti, i tako redom, onda je

$$\boxed{N=N_1+N_2+\ldots+N_k.}$$

Neka su $A_1,A_2,\ldots,A_n$ konačni skupovi koji su po parovima disjunktni, odnosno

$$A_i\cap A_j=\varnothing,\qquad i\ne j.$$

Tada je broj elemenata njihove unije jednak zbiru brojeva elemenata pojedinačnih skupova:

$$\boxed{|A_1\cup A_2\cup\cdots\cup A_n|=|A_1|+|A_2|+\cdots+|A_n|.}$$

3. Osnovni pojmovi kombinatorike

Pored pravila zbira i proizvoda, u kombinatorici razlikujemo tri osnovna načina izbora i raspoređivanja elemenata:

• Permutacije – raspoređujemo sve elemente nekog skupa. Redosled je važan.
• Varijacije – biramo određeni broj elemenata iz skupa i raspoređujemo ih. Redosled je važan.
• Kombinacije – biramo određeni broj elemenata iz skupa, ali redosled nije važan.

Na primer, ako imamo cifre $1$, $2$ i $3$:

U formulama je $n$ ukupan broj elemenata, a $k$ broj elemenata koje biramo.

	Primer	Šta posmatramo?	Formula bez ponavljanja
Permutacije	$123,132,213,\ldots$	Raspoređujemo svih $n$ elemenata	$P_n=n!$
Varijacije	$12,13,21,\ldots$	Biramo i raspoređujemo $k$ od $n$ elemenata	$V_n^k=\dfrac{n!}{(n-k)!}$
Kombinacije	$\{1,2\},\{1,3\},\{2,3\}$	Biramo $k$ od $n$ elemenata, bez obzira na redosled	$C_n^k=\dfrac{n!}{k!(n-k)!}$

Kod svakog od ovih pojmova dodatno razmatramo da li je ponavljanje elemenata dozvoljeno.

Pri rešavanju zadataka zato postavljamo tri pitanja:

1. Da li biramo sve elemente ili samo neke?
2. Da li je redosled važan?
3. Da li je ponavljanje dozvoljeno?

Odgovori na ova pitanja određuju koju formulu koristimo.

4. Primeri