Kombinatorika – elementi i pojam skupa
Autor: D.Bajović www.promath.in.rs
Kombinatorika je grana matematike (diskretne matematike ) koja se bavi proučavanjem rasporeda podskupova i prebrojavanjem elemenata tih skupova.
Skup je osnovni matematički pojam i ne definiše se. Skup se može opisati (ne i definisati) kao celina različitih elemenata koji imaju neku osobinu. To se zapisuje
A={xІ α(x)} i čita se A je skup x-ova takvih da važi osobina α.
Skupove možemo zapisati i u sledećem obliku A={a1,a2,a3,a4,…,an-1,an}
U ovom zapisu su elementi skupa A nabrojani.
Za skupove nije bitan redosled elemenata, nije ni bitno da li se neki elementi ponavljaju ili ne.
{1,2,3}={1,1,2,2,3,3,3}={3,2,1}
Od elemenata skupa A možemo praviti različite rasporede ili nizove, praviti nove podskupove i prebrojavati njihove elemente.
Kombinatorika je povezana sa : algebrom , teorijom verovatnoće, geometrijom, računarstvom i fizikom.
Primer 1.
Dat je skup cifara A = {1, 2, 3, 4, 6, 7, 8}. Koliko se različitih petocifrenih brojeva može formirati od ovog skupa cifara, ako se cifre ne ponavljaju?
U prvom razredu su ovi zadaci rešavani bez korišćenja formula i bez navođenja koji je tip rasporeda u pitanju. Taj način rešavanja zadataka je, često najbolji način da se dođe do rešenja. Pa da se podsetimo.
Formiraju se petocifreni brojevi i posmatramo svaku poziciju cifre posebno i na koliko načina se ona može formirati.
_ _ _ _ _
Posmatramo prvu cifru broja i na koliko načina je možemo odabrati. Na raspolaganju je sedam cifara, znači na sedam načina
7 _ _ _ _ . Za izbor druge cifre je preostalo šest cifara
7 6 _ _ _ . Za treću cifru je preostalo pet cifara
7 6 5 _ _ i redom
7 6 5 4 3
Takvih brojeva ima x=7·6·5·4·3=2520
Pri rešavanju zadataka ovog tipa treba uočiti dve važne osobine formiranja izbora.
I Da li je bitan redosled izbora elemenata?
II Da li se elementi mogu ponavljati u izboru?
U prethodnom primeru je bitan redosled izbora (12 je različito od 21). Nekada se u tekstu zadatka naglasi da li se elementi mogu ponavljati ili ne. Ako se to ne naglasi onda moramo na osnovu izbora koji se formiraju odrediti da li se elementi mogu ponavljati ili ne.
Primer 2.
Dat je skup cifara A = {1, 2, 3, 4, 6, 7, 8}. Koliko se različitih petocifrenih brojeva može formirati od ovog skupa cifara?
U tekstu zadatka nije navedeno da li se cifre mogu ponavljati ili ne. U ovom slučaju npr. broj 11111 ispunjava uslove date u zadatku, a to znači da se cifre mogu ponavljati. Ukupan broj ovakvih brojeva se može odrediti sledećim postupkom.
Prva cifra se može odabrati na sedam načina.
Cifre se mogu ponavljati pa se za izbor druge cifre mogu koristiti sve cifre redom
7 7 7 7 7
Takvih brojeva ima
x=7·7·7·7·7=16807
Primer 3.
Iz odeljenja IV-1 koje ima 26 učenika treba odabrati delegaciju od tri učenika. Na koliko se načina to može uraditi?
Prvog učenika možemo odabrati na 26 načina. Izbor se ne može ponoviti pa je preostalo 25 učenika i poslednjeg učenika biramo od preostala 24 učenika
26 25 24
Prilikom izbora delegacije nije bitno kojim redom su odabrani učenici pa važi
A B V = A V B = B A V = B V A = V A B = V B A
To znači da je 6 puta ponovljen isti izbor. Bez nabrajanja istih izbora mogli smo taj broj ponavljanja odrediti i tako što posmatramo na koliko načina smo mogli rasporediti tri A, B i V učenika, a to je
3 2 1
Ukupan broj različitih delegacija je
X=(26·25·24):(3·2·1)
Primer 4.
Dat je skup cifara A = {0, 1, 2, 3, 4, 6, 7, 8}. Koliko se različitih petocifrenih brojeva može formirati od ovog skupa ako se:
- a) cifre ponavljaju;
- b) cifre ne ponavljaju.
Primer 5.
Dat je skup cifara A = {0, 1, 2, 3, 4, 6, 7, 8}. Koliko se različitih parnih/neparnih petocifrenih brojeva može formirati od ovog skupa ako se
- a) cifre ponavljaju;
- b) cifre ne ponavljaju.■
Primer 6.
Dat je skup cifara A = {0, 1, 2, 3, 4, 6, 7, 8}. Koliko se različitih petocifrenih brojeva deljivih sa 4 može formirati od ovog skupa ako se
- a) cifre ponavljaju;
- b) cifre ne ponavljaju.