Ta članek se bo osredotočil na poseben del matematike, imenovan kombinatorika. Formule, pravila, primeri reševanja problemov - vse to najdete tukaj, tako da preberete članek do konca.
Torej, kaj je ta razdelek? Kombinatorika se ukvarja z vprašanjem štetja kakršnih koli predmetov. A v tem primeru predmeti niso slive, hruške ali jabolka, ampak nekaj drugega. Kombinatorika nam pomaga najti verjetnost dogodka. Kolikšna je na primer verjetnost, da ima nasprotnik adut pri igranju kart? Ali pa tak primer – kakšna je verjetnost, da boste iz vrečke z dvajsetimi kroglicami dobili ravno belo? Za tovrstne naloge moramo poznati vsaj osnove tega odseka matematike.
Kombinatorne konfiguracije
Glede na problematiko osnovnih konceptov in formul kombinatorike, ne moremo le biti pozorni na kombinatorične konfiguracije. Uporabljajo se ne samo za formulacijo, ampak tudi za reševanje različnih kombinatornih problemov. Primeri takšnih modelov so:
- umestitev;
- permutacija;
- kombinacija;
- številčna sestava;
- razdeljena številka.
O prvih treh bomo podrobneje govorili kasneje, vendar bomo v tem razdelku pozorni na kompozicijo in razdelitev. Ko govorijo o sestavi določenega števila (recimo a), mislijo na prikaz števila a kot urejene vsote nekaterih pozitivnih števil. In delitev je neurejena vsota.
razdelki
Preden gremo neposredno na formule kombinatorike in obravnavo problemov, je vredno biti pozoren na dejstvo, da ima kombinatorika, tako kot drugi deli matematike, svoje pododdelke. Ti vključujejo:
- naštevanje;
- strukturno;
- ekstremno;
- Ramseyeva teorija;
- verjetna;
- topološki;
- neskončno.
V prvem primeru govorimo o enumerativni kombinatoriki, problemi obravnavajo naštevanje oziroma štetje različnih konfiguracij, ki jih tvorijo elementi množic. Za te sklope so praviloma določene omejitve (razločljivost, neločljivost, možnost ponovitve itd.). In število teh konfiguracij se izračuna z uporabo pravila seštevanja ali množenja, o katerem bomo govorili malo kasneje. Strukturna kombinatorika vključuje teorije grafov in matroidov. Primer problema ekstremne kombinatorike je, katera je največja dimenzija grafa, ki izpolnjuje naslednje lastnosti… V četrtem odstavku smo omenili Ramseyevo teorijo, ki proučuje prisotnost regularnih struktur v naključnih konfiguracijah. Verjetnostnakombinatorika zna odgovoriti na vprašanje – kolikšna je verjetnost, da ima določena množica določeno lastnost. Kot lahko uganete, topološka kombinatorika uporablja metode v topologiji. In končno, sedma točka - neskončna kombinatorika proučuje uporabo kombinatoričnih metod za neskončne množice.
pravilo seštevanja
Med formulami kombinatorike najdemo precej preproste, ki jih poznamo že dolgo. Primer je pravilo vsote. Recimo, da imamo dve dejanji (C in E), če se med seboj izključujeta, lahko dejanje C izvedemo na več načinov (na primer a) in dejanje E lahko izvedemo na b-poteh, potem katero koli od njih (C ali E) se lahko izvede na načine a + b.
V teoriji je to precej težko razumeti, poskušali bomo celotno bistvo prenesti s preprostim primerom. Vzemimo povprečno število učencev v enem razredu – recimo, da je petindvajset. Med njimi je petnajst deklet in deset fantov. Vsak dan je v razred dodeljen en spremljevalec. Na koliko načinov je danes mogoče dodeliti spremljevalca razreda? Rešitev problema je precej preprosta, zatekli se bomo k pravilu seštevanja. Besedilo naloge ne pravi, da so lahko dežurni samo fantje ali samo dekleta. Zato je lahko katera od petnajstih deklet ali kateri koli od desetih fantov. Z uporabo pravila vsote dobimo dokaj preprost primer, s katerim se osnovnošolec zlahka spopade: 15 + 10. Po izračunu dobimo odgovor: petindvajset. Se pravi, obstaja le petindvajset načinovdodeli delovni razred za danes.
pravilo množenja
Pravilo množenja sodi tudi k osnovnim formulam kombinatorike. Začnimo s teorijo. Recimo, da moramo izvesti več dejanj (a): prvo dejanje se izvede na 1 način, drugo - na 2 načina, tretje - na 3 načine in tako naprej, dokler se zadnje dejanje a ne izvede na sa načine. Nato lahko vsa ta dejanja (ki jih imamo skupaj) izvedemo na N načinov. Kako izračunati neznano N? Pri tem nam bo pomagala formula: N \u003d c1c2c3…ca.
Spet v teoriji ni nič jasno, pojdimo na preprost primer uporabe pravila množenja. Vzemimo isti razred petindvajsetih ljudi, v katerem študira petnajst deklet in deset fantov. Le tokrat moramo izbrati dva spremljevalca. Lahko so samo fantje ali dekleta ali pa fant z deklico. Obrnemo se na osnovno rešitev problema. Izberemo prvega spremljevalca, kot smo se odločili v zadnjem odstavku, dobimo petindvajset možnih možnosti. Druga dežurna oseba je lahko katera koli od preostalih oseb. Imeli smo petindvajset učencev, izbrali smo enega, kar pomeni, da je lahko kateri koli od preostalih štiriindvajsetih drugi dežurni. Na koncu uporabimo pravilo množenja in ugotovimo, da je spremljevalca mogoče izbrati na šeststo načinov. To število smo dobili tako, da pomnožimo petindvajset in štiriindvajset.
Zamenjaj
Sedaj bomo obravnavali še eno kombinatorično formulo. V tem razdelku članka smoPogovorimo se o permutacijah. Takoj razmislite o problemu s primerom. Vzemimo biljardne krogle, imamo jih n-to število. Izračunati moramo: koliko možnosti je, da jih razporedimo v vrsto, torej da naredimo urejen niz.
Začnimo, če nimamo žogic, potem imamo tudi nič možnosti umestitve. In če imamo eno kroglo, potem je tudi razporeditev enaka (matematično lahko to zapišemo takole: Р1=1). Dve kroglici lahko razporedimo na dva različna načina: 1, 2 in 2, 1. Torej je Р2=2. Tri kroglice lahko razporedimo na šest načinov (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. In če takšnih kroglic niso tri, ampak deset ali petnajst? Naštevanje vseh možnih možnosti je zelo dolgo, potem nam na pomoč priskoči kombinatorika. Formula permutacije nam bo pomagala najti odgovor na naše vprašanje. Pn=nP(n-1). Če poskušamo poenostaviti formulo, dobimo: Pn=n (n - 1) … 21. In to je produkt prvih naravnih števil. Takšno število se imenuje faktorial in je označeno kot n!
Razmislimo o težavi. Vodja vsako jutro zgradi svoj odred v vrsti (dvajset ljudi). V odredu so trije najboljši prijatelji - Kostya, Sasha in Lesha. Kakšna je verjetnost, da bosta drug ob drugem? Da bi našli odgovor na vprašanje, morate verjetnost »dobrega« izida deliti s skupnim številom izidov. Skupno število permutacij je 20!=2,5 kvintiljona. Kako prešteti število "dobrih" rezultatov? Recimo, da so Kostya, Sasha in Lesha en superman. Potem pa miImamo samo osemnajst predmetov. Število permutacij v tem primeru je 18=6,5 kvadrilijona. Ob vsem tem se lahko Kostya, Sasha in Lesha samovoljno premikajo med seboj v svoji nedeljivi trojki, to pa je še 3!=6 možnosti. Skupaj imamo torej 18 "dobrih" ozvezdij!3! Najti moramo le želeno verjetnost: (18!3!) / 20! Kar je približno 0,016. Če se pretvori v odstotek, se izkaže, da je le 1,6%.
Namestitev
Sedaj bomo obravnavali še eno zelo pomembno in potrebno kombinatorično formulo. Namestitev je naša naslednja tema, ki vam jo predlagamo, da razmislite v tem delu članka. Zakomplicirali bomo. Predpostavimo, da želimo upoštevati možne permutacije, le ne iz celotne množice (n), temveč iz manjšega (m). To pomeni, da upoštevamo permutacije n elementov z m.
Osnovnih formul kombinatorike ne bi smeli le zapomniti, ampak jih razumeti. Tudi kljub dejstvu, da postanejo bolj zapleteni, saj nimamo enega parametra, ampak dva. Recimo, da je m=1, nato A=1, m \u003d 2, nato A=n(n - 1). Če formulo še poenostavimo in preklopimo na zapis z uporabo faktorialov, dobimo precej jedrnato formulo: A \u003d n! / (n - m)!
kombinacija
Upoštevali smo skoraj vse osnovne formule kombinatorike s primeri. Zdaj pa preidimo na zadnjo fazo obravnave osnovnega poteka kombinatorike – spoznavanje kombinacije. Zdaj bomo izbrali m predmetov izmed n, ki jih imamo, medtem ko bomo vse izbrali na vse možne načine. Kako se potem to razlikuje od nastanitve? Ne bomoupoštevajte red. Ta neurejen niz bo kombinacija.
Takoj uvedite zapis: C. Iz n vzamemo umestitve m kroglic. Nehamo biti pozorni na vrstni red in dobimo ponavljajoče se kombinacije. Da bi dobili število kombinacij, moramo število umestitev deliti z m! (m faktorial). Se pravi, C \u003d A / m! Tako lahko izbirate med n kroglicami na nekaj načinov, ki so približno enaki kolikor želite izbrati skoraj vse. Za to obstaja logičen izraz: izbrati malo je enako kot zavreči skoraj vse. Na tej točki je prav tako pomembno omeniti, da je največje število kombinacij mogoče doseči, ko poskušate izbrati polovico predmetov.
Kako izbrati formulo za rešitev težave?
Podrobno smo preučili osnovne formule kombinatorike: umestitev, permutacija in kombinacija. Zdaj je naša naloga olajšati izbiro potrebne formule za reševanje problema v kombinatoriki. Uporabite lahko naslednjo precej preprosto shemo:
- Vprašajte se: ali je vrstni red elementov upoštevan v besedilu težave?
- Če je odgovor ne, potem uporabite formulo kombinacije (C=n! / (m!(n - m)!)).
- Če je odgovor ne, potem morate odgovoriti še na eno vprašanje: ali so vsi elementi vključeni v kombinacijo?
- Če je odgovor pritrdilen, potem uporabite permutacijsko formulo (P=n!).
- Če je odgovor ne, potem uporabite formulo za dodelitev (A=n! / (n - m)!).
Primer
Upoštevali smo elemente kombinatorike, formule in nekatera druga vprašanja. Zdaj pa pojdimo naprejob upoštevanju resničnega problema. Predstavljajte si, da imate pred seboj kivi, pomarančo in banano.
Prvo vprašanje: na koliko načinov jih je mogoče preurediti? Za to uporabimo permutacijsko formulo: P=3!=6 načinov.
Drugo vprašanje: na koliko načinov je mogoče izbrati eno sadje? To je očitno, imamo samo tri možnosti - izberite kivi, pomarančo ali banano, vendar uporabimo kombinacijo formule: C=3! / (2!1!)=3.
Tretje vprašanje: na koliko načinov je mogoče izbrati dva sadeža? Kakšne možnosti imamo? Kivi in pomaranča; kivi in banana; pomaranča in banana. Se pravi tri možnosti, vendar je to enostavno preveriti s kombinirano formulo: C \u003d 3! / (1!2!)=3
Četrto vprašanje: na koliko načinov je mogoče izbrati tri sadeže? Kot lahko vidite, obstaja samo en način, da izberete tri sadje: vzemite kivi, pomarančo in banano. C=3! / (0!3!)=1.
Peto vprašanje: na koliko načinov lahko izberete vsaj eno sadje? Ta pogoj pomeni, da lahko vzamemo enega, dva ali vse tri sadeže. Zato dodamo C1 + C2 + C3=3 + 3 + 1=7. To pomeni, da imamo sedem načinov, kako iz mize vzeti vsaj en kos sadja.
