Ovaj članak će se usredotočiti na poseban dio matematike koji se zove kombinatorika. Formule, pravila, primjeri rješavanja problema - sve to možete pronaći ovdje čitajući članak do samog kraja.
Dakle, koji je ovo odjeljak? Kombinatorika se bavi pitanjem brojanja bilo kojih objekata. No, u ovom slučaju, predmeti nisu šljive, kruške ili jabuke, već nešto drugo. Kombinatorika nam pomaže pronaći vjerojatnost događaja. Na primjer, pri kartanju, kolika je vjerojatnost da protivnik ima adut? Ili takav primjer – kolika je vjerojatnost da ćete iz vrećice od dvadeset loptica dobiti točno bijelo? Za ovakvu vrstu zadataka moramo poznavati barem osnove ovog dijela matematike.
Kombinatorne konfiguracije
S obzirom na problematiku osnovnih pojmova i formula kombinatorike, ne možemo ne obratiti pozornost na kombinatorne konfiguracije. Koriste se ne samo za formulaciju, već i za rješavanje raznih kombinatornih problema. Primjeri takvih modela su:
- placement;
- permutacija;
- kombinacija;
- broj sastav;
- podijeljeni broj.
O prva tri ćemo detaljnije govoriti kasnije, ali ćemo u ovom odjeljku obratiti pažnju na sastav i podjelu. Kada govore o sastavu određenog broja (recimo, a), misle na prikaz broja a kao uređenog zbroja nekih pozitivnih brojeva. A split je neuređeni zbroj.
odjeljci
Prije nego što prijeđemo izravno na formule kombinatorike i razmatranje problema, vrijedi obratiti pažnju na činjenicu da kombinatorika, kao i drugi dijelovi matematike, ima svoje pododjeljke. To uključuje:
- nabrajanje;
- strukturno;
- extreme;
- Ramseyeva teorija;
- probabilistički;
- topološki;
- beskonačno.
U prvom slučaju govorimo o enumerativnoj kombinatorici, problemi se odnose na nabrajanje ili brojanje različitih konfiguracija koje su formirane elementima skupova. U pravilu se na te skupove nameću neka ograničenja (različivost, nerazlučivost, mogućnost ponavljanja i tako dalje). A broj ovih konfiguracija izračunava se pomoću pravila zbrajanja ili množenja, o čemu ćemo govoriti malo kasnije. Strukturna kombinatorika uključuje teorije grafova i matroida. Primjer problema ekstremne kombinatorike je koja je najveća dimenzija grafa koja zadovoljava sljedeća svojstva… U četvrtom odlomku spomenuli smo Ramseyevu teoriju koja proučava prisutnost regularnih struktura u slučajnim konfiguracijama. Vjerojatnostkombinatorika je u stanju odgovoriti na pitanje – kolika je vjerojatnost da dati skup ima određeno svojstvo. Kao što možete pretpostaviti, topološka kombinatorika primjenjuje metode u topologiji. I na kraju, sedma točka - beskonačna kombinatorika proučava primjenu kombinatoričkih metoda na beskonačne skupove.
Pravilo zbrajanja
Među formulama kombinatorike mogu se pronaći sasvim jednostavne, s kojima smo već dugo upoznati. Primjer je pravilo zbroja. Pretpostavimo da su nam zadane dvije radnje (C i E), ako se međusobno isključuju, radnja C se može izvesti na nekoliko načina (na primjer, a), a akcija E može se izvesti na b-načine, tada bilo koja od njih (C ili E) može se izvesti na a + b načine.
U teoriji, ovo je prilično teško razumjeti, pokušat ćemo prenijeti cijelu poantu jednostavnim primjerom. Uzmimo prosječan broj učenika u jednom razredu – recimo da je dvadeset i pet. Među njima je petnaest djevojaka i deset dječaka. U razred se dnevno dodjeljuje jedan polaznik. Na koliko načina danas možete dodijeliti polaznika razreda? Rješenje problema je prilično jednostavno, pribjeći ćemo pravilu zbrajanja. U tekstu zadatka ne stoji da dežuraju mogu biti samo dječaci ili samo djevojčice. Stoga bi to mogla biti bilo koja od petnaest djevojaka ili bilo koji od deset dječaka. Primjenom pravila zbroja dobivamo prilično jednostavan primjer s kojim se učenik osnovne škole lako može nositi: 15 + 10. Izračunavši, dobivamo odgovor: dvadeset pet. Odnosno, postoji samo dvadeset pet načinadodijeli dežurnu klasu za danas.
Pravilo množenja
Pravilo množenja također pripada osnovnim formulama kombinatorike. Počnimo s teorijom. Pretpostavimo da trebamo izvršiti nekoliko radnji (a): prva radnja se izvodi na 1 način, druga - na 2 načina, treća - na 3 načina, i tako sve dok se posljednja a-radnja ne izvodi na sa načina. Tada se sve ove radnje (kojih imamo ukupno) mogu izvesti na N načina. Kako izračunati nepoznato N? Formula će nam pomoći u tome: N \u003d c1c2c3…ca.
Opet, ništa nije jasno u teoriji, prijeđimo na jednostavan primjer primjene pravila množenja. Uzmimo isti razred od dvadeset i pet ljudi, u kojem uči petnaest djevojaka i deset dječaka. Samo ovaj put trebamo izabrati dva pratitelja. Mogu biti ili samo dječaci ili djevojčice, ili dječak s djevojčicom. Okrećemo se elementarnom rješenju problema. Odaberemo prvog pratitelja, kao što smo odlučili u prošlom paragrafu, dobivamo dvadeset i pet mogućih opcija. Druga dežurna osoba može biti bilo koja od preostalih osoba. Imali smo dvadeset i pet učenika, izabrali smo jednog, što znači da bilo tko od preostalih dvadeset i četiri osobe može biti drugi dežurni. Konačno, primjenjujemo pravilo množenja i nalazimo da se dva pratioca mogu izabrati na šest stotina načina. Dobili smo ovaj broj množenjem dvadeset pet i dvadeset četiri.
Zamijeni
Sada ćemo razmotriti još jednu kombinatoričku formulu. U ovom dijelu članka, miRazgovarajmo o permutacijama. Razmotrite problem odmah na primjeru. Uzmimo bilijarske kugle, imamo ih n-ti broj. Moramo izračunati: koliko postoji opcija da ih poredamo u red, odnosno da napravimo naručeni skup.
Počnimo, ako nemamo lopte, onda imamo i nula mogućnosti plasmana. A ako imamo jednu kuglicu, onda je i raspored isti (matematički, to se može napisati na sljedeći način: R1=1). Dvije kuglice mogu se poredati na dva različita načina: 1, 2 i 2, 1. Dakle, R2=2. Tri kuglice mogu se poredati na šest načina (R3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. A ako ne postoje tri takve kuglice, nego deset ili petnaest? Nabrajati sve moguće opcije je jako dugo, tada nam u pomoć dolazi kombinatorika. Formula permutacije pomoći će nam pronaći odgovor na naše pitanje. Pn=nP(n-1). Ako pokušamo pojednostaviti formulu, dobivamo: Pn=n (n - 1) … 21. A ovo je umnožak prvih prirodnih brojeva. Takav broj naziva se faktorijel i označava se kao n!
Razmotrimo problem. Vođa svakog jutra gradi svoj odred u nizu (dvadeset ljudi). U odredu su tri najbolja prijatelja - Kostya, Sasha i Lesha. Kolika je vjerojatnost da će biti jedno do drugog? Da biste pronašli odgovor na pitanje, trebate podijeliti vjerojatnost "dobrog" ishoda s ukupnim brojem ishoda. Ukupan broj permutacija je 20!=2,5 kvintilijuna. Kako izbrojati broj "dobrih" ishoda? Pretpostavimo da su Kostya, Sasha i Lesha jedan superman. Onda miImamo samo osamnaest predmeta. Broj permutacija u ovom slučaju je 18=6,5 kvadrilijuna. Uz sve to, Kostya, Sasha i Lesha mogu se proizvoljno kretati među sobom u svojoj nedjeljivoj trojci, a ovo je još 3!=6 opcija. Dakle, imamo ukupno 18 "dobrih" sazviježđa!3! Moramo samo pronaći željenu vjerojatnost: (18!3!) / 20! Što je otprilike 0,016. Ako se pretvori u postotak, ispada samo 1,6%.
Smještaj
Sada ćemo razmotriti još jednu vrlo važnu i potrebnu kombinatoričku formulu. Smještaj je naše sljedeće pitanje, koje predlažemo da razmotrite u ovom dijelu članka. Zakomplicirat ćemo. Pretpostavimo da želimo razmotriti moguće permutacije, samo ne iz cijelog skupa (n), već iz manjeg (m). To jest, razmatramo permutacije n stavki po m.
Osnovne formule kombinatorike ne treba samo zapamtiti, već i razumjeti. Čak i unatoč činjenici da postaju složeniji, budući da nemamo jedan parametar, već dva. Pretpostavimo da je m=1, zatim A=1, m \u003d 2, zatim A=n(n - 1). Ako dodatno pojednostavimo formulu i prijeđemo na zapis pomoću faktorijala, dobit ćemo prilično sažetu formulu: A \u003d n! / (n - m)!
Kombinacija
Razmotrili smo gotovo sve osnovne formule kombinatorike s primjerima. A sada prijeđimo na završnu fazu razmatranja osnovnog tečaja kombinatorike – upoznavanje kombinacije. Sada ćemo odabrati m stavki od n koje imamo, dok ćemo ih sve odabrati na sve moguće načine. Po čemu se to onda razlikuje od smještaja? Nećemorazmotriti red. Ovaj neuređeni skup bit će kombinacija.
Odmah uvedite oznaku: C. Uzimamo položaje m loptica iz n. Prestajemo paziti na red i dobivamo ponavljajuće kombinacije. Da bismo dobili broj kombinacija, broj plasmana trebamo podijeliti s m! (m faktorijal). To jest, C \u003d A / m! Dakle, postoji nekoliko načina za odabir između n loptica, približno jednako koliko odabrati gotovo sve. Za to postoji logičan izraz: izabrati malo je isto što i baciti gotovo sve. Također je važno spomenuti da se najveći broj kombinacija može postići kada se pokuša odabrati polovicu stavki.
Kako odabrati formulu za rješavanje problema?
Detaljno smo ispitali osnovne formule kombinatorike: postavljanje, permutaciju i kombinaciju. Sada je naš zadatak olakšati izbor potrebne formule za rješavanje problema u kombinatorici. Možete koristiti sljedeću prilično jednostavnu shemu:
- Zapitajte se: uzima li se u obzir redoslijed elemenata u tekstu problema?
- Ako je odgovor ne, upotrijebite formulu kombinacije (C=n! / (m!(n - m)!)).
- Ako je odgovor ne, onda morate odgovoriti na još jedno pitanje: jesu li svi elementi uključeni u kombinaciju?
- Ako je odgovor potvrdan, upotrijebite formulu permutacije (P=n!).
- Ako je odgovor ne, upotrijebite formulu za dodjelu (A=n! / (n - m)!).
Primjer
Razmatrali smo elemente kombinatorike, formule i neka druga pitanja. Sada idemo nas obzirom na stvarni problem. Zamislite da imate kivi, naranču i bananu ispred sebe.
Pitanje prvo: na koliko se načina mogu preurediti? Da bismo to učinili, koristimo formulu permutacije: P=3!=6 načina.
Drugo pitanje: na koliko načina se može odabrati jedno voće? To je očito, imamo samo tri mogućnosti - odaberite kivi, naranču ili bananu, ali primjenjujemo formulu kombinacije: C \u003d 3! / (2!1!)=3.
Pitanje treće: na koliko načina se mogu odabrati dva voća? Koje opcije imamo? Kivi i naranča; kivi i banana; naranče i banane. Odnosno, tri opcije, ali to je lako provjeriti kombinacijom formule: C \u003d 3! / (1!2!)=3
Četvrto pitanje: na koliko načina se mogu odabrati tri voća? Kao što vidite, postoji samo jedan način da odaberete tri voća: uzmite kivi, naranču i bananu. C=3! / (0!3!)=1.
Pitanje pet: na koliko načina možete odabrati barem jedno voće? Ovo stanje podrazumijeva da možemo uzeti jedan, dva ili sva tri ploda. Stoga dodajemo C1 + C2 + C3=3 + 3 + 1=7. To jest, imamo sedam načina da uzmemo barem jedan komad voća sa stola.
