Odlomak

1. ČIME SE BAVI KOMBINATORIKA?
Grubo govoreći, razmeštanjima elemenata nekog skupa u tzv. diskretne strukture
(š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 A1, … , An može izabrati po jedan element − predstavnik, tako da svi predstavnici
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 igrač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 klasifikacija
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 rezultat
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 dvaput.
Tada se, uprkos pogrešnom brojanju, dobije tačan rezultat. No to je malo verovatna
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.

No votes yet.
Please wait…

Prijavi se

Detalji dokumenta

  • 14 stranica
  • Matematika kombinatorika Petrovic
  • Školska godina: Petrovic
  • Skripte, Matematika
  • Srbija,  Beograd,  UNIVERZITET U BEOGRADU - Matematički fakultet  

Više u Matematika

Više u Skripte

Komentari