Kažu da je ključni preduslov za stvaranje elemenata kombinatorike i teorije vjerovatnoće bila ovisnost ljudi o lutriji, kockicama, kartama i drugim igrama na sreću. Kockanje je bilo od velikog značaja u antici. Neki su osvojili bogatstvo, zemlju, žene. Drugi su izgubili sve što su imali, do posljednje majice. Zaista, došlo je do uticaja igara rizika ili nasumičnih igara. Međutim, postojali su fundamentalniji razlozi, uključujući brzi razvoj nauke: eksperimenti, potreba da se predvidi tok serije eksperimenata i proceni greška u rezultatima. Sve ovo i mnogo više dovelo je do pojave elemenata kombinatorike i teorije vjerovatnoće.
Bernoullijeva teorema
Smatra se da se kombinatorika pojavila u 17. veku zahvaljujući radu naučnika kao što su Cardano, Pascal, Galileo, Fermat, Leibniz, Bernoulli. Oni su bili ti koji su uveli posebne termineza ovu nauku i dokazao niz fundamentalnih zakona i prve formule za kombinatoriku. Na primjer, Bernoullijev teorem, koji kaže da vrijedi uzeti u obzir samo one eksperimente i eksperimente sa slučajnošću koji su neovisni jedan o drugom i mogu se ponoviti neograničen broj puta pod istim uvjetima. Općenito je prihvaćeno da je ova teorema odredila dalji razvoj kombinatorike i teorije vjerovatnoće kao nauke.
Stabilnost frekvencije
Prije nego što pređemo na proučavanje elemenata kombinatorike, dajmo jasan primjer koji sugerira određena razmišljanja - bacanje kockica. Razmotrimo jednu kost radi jednostavnosti. Ovo je šestostrana kocka, čija je svaka strana numerisana. Ako izvršimo seriju eksperimenata od n bacanja i pretpostavimo da je G1 broj padova ivice sa brojem 1, G2 - sa brojem 2 itd. itd., ispada da sa povećanjem broja bacanja n, frekvencija G1/n, G2 /n, …, G 6/n, koji na početku eksperimenta izgledaju nasumično, dobijaju sasvim određene vrijednosti. A za dobro izbalansiranu kocku, frekvencija svakog aspekta će biti jednaka sa velikom preciznošću.
Još jedan primjer je eksperiment s novčićima. Dakle, naučnik Pearson je, nakon što je izvršio 24.000 bacanja novčića, došao do zaključka da se učestalost ispadanja jedne od strana novčića približava 0,5, što je tačnije, više se baca. Tako je za gubitak grba dobio vjerovatnoću od 0,5005. Ovaj principstabilnost frekvencije je također jedan od temelja teorije.
Historijska bilješka
Teorija verovatnoće i kombinatorika su se najaktivnije razvijale u 20. veku. I ogroman doprinos ovoj stvari dali su ruski i sovjetski matematičari. Među njima, na primjer, Kolmogorov, Čebišev, Ljapunov, Markov. Oni su značajno proširili područja primjenjivosti, istražili i opisali zakon velikih brojeva, središnju graničnu teoremu i aksiomatiku teorije vjerovatnoće. Sve je to postalo osnova za čitavu nauku. Danas je teško precijeniti značaj elemenata kombinatorike i teorije vjerovatnoće u fizici, hemiji, biologiji i mnogim drugim oblastima, posebno u njihovoj praktičnoj oblasti.
Primjeri kombinatoričkih problema
Kombinatorika je procjena broja mogućih kombinacija sastavljenih od bilo kojeg skupa elemenata, pod određenim uvjetima. Za to su u kombinatorici izvedene formule koje omogućavaju pogodno i brzo rješavanje traženog problema. Ali prije nego što pokažemo ove formule, pogledajmo neke primjere pitanja koja su dovela do njih.
Zadatak 1. U play-off fazi Svjetskog prvenstva učestvuje 16 timova. Na koliko načina će moći da raspodijele mjesta među sobom? Tako na primjer:
- (3, 1, 2, 4..16) - tim broj 3 je na prvom mjestu, tim broj 1 je na drugom mjestu, itd.
- (16, 1, 2, 3, 4..15) - tim broj 16 je na prvom mjestu, …
- (1..7, 9, 8, 10..16) - na prvim mjestima tima 1, 2, 3, …
Ovo su sve primjeri opcija. Očigledno rješenje ovog problema bi bilo da se sve ispišemoguće kombinacije. Međutim, to će potrajati dosta vremena, jer će njihov broj biti isti jer postoje načini za preuređivanje 16 cifara na mjestima. Elementi kombinatorike rješavaju primjere poput ovog u trenu.
Problem 2. Među ovih 16 timova, samo tri mogu dobiti nagradu. Na koliko načina će se odrediti pobjednici? U ovom slučaju zadatak se razlikuje od prethodnog po tome što uopšte nije bitno kako izgleda poredak i kakav je redosled finalista. Zaista, među svim timovima važno je pronaći samo tri koji će se međusobno takmičiti za nagrade. Odnosno, setovi mogu izgledati kao {3, 2, 1}, {5, 12, 7}, {8, 1, 2}, itd.
Problem 3. Šta ako postavimo pitanje malo drugačije: na koliko načina postoji raspodjela medalja za 16 timova koji učestvuju u doigravanju? Razlika sa drugim zadatkom možda nije sasvim očigledna. Međutim, sada moramo izabrati ne samo tri ekipe koje će se nadmetati za nagrade, već da odredimo koji će od njih zauzeti koje mjesto. Drugim riječima, ako su za drugi zadatak, na primjer, skupovi (5, 12, 1) i (1, 12, 5) bili ekvivalentni, onda red naredbi sada ima težinu. Zaista, u prvom slučaju, tim broj 5 će dobiti zlato, au drugom slučaju tim broj 1.
U nastavku ćemo razmotriti kojem od dijelova kombinatorike pripada svaki od zadataka i detaljno opisati kako ih riješiti. U međuvremenu, možete pokušati sami razmisliti o postavljenim pitanjima.
Kombinacije ili kombinacije bez obzira na narudžbu
Kombinacija samo n-komada elemenataskupovi k-komada elemenata, gdje k može imati vrijednosti od 1 do n, je bilo koja kombinacija od k elemenata odabranih od n komada elemenata. U ovom slučaju, dva skupa će se smatrati različitim ako jedan od njih sadrži bilo koji element iz n, ali ne pripada drugom. Drugim riječima, razlikuju se samo po sastavu. U elementima kombinatorike, kombinacije su uvodna osnova.
Broj kombinacija od n do k je označen sa C k, od engleske riječi Combination. Izjave C 1=n i C =1 su prilično Očigledno To jest, postoji samo n opcija za biranje između n elemenata jedan po jedan (isti broj kao i sami elementi) i, shodno tome, možete napraviti skup od n elemenata u količini od n komada, samo jedan.
Tako, na primjer, razmotrite skup od tri elementa {e, 2, a}. Za njega C31=3: {a}, {2}, {e}; C32=3: {e, 2}, {2, a}, {a, e}; i konačno C33=1: {e, 2, a}. Podsjetimo da u ovom slučaju redoslijed elemenata u skupovima nije bitan.
Šta se dešava ako pokušate da shvatite šta je C 0?
Postavljanje ili kombinacija na osnovu narudžbe
Kombinatorika plasmana je dovoljno laka za razumevanje. To su iste kombinacije, samo što se sada ne uzima u obzir samo sastav, već i redoslijed u svakoj kombinaciji. Dakle, postavljanjem n komada elemenata u kombinacije (skupove) od k komada, pri čemu k može imati vrijednosti od 1 do n,naziva se svaka kombinacija koja se sastoji od k-komada elemenata iz n, raspoređenih određenim redoslijedom. Drugim riječima, dvije kombinacije plasmana su različite u tri slučaja:
- razlikuju se po sastavu;
- razlikuju se po redoslijedu elemenata u setovima;
- razlikuju se i po sastavu i po redoslijedu.
Broj plasmana od n do k je označen sa A k, iz Aranžmana. Razmotrite sve opcije postavljanja za skup od tri elementa {x, e, z}:
- A31=3: (x), (e), (z);
- A32=6: (x, e), (e, x), (x, z), (z, x), (e, z), (z, e);
- A33=6: (x, e, z), (e, x, z), (z, x, e), (x, z, e), (e, z, x), (z, e, x).
Posljednji red A33 zaslužuje posebnu pažnju. Ovo nisu ništa drugo do permutacije.
Permutacije
Kao što je gore spomenuto, permutacije su prilično jednostavne po značenju. Ovo su jednostavno rasporedi od n elemenata, po n. Odnosno, zanimaju nas sve kombinacije koje se razlikuju po redoslijedu elemenata, i samo u njima. Ili, ekvivalentno, A . Broj permutacija je označen slovom P, od riječi Permutacija. U elementima kombinatorike, permutacije imaju samo jedan indeks. Tako, na primjer, P3=6, kao što smo saznali u prethodnom poglavlju.
Kombinacije kroz teoriju skupova
Kao što znate, u matematici je teško komunicirati sa neodređenim entitetima: skupom, kombinacijom itd. Bilo bi lijepomatematički precizno odrediti sa čime imamo posla. Ovdje dobro dolazi jezik teorije skupova. Hajde da definišemo šta su elementi kombinatorike u jeziku teorije skupova.
Neka se da neki n-skup A={a1, a2, …, a }, sadrži n komada elemenata. Lako je odrediti iz n-skupa njegov k-podskup, gdje je k manji ili jednak n. Tada će se kombinacije od n do k zvati svi podskupovi k skupa n. Zahvaljujući ovoj definiciji, lako je odgovoriti na pitanje kako će izgledati unos C 0. Pošto je u teoriji skupova prazan skup sadržan u bilo kojem podskupu, onda je C 0=1. Drugim riječima, to će biti kombinacija koja sadrži jedan element - prazan set.
Tako, proučavajući skup od tri elementa {c, b, a}, dobijamo da C 0 =1: { }; C31=3: {a}, {b}, {c}; C32=3: {a, b}, {b, c}, {c, a}; i konačno C33=1: {a, b, c}.
Shodno tome, oni će biti definisani na isti način u kombinatorici plasmana. Jedina razlika je u tome što morate odabrati uređene k-podskupove iz n-skupa. I svi podskupovi će također sadržavati prazan skup. Uslovno se smatra uređenom kombinacijom n elemenata od 0 komada, tj. A 0=1.
Usled prelaska sa nejasnih konstrukcija na objekte jasno definisane u teoriji skupova, pokazalo se da je sasvim trivijalno odgovoriti na jedan odpitanja koja su se pojavila. To je sva matematika.
Princip dodavanja
Ovo je jedno od dva osnovna pravila kombinatorike. Neka se u gradu Moskvi od tačke A do tačke B može doći sa 5 autobusa, 3 tramvaja i 1 metro vozom. Ispostavilo se da postoji 5 + 3 + 1=9 načina da dođete do pravog mjesta. Ovo je kombinatorni princip sabiranja.
Ako se pri razmatranju problema može riješiti na n načina, dok se prva od ovih metoda može primijeniti m1 puta, druga - m 2puta, itd., tada će ovaj problem biti riješen m1 + m2 + … + mnačina.
Princip množenja
Sada zamislimo da trebate stići od Moskve do Kazana preko Nižnjeg Novgoroda. Istovremeno, Moskvu i Nižnji Novgorod povezuju 2 voza, 3 leta i 10 automobila, a Nižnji Novgorod i Kazanj - 1 voz, 1 let i 2 autobusa. Po principu sabiranja, dolazimo do zaključka da postoji 13 načina da se od Moskve stigne do Nižnjeg Novgoroda, a odatle do Kazanja - 4. Ukupan broj načina koji povezuje Moskvu i Kazan će biti: 134=52.
Dakle, kombinatorni princip množenja glasi kako slijedi. Ako se problem riješi u n uzastopnih faza, sa m1 načinima u prvoj fazi, m2 - u drugoj, itd., sa U ovom slučaju, ove uzastopne faze su nezavisne, odnosno broj načina se ne mijenja ovisno o tome kako je odluka donesena u prethodnim fazama, tada je problem riješen m1 m2 …m načine. Dva rješenja se smatraju različitim ako postoji barem jedna razlika u koracima.
Osnovne formule
Pokažimo formule odmah, zatim ukratko opišemo odakle dolaze i riješimo ranije opisane primjere koristeći ove elemente kombinatorike.
Accommodations. Počinjemo sa ovom formulom pošto su druge izvedene iz nje
| A k= | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1)= | n! |
| (n-k)! |
Permutacije
| P= | A = | n(n-1)(n-2)(n-3)(n-4)(n-5)…4321= | n! |
Kombinacije
| C k= | A k | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1) | n! |
| k! | k! | k!(n-k)! |
Dokaz ovih formula zasniva se na principima elemenata kombinatorike - pravilima sabiranja i množenja. Razmotrite prvu formulu za pronalaženje broja plasmana. U prvoj fazi, uzimamo jedan od n komada elemenata i imamo n načina da to uradimo. U drugoj fazi ostaje nam n-1 elemenata i, shodno tome, n-1 izbora. Na trećem - n-3 načina. Nastavljamo da radimo sve dok u našem skupu ne bude k komada elemenata. Po pravilu množenja doći ćemo do činjenice da ukupno ima n (n-1) (n-2) (n-3) (n-4) (n-5) … (n-k + 1) načina odabira k elemenata. Druga formula za pronalaženje permutacija je jednostavna posljedica prve.broj zamjene m=k. Posljednja formula, koja daje broj kombinacija, dobijena je iz razmatranja da kada se traži kombinacija od n elemenata, k komada svaki put kada dođemo do k! rasporedi od n do k (dobijaju se kao permutacije k elemenata). Dakle, imamo A k=C kk!.
Sada se možemo vratiti na ranije najavljene zadatke i procijeniti broj opcija. Za prvi problem, trebamo koristiti formulu permutacije, tj. P16=16!=20 922 789 888 000 ≈ 211012 moguće opcije kako se 16 timova može postaviti na tabeli. Drugi problem se tiče kombinacija, što znači C163=16! / [3!(16-3)!]=560 pobjednika. Konačno, posljednji problem se tiče plasmana, tj. A163=16! / (16-3)!=3360 načina kako 3 tima od 16 mogu podijeliti nagrade.
S obzirom na gore navedeno, suvišno je govoriti o tome kako kombinatorika velikih brojeva funkcionira.
