Kažu da je ključni preduvjet za stvaranje elemenata kombinatorike i teorije vjerojatnosti bila ovisnost ljudi o lutriji, kockicama, kartama i drugim igrama na sreću. Kocka je bila od velike važnosti u antici. Neki su osvojili bogatstvo, zemlju, žene. Drugi su izgubili sve što su imali, do posljednje majice. Doista, dogodio se utjecaj rizičnih igara ili nasumičnih igara. Međutim, postojali su temeljniji razlozi, uključujući brzi razvoj znanosti: eksperimenti, potreba da se predvidi tijek niza eksperimenata i procijeni pogreška u rezultatima. Sve to i mnogo više dovelo je do pojave elemenata kombinatorike i teorije vjerojatnosti.
Bernoullijev teorem
Smatra se da se kombinatorika pojavila u 17. stoljeću zahvaljujući radu znanstvenika kao što su Cardano, Pascal, Galileo, Fermat, Leibniz, Bernoulli. Upravo su oni uveli posebne pojmoveza ovu znanost i dokazao niz temeljnih zakona i prve formule za kombinatoriku. Na primjer, Bernoullijev teorem, koji kaže da vrijedi uzeti u obzir samo one eksperimente i pokuse s slučajnošću koji su neovisni jedan o drugome i mogu se ponoviti neograničen broj puta pod istim uvjetima. Općenito je prihvaćeno da je ovaj teorem odredio daljnji razvoj kombinatorike i teorije vjerojatnosti kao znanosti.
Stabilnost frekvencije
Prije nego pređemo na proučavanje elemenata kombinatorike, dajmo jasan primjer koji sugerira određena razmišljanja - bacanje kocke. Razmotrimo jednu kost radi jednostavnosti. Ovo je šesterostrana kocka, čija je svaka strana numerirana. Ako provedemo niz eksperimenata od n bacanja i pretpostavimo da je G1 broj padova ruba s brojem 1, G2 - s brojem 2 itd. itd., ispada da s povećanjem broja bacanja n, frekvencija G1/n, G2 /n, …, G 6/n, koji se na početku eksperimenta čine nasumični, dobivaju sasvim određene vrijednosti. A za dobro izbalansiranu kocku, učestalost svakog aspekta bit će jednaka s velikom točnošću.
Još jedan primjer je eksperiment s novčićem. Dakle, znanstvenik Pearson, nakon što je proveo 24.000 bacanja novčića, došao je do zaključka da se učestalost ispadanja s jedne od strana novčića približava 0,5, što je točnije, to se više baca. Tako je za gubitak grba dobio vjerojatnost od 0,5005. Ovaj principstabilnost frekvencije je također jedan od temelja teorije.
Povijesna bilješka
Teorija vjerojatnosti i kombinatorika najaktivnije su se razvijale u 20. stoljeću. I ogroman doprinos ovoj stvari dali su ruski i sovjetski matematičari. Među njima, na primjer, Kolmogorov, Chebyshev, Lyapunov, Markov. Značajno su proširili područja primjenjivosti, istražili i opisali zakon velikih brojeva, središnji granični teorem i aksiomatiku teorije vjerojatnosti. Sve je to postalo osnova za cijelu znanost. Danas je teško precijeniti važnost elemenata kombinatorike i teorije vjerojatnosti u fizici, kemiji, biologiji i mnogim drugim područjima, posebice u njihovom praktičnom području.
Primjeri kombinatoričkih problema
Kombinatorika je procjena broja mogućih kombinacija sastavljenih od bilo kojeg skupa elemenata, podložna određenim uvjetima. Za to su izvedene formule u kombinatorici koje omogućuju prikladno i brzo rješenje 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 sudjeluje 16 momčadi. Na koliko će načina moći dodijeliti 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 ekipe 1, 2, 3, …
Ovo su sve primjeri opcija. Očigledno rješenje ovog problema bilo bi ispisati svemoguće kombinacije. Međutim, to će potrajati dosta vremena, jer će njihov broj biti isti jer postoje načini za preuređivanje 16 znamenki 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će nije važno kako izgleda poredak i kakav je redoslijed finalista. Doista, među svim timovima važno je pronaći samo tri koji će se međusobno natjecati za nagrade. Odnosno, skupovi mogu izgledati kao {3, 2, 1}, {5, 12, 7}, {8, 1, 2}, itd.
Problem 3. Što ako postavimo pitanje malo drugačije: na koliko načina postoji raspodjela medalja za 16 momčadi koje sudjeluju u doigravanju? Razlika s drugim zadatkom možda nije posve očita. No, sada moramo odabrati ne samo tri ekipe koje će se boriti za nagrade, već odrediti tko ć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, tada redoslijed naredbi sada ima težinu. Doista, 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 označen je sa C k, od engleske riječi Combination. Izjave C 1=n i C =1 su prilično očito To jest, postoji samo n opcija za odabir između n elemenata jedan po jedan (isti broj kao i sami elementi) i, sukladno 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.
Što se događa ako pokušate shvatiti što je C 0?
Postavljanje ili kombinacija na temelju narudžbe
Kombinatoriku postavljanja dovoljno je lako razumjeti. 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-dijelova elemenata iz n, poredanih određenim redoslijedom. Drugim riječima, dvije kombinacije položaja razlikuju se u tri slučaja:
- razlikuju se po sastavu;
- razlikuju se po redoslijedu elemenata u skupovima;
- razlikuju se i po sastavu i po redoslijedu.
Broj položaja od n do k označen je s 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 redak A33 zaslužuje posebnu pažnju. Ovo nisu ništa drugo nego permutacije.
Permutacije
Kao što je gore spomenuto, permutacije su prilično jednostavne u značenju. To 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 označava se 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 s neodređenim entitetima: skupom, kombinacijom itd. Bilo bi lijepomatematički precizno odrediti s čime imamo posla. Ovdje dobro dolazi jezik teorije skupova. Definirajmo koji su elementi kombinatorike jezikom teorije skupova.
Neka je zadan neki n-skup A={a1, a2, …, a }, sadrži n komada elemenata. Lako je iz n-skupa odrediti 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. Budući da 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 skup.
Tako, proučavajući skup od tri elementa {c, b, a}, dobivamo 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}.
Prema tome, oni će biti definirani na isti način u kombinatorici plasmana. Jedina razlika je u tome što trebate odabrati uređene k-podskupove iz n-skupa. I svi podskupovi će također sadržavati prazan skup. Uvjetno se smatra uređenom kombinacijom n elemenata od 0 komada, t.j. A 0=1.
Zbog prijelaza s nejasnih konstrukcija na objekte jasno definirane u teoriji skupova, pokazalo se prilično trivijalnim odgovoriti na jedan odpitanja koja su se pojavila. To je sva matematika.
Načelo zbrajanja
Ovo je jedno od dva osnovna pravila kombinatorike. Neka se u gradu Moskvi od točke A do točke B može doći s 5 autobusa, 3 tramvaja i 1 metroom. Ispostavilo se da postoji 5 + 3 + 1=9 načina da dođete do pravog mjesta. Ovo je kombinatorni princip zbrajanja.
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.
Načelo množenja
Zamislimo sada da trebate stići od Moskve do Kazana kroz Nižnji Novgorod. Istodobno, Moskva i Nižnji Novgorod su povezani s 2 vlaka, 3 leta i 10 automobila, a Nižnji Novgorod i Kazan - 1 vlakom, 1 letom i 2 autobusa. Načelom zbrajanja dolazimo do zaključka da postoji 13 načina da dođete od Moskve do Nižnjeg Novgoroda, a odatle do Kazana - 4. Ukupan broj načina koji povezuje Moskvu i Kazan bit će: 134=52.
Dakle, kombinatorni princip množenja glasi kako slijedi. Ako se problem riješi u n uzastopnih faza, s m1 načinima u prvoj fazi, m2 - u drugoj, itd., s U ovom slučaju, ove uzastopne faze su neovisne, 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 smatraju se različitim ako postoji barem jedna razlika u koracima.
Osnovne formule
Pokažimo formule odmah, zatim ukratko opišimo odakle dolaze i riješimo prethodno opisane primjere koristeći ove elemente kombinatorike.
Smještaj. Počinjemo s ovom formulom jer 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 temelji se na principima elemenata kombinatorike - pravilima zbrajanja i množenja. Razmotrite prvu formulu za pronalaženje broja položaja. U prvoj fazi uzimamo jedan od n komada elemenata i imamo n načina da to učinimo. U drugoj fazi ostaje nam n-1 elemenata i, sukladno tome, n-1 izbora. Na trećem - n-3 načina. Nastavljamo to činiti sve dok u našem skupu ne bude k komada elemenata. Prema 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 jednostavna je posljedica prve.broj zamjene m=k. Posljednja formula, koja daje broj kombinacija, dobiva se iz razmatranja da kada tražimo kombinacije 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 momčadi može smjestiti na ljestvicu. Drugi problem se odnosi na kombinacije, što znači C163=16! / [3!(16-3)!]=560 pobjednika. Konačno, posljednji problem se tiče položaja, 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.
