Osnovne formule kombinatorike. Kombinatorika: formula za permutacijo, umestitev

V tem članku bomo razpravljali o posebnem delu matematike, imenovane kombinatorika. Formule, pravila, primeri reševanja problemov - vse to lahko najdete tukaj, po branju članka do konca.

Torej, kakšen je ta razdelek? Kombinatorika obravnava vprašanje štetja predmetov. Toda v tem primeru predmeti niso slive, hruške ali jabolka, ampak nekaj drugega. Combinatorics nam pomaga najti verjetnost dogodka. Na primer, ko igrate karte - kakšna je verjetnost, da ima nasprotnik adut? Ali primer - kakšna je verjetnost, da boste dobili vrečko iz vreče z dvajsetimi kroglicami? Za takšne probleme moramo vedeti vsaj osnove tega dela matematike.

Kombinatorske konfiguracije

Glede vprašanja osnovnih pojmov in formul kombinatorike pa ne moremo posvetiti pozornosti kombiniranim konfiguracijam. Uporabljajo se ne samo za besedilo, temveč tudi za reševanje različnih kombinatorne težave. Primeri takšnih modelov so:

• nastanitev;
• permutacija;
• kombinacija;
• sestava številke;
• razdelitev številke.

O prvih treh bomo podrobneje govorili kasneje, vendar bomo v tem razdelku pozorni na skladbe in particije. Ko govorimo o sestavi določenega števila (npr. A), potem mislimo na predstavitev števila a v obliki urejene vsote določenih pozitivnih števil. Razcepitev je neurejena količina.

Sekcije

Preden gremo neposredno v kombinatorične formule in pri obravnavi problemov, je vredno posvetiti pozornost dejstvu, da ima kombinatorika, tako kot druga področja matematike, tudi svoje podsekcije. Te vključujejo:

• enumerativno;
• strukturni;
• ekstremno;
• Ramseyova teorija;
• verjetnostna;
• topološki;
• Infinacionalno.

V prvem primeru govorimo o izračunavanju kombinatorike, težave pa obravnavajo štetje ali štetje različnih konfiguracij, ki jih tvorijo elementi množic. Praviloma se na teh sklopih naložijo morebitne omejitve (razlikovalnost, neenotnost, možnost ponovitve in tako naprej). In število teh konfiguracij se izračuna z uporabo pravila dodajanja ali množenja, o katerem bomo govorili malo kasneje. Teorije grafov in matroidov so strukturne kombinatorike. Primer problema ekstremne kombinatorike je tista največja dimenzija grafa, ki izpolnjuje naslednje lastnosti hellipa. V četrtem odstavku smo omenili teorijo Ramseyja, ki proučuje naključne konfiguracije rednih struktur. Verjetnostna kombinatorika je sposobna odgovoriti na vprašanje - kakšna je verjetnost, da ima določen niz določeno lastnost. Ni težko uganiti, da topološki kombinatoriki uporabljajo metode topologije. In končno, sedma točka - infinitrična kombinatorika - proučuje uporabo kombinatorskih metod v neskončnih sklopih.

Pravilo dodatka

Med formulami kombinatorike lahko najdemo precej preproste, s katerimi smo že dolgo poznani. Primer je pravilo vsote. Recimo, da smo imeli na voljo dve korake (C in E), če so med seboj izključujejo, je v veljavi od izvedljivo na več načinov (npr), in učinek E izvedljivo b-načinov, da se v skladu s katerim koli od njih (C ali E) so lahko a + b načinov .

V teoriji je to težko razumeti, poskušamo celotno točko posredovati na preprost nazor. Vzemimo povprečno število učencev enega razreda - recimo, petindvajset. Med njimi je petnajst deklet in deset fantov. Vsak dan v razredu je dodeljena ena oseba na dolžnosti. Koliko načinov za imenovanje dežurstva danes? Rešitev problema je precej preprosta, zatekamo k dodatnemu pravilu. Besedilo problema ne pravi, da so lahko samo dečki ali dekleta na službi. Posledično so lahko katerikoli od petnajst deklet ali kateri od desetih fantov. S pravili vsote dobimo precej preprost primer, s katerim lahko osnovnošolski učitelj zlahka spopade: 15 + 10. Po štetju dobimo odgovor: petindvajset. To pomeni, da obstaja samo petindvajset načinov za imenovanje službenega razreda za danes.

