Ovaj članak će se fokusirati 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.
Pa, koji je ovo odjeljak? Kombinatorika se bavi pitanjem brojanja bilo kojih objekata. Ali u ovom slučaju, predmeti nisu šljive, kruške ili jabuke, već nešto drugo. Kombinatorika nam pomaže da pronađemo vjerovatnoću događaja. Na primjer, pri kartanju, kolika je vjerovatnoća da protivnik ima adut? Ili takav primjer - kolika je vjerovatnoća da ćete iz vreće od dvadeset loptica dobiti baš bijelo? Za ovakvu vrstu zadataka moramo znati barem osnove ovog odsjeka matematike.
Kombinatorne konfiguracije
S obzirom na osnovne pojmove i formule kombinatorike, ne možemo a da ne obratimo pažnju na kombinatorne konfiguracije. Koriste se ne samo za formulaciju, već i za rješavanje raznih kombinatornih problema. Primjeri takvih modela su:
- placement;
- permutacija;
- kombinacija;
- sastav broja;
- podijeljeni broj.
O prva tri ćemo detaljnije govoriti kasnije, ali ćemo u ovom dijelu obratiti pažnju na kompoziciju i podjelu. Kada govore o sastavu određenog broja (recimo, a), misle na prikaz broja a kao uređenog zbira nekih pozitivnih brojeva. A podjela je neuređena suma.
Sekcije
Prije nego što pređemo direktno na formule kombinatorike i razmatranje problema, vrijedi obratiti pažnju na činjenicu da kombinatorika, kao i drugi dijelovi matematike, ima svoje pododjeljke. Ovo uključuje:
- enumerative;
- strukturno;
- extreme;
- Ramsey 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. Po pravilu se na ove skupove nameću određena ograničenja (različivost, nerazlučivost, mogućnost ponavljanja i sl.). 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 pasusu spomenuli smo Ramseyevu teoriju, koja proučava prisustvo regularnih struktura u slučajnim konfiguracijama. Probabilističkikombinatorika je u stanju da odgovori na pitanje - kolika je verovatnoća da dati skup ima određeno svojstvo. Kao što možete pretpostaviti, topološka kombinatorika primjenjuje metode u topologiji. I na kraju, sedma tačka - beskonačna kombinatorika proučava primenu kombinatoričkih metoda na beskonačne skupove.
Pravilo dodavanja
Među formulama kombinatorike mogu se naći sasvim jednostavne, sa kojima smo već dugo upoznati. Primjer je pravilo sume. Pretpostavimo da su nam date dvije akcije (C i E), ako se međusobno isključuju, akcija C se može izvršiti na nekoliko načina (na primjer, a), a akcija E može se izvršiti na b-načine, tada bilo koja od njih (C ili E) može se uraditi na a + b načine.
U teoriji, ovo je prilično teško razumjeti, pokušat ćemo prenijeti cijelu poentu jednostavnim primjerom. Uzmimo prosječan broj učenika u jednom odjeljenju – recimo da je dvadeset pet. Među njima je petnaest devojčica i deset deč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 samo dečaci ili samo devojčice. Dakle, to može biti bilo koja od petnaest djevojčica ili bilo koji od deset dječaka. Primjenom pravila zbira dobijamo prilično jednostavan primjer s kojim se učenik osnovne škole lako nosi: 15 + 10. Izračunavši, dobijamo odgovor: dvadeset pet. Odnosno, postoji samo dvadeset pet načinadodijeli dežurnu klasu za danas.
Pravilo množenja
Pravilo množenja takođe pripada osnovnim formulama kombinatorike. Počnimo s teorijom. Pretpostavimo da treba da izvršimo 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 poslednja a-akcija ne izvede na dva 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, pređimo na jednostavan primjer primjene pravila množenja. Uzmimo istu klasu od dvadeset i pet ljudi, u kojoj uči petnaest djevojaka i deset dječaka. Samo ovaj put trebamo izabrati dva pratioca. Mogu biti ili samo dječaci ili djevojčice, ili dječak sa djevojčicom. Okrećemo se elementarnom rješenju problema. Biramo prvog pratioca, kao što smo odlučili u prošlom pasusu, dobijamo dvadeset 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 ko od preostala dvadeset i četiri čovjeka 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.
Zamjena
Sada ćemo razmotriti još jednu kombinatoričku formulu. U ovom dijelu članka, miHajde da pričamo o permutacijama. Razmotrite problem odmah na primjeru. Uzmimo loptice za bilijar, imamo ih n-ti broj. Moramo izračunati: koliko ima opcija da ih rasporedimo u niz, odnosno da napravimo naručeni skup.
Počnimo, ako nemamo lopte, onda imamo i nulte mogućnosti plasmana. A ako imamo jednu loptu, onda je i raspored isti (matematički, ovo se može napisati na sljedeći način: R1=1). Dve lopte se mogu poredati na dva različita načina: 1, 2 i 2, 1. Dakle, R2=2. Tri kuglice se mogu rasporediti 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 lopte, već deset ili petnaest? Nabrajati sve moguće opcije je jako dugo, tada nam u pomoć dolazi kombinatorika. Formula permutacije će nam pomoći da pronađemo odgovor na naše pitanje. Pn=nP(n-1). Ako pokušamo da pojednostavimo formulu, dobićemo: Pn=n (n - 1) … 21. A ovo je proizvod prvih prirodnih brojeva. Takav broj se naziva faktorijel i označava se kao n!
Razmotrimo problem. Vođa svakog jutra gradi svoj odred u liniji (dvadeset ljudi). U odredu su tri najbolja prijatelja - Kostya, Sasha i Lesha. Kolika je vjerovatnoća da će biti jedno pored drugog? Da biste pronašli odgovor na pitanje, trebate podijeliti vjerovatnoću „dobrog“ishoda s ukupnim brojem ishoda. Ukupan broj permutacija je 20!=2,5 kvintiliona. Kako izbrojati broj "dobrih" ishoda? Pretpostavimo da su Kostja, Saša i Leša jedan supermen. Onda miImamo samo osamnaest predmeta. Broj permutacija u ovom slučaju je 18=6,5 kvadriliona. Uz sve ovo, 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“sazvežđa!3! Moramo samo pronaći željenu vjerovatnoću: (18!3!) / 20! Što je otprilike 0,016. Ako se pretvori u postotak, ispada da je 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. Postat ćemo još komplikovaniji. Pretpostavimo da želimo razmotriti moguće permutacije, samo ne iz cijelog skupa (n), već iz manjeg (m). To jest, razmatramo permutacije n stavki sa m.
Osnovne formule kombinatorike ne treba samo zapamtiti, već i razumjeti. Čak i uprkos činjenici da postaju komplikovanije, jer nemamo jedan parametar, već dva. Pretpostavimo da je m=1, zatim A=1, m=2, zatim A=n(n - 1). Ako dodatno pojednostavimo formulu i prijeđemo na notaciju pomoću faktorijala, dobićemo prilično sažetu formulu: A=n! / (n - m)!
Kombinacija
Razmotrili smo gotovo sve osnovne formule kombinatorike sa primjerima. Pređimo sada na završnu fazu razmatranja osnovnog kursa kombinatorike – upoznavanje kombinacije. Sada ćemo izabrati m stavki od n koje imamo, dok ćemo ih sve izabrati na sve moguće načine. Po čemu se to onda razlikuje od smještaja? Nećemorazmotriti red. Ovaj neuređeni set će biti kombinacija.
Odmah uvedite notaciju: C. Uzimamo plasmane m loptica iz n. Prestajemo obraćati pažnju na red i dobivamo kombinacije koje se ponavljaju. Da bismo dobili broj kombinacija, trebamo podijeliti broj plasmana sa m! (m faktorijel). To jest, C \u003d A / m! Dakle, postoji nekoliko načina da birate između n loptica, približno jednako koliko treba izabrati gotovo sve. Za ovo postoji logičan izraz: izabrati malo je isto što i baciti skoro sve. Također je važno napomenuti u ovom trenutku da se maksimalni 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 šemu:
- Zapitajte se: da li je redoslijed elemenata uzet u obzir u tekstu problema?
- Ako je odgovor ne, onda koristite formulu kombinacije (C=n! / (m!(n - m)!)).
- Ako je odgovor ne, onda morate odgovoriti na još jedno pitanje: da li su svi elementi uključeni u kombinaciju?
- Ako je odgovor da, onda koristite formulu permutacije (P=n!).
- Ako je odgovor ne, onda koristite formulu alokacije (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, pomorandžu i bananu ispred sebe.
Pitanje prvo: na koliko načina se mogu preurediti? Da bismo to učinili, koristimo formulu permutacije: P=3!=6 načina.
Pitanje drugo: na koliko načina se može izabrati jedno voće? Ovo je očito, imamo samo tri opcije - odaberite kivi, naranču ili bananu, ali primjenjujemo formulu kombinacije: C=3! / (2!1!)=3.
Pitanje treće: na koliko načina se mogu izabrati dva voća? Koje opcije imamo? Kivi i narandža; kivi i banana; pomorandž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 izabrati tri voća? Kao što vidite, postoji samo jedan način da odaberete tri voća: uzmite kivi, narandž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 jednu, dvije 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.