Pravilo množenja

Pravilo množenja velja za osnovne formule kombinatorike. Začnimo s teorijo. Na primer, moramo izvajati več dejanj (a): prvi ukrep se izvaja na 1 načine, drugi v c2 načinih, tretji z metodami c3 in tako naprej, dokler se ne izvede zadnja a-dejanja na enak način. Potem se vsa ta dejanja (od katerih imamo vsi a) lahko izvedemo na N načinih. Kako izračunati neznano N? Pri tem bomo pomagala formula: N = c1 * c2 * c3 * hellip- * sa.

Torej, v teoriji nič ni jasno, se obračamo na preprost primer uporabe pravila množenja. Vzemimo isti razred petindvajsetih ljudi, v katerem študira petnajst deklet in deset fantov. Samo tokrat moramo izbrati dve osebi na službi. Lahko so takoj kot fantje ali dekleta in fant z dekletom. Nadaljujemo z osnovno rešitev problema. Izberemo prvo dežurno osebo, kot smo se odločili v zadnjem odstavku, dobimo petindvajset možnih možnosti. Druga oseba na delu je lahko katera koli od preostalih ljudi. Imeli smo petindvajset študentov, tistega, ki smo ga izbrali, zato je lahko druga oseba na delu katera koli od preostalih 24 ljudi. Nazadnje, uporabimo pravilo množenja in ugotovimo, da sta lahko dva člana na položaju izvoljena na šeststo načinov. To število smo pomnožili z dvainpetdesetimi in štiriindvajsetimi.

Preurejanje

Zdaj bomo preučili še eno formulo kombinatorike. V tem delu članka bomo govorili o permutacijah. Problem takoj preučite z zgledom. Vzemi biljardne kroglice, imava svojo n-ti številko. Izračunati moramo: koliko možnosti jih moramo urediti v zaporedju, torej sestaviti naročeni niz.

Začnimo, če nimamo kroglic, potem imamo enake različice dogovora kot nič. In če imamo eno kroglo, potem je dogovor enak (matematično lahko to napišemo takole: P1 = 1). Dve krogli lahko postavite na dva različna načina: 1,2 in 2,1. Posledično je P2 = 2. Tri krogle je mogoče razvrstiti na šest načinov (P3 = 6): 1,2,3-1,3,2-2,1,3-2,3,1-3,2,1-3 , 1.2. In če ni treh takih kroglic, ampak deset ali petnajst? Poiščite vse možne možnosti za zelo dolgo časa, nato pa prihajamo do reševalne kombinatorike. Formula permutacije nam bo pomagal najti odgovor na vprašanje, ki nas zanima. Pn = n * P (n-1). Če skušamo poenostaviti formulo, dobimo: Pn = n * (n - 1) * hellip- * 2 * 1 To je produkt prvih pozitivnih celih števil. Takšna številka se imenuje faktorial, označena kot n!

Razmislite o problemu. Vodja vsako jutro gradi svojo ekipo v vrsti (dvajset ljudi). Oddelek ima tri najboljše prijatelje - Kostya, Sasha in Lesha. Kakšna je verjetnost, da bodo stali ob strani? Če želite najti odgovor na vprašanje, je verjetnost "dobrega" rezultata razdeliti na skupno število rezultatov. Skupno število permutacij je 20! = 2,5 kvintiliona. Kako izračunati število "dobrih" rezultatov? Recimo, da sta Kostya, Sasha in Lesha en superman. Potem imamo samo osemnajst predmetov. Število permutacij v tem primeru je 18 = 6,5 kvadrillionov. S tem se lahko Kostya, Sasha in Lesha samovoljno premikajo med seboj v svojih nedeljivih treh, to je 3! = 6 možnosti. Tako imamo samo 18 "dobrih" ureditev! * 3! Zahtevano verjetnost najdemo le: (18! * 3!) / 20! Kar je enako 0,016. Če prevedete v odstotek, se izkaže le za 1,6%.

Nastanitev

Zdaj bomo obravnavali še eno zelo pomembno in potrebno kombinacijsko formulo. Namestitev je naše naslednje vprašanje, ki vam predlagamo, da upoštevate v tem razdelku članka. Gre za zapletene stvari. Recimo, da želimo preučiti morebitne permutacije, ne le iz celotnega niza (n), temveč tudi iz manjšega (m). To pomeni, da bomo v percepciji n objektov upoštevali permutacije n.

Osnovne formule kombinatorike niso le učenje, temveč tudi razumevanje. Tudi kljub temu, da so zapleteni, ker nimamo enega parametra, temveč dva. Predpostavimo, da je m = 1, potem A = 1, m = 2, potem A = n * (n - 1). Če še dodatno poenostavimo formulo in gremo v zapis s pomočjo faktorialov, potem dobimo popolnoma jedrnato formulo: A = n! / (n-m)!

Kombinacija

S primeri smo obravnavali skoraj vse osnovne formule kombinatorike. Zdaj bomo prešli v zaključno fazo obravnave osnovnega tečaja kombinatorike - seznanitev s kombinacijo. Sedaj bomo izbrali m postavke iz naše obstoječe n, medtem ko bomo vse izbrali z vsemi možnimi sredstvi. Kaj se potem razlikuje od umestitve? Ne bomo upoštevali naročila. Ta neurejen niz bo kombinacija.

Takoj vnesemo zapis: C. Vzamemo m-kroglice n. Prenehamo posvečati pozornost naročilu in ponoviti kombinacije. Da bi dobili število kombinacij, moramo število umestitev razdeliti z m! (m faktor). To pomeni, da je C = A / m! Tako so načini izbire n kroglic malo, je približno toliko kot izbiro skoraj vsega. To je logični izraz: da bi nekoliko izbrali, da bi skoraj vse izpustili. Tudi v tem odstavku je pomembno omeniti, da je največje število kombinacij mogoče doseči, ko poskušate izbrati polovico postavk.

Kako izbrati formulo za reševanje problema?

Podrobno smo pregledali osnovne formule kombinatorike: postavitev, permutacijo in kombinacijo. Zdaj je naša naloga olajšati izbor potrebne formule za reševanje problema kombinatorike. Uporabljamo lahko precej preprosto shemo:

1. Vprašajte se, ali se v besedilu naloga upošteva vrstni red postavitve elementov?
2. Če je odgovor ne, uporabite kombinacijsko formulo (C = n! / (M! * (N-m)!)).
3. Če ni odgovora, je potrebno odgovoriti na še eno vprašanje: ali so vsi elementi vključeni v kombinacijo?
4. Če je odgovor pritrdilen, uporabite obliko permutacije (P = n!).
5. Če je odgovor ne, uporabite formulo umestitve (A = n! / (N-m)!).

Primer:

Preučili smo elemente kombinatorike, formul in nekaj drugih vprašanj. Zdaj se obrnemo na pravi problem. Predstavljajte si to, preden položite kivije, oranžne in banane.

Prvo vprašanje: kako jih je mogoče preurediti? Za to uporabimo formulo permutacije: P = 3! = 6 načinov.

Drugo vprašanje: koliko načinov lahko izberem eno sadje? To je očitno, imamo samo tri možnosti - izbrati kivi, pomaranče ali banane, vendar uporabimo formulo kombinacij: C = 3! / (2! * 1!) = 3.

Vprašanje tri: koliko načinov lahko izberete dve plodovi? Kakšne možnosti imamo na splošno? Kiwi in pomarančni kivi ter banana-oranžna in banana. To pomeni tri možnosti, vendar je enostavno preveriti z uporabo kombinacijske formule: C = 3! / (1! * 2!) = 3

Četrto vprašanje: koliko načinov lahko izberete tri plodove? Očitno lahko na eni strani izberete tri plodove: vzemite kivi, pomaranče in banane. C = 3! / (0! * 3!) = 1.

Vprašanje pet: koliko načinov lahko izberem vsaj eno sadje? Ta pogoj pomeni, da lahko vzamemo eno, dve ali vsa tri plodove. Zato dodamo C1 + C2 + C3 = 3 + 3 + 1 = 7. To pomeni, da imamo sedem načinov, da iz tabele vzamemo vsaj eno sadje.