Osnovne formule kombinatorika. Kombinatorika: formula za permutaciju, plasman

U ovom članku ćemo razgovarati o posebnom dijelu matematike nazvanu combinatorics. Formule, pravila, primjeri rješavanja problema - sve to možete pronaći ovdje, nakon čitanja članka do samog kraja.

Dakle, što je ovo odjeljak? Combinatorics se bavi pitanjem računanja bilo kojeg objekta. Ali u ovom slučaju objekti nisu šljive, kruške ili jabuke, već nešto drugo. Combinatorics nam pomaže pronaći vjerojatnost događaja. Na primjer, kada igrate karte - koja je vjerojatnost da protivnik ima adut? Ili primjer - koja je vjerojatnost da ćete dobiti bijelu vrećicu iz vrećice s dvadeset kuglica? Za takve probleme moramo znati barem osnove ovog dijela matematike.

Kombinatorne konfiguracije

S obzirom na pitanje osnovnih pojmova i formula kombinatorika, ne možemo obratiti pažnju na kombinacijske konfiguracije. Koriste se ne samo za tekst, nego i za rješavanje različitih kombinatorni problemi. Primjeri takvih modela su:

• smještaj;
• permutacija;
• kombinacija;
• sastav broja;
• raspodjela broja.

O prva tri, kasnije ćemo razgovarati detaljnije, ali ćemo obratiti pozornost na kompozicije i particiju u ovom odjeljku. Kad netko govori o sastavu određenog broja (recimo, a), tada mislimo na prikaz broja a u obliku naredbe zbroja određenih pozitivnih brojeva. Razdvajanje je neuredan iznos.

Sekcije

Prije nego što prijeđemo izravno na formule kombinatorike i razmatranje problema, vrijedno je obratiti pažnju na činjenicu da kombinatorika, kao i druge grane matematike, ima svoje vlastite pododjeljke. To uključuje:

• enumerative;
• strukturne;
• ekstremno;
• Ramseyova teorija;
• vjerojatnosti;
• topološki;
• infinitary.

U prvom slučaju govorimo o izračunavanju combinatorika, problemi uzimaju u obzir popisivanje ili brojanje različitih konfiguracija koje se formiraju elementima skupova. U pravilu se nameću sva ograničenja na ovim setovima (razlikovnost, nerazlučivost, mogućnost ponavljanja i tako dalje). A broj tih konfiguracija izračunava se pomoću pravila dodavanja ili množenja, o kojima ćemo pričati malo kasnije. Teorije grafikona i matroida su strukturna kombinatorika. Primjer problema ekstremnih kombinatorika - što je najveća dimenzija grafikona, koji zadovoljava sljedeće svoystvamhellip- U četvrtom odlomku spomenutu teoriju Ramsay, koji proučava u prisustvu slučajnih konfiguracije redovitih struktura. Probabilisticka combinatorika može odgovoriti na pitanje - koja je vjerojatnost da određeni skup ima određenu imovinu. Nije teško pogoditi da topološka kombinatorika primjenjuje metode u topologiji. Konačno, sedma točka - beskonačna kombinatorika - proučava primjenu kombinatornih metoda do beskonačnih skupova.

Pravilo za dodavanje

Među formulama combinatorika možemo naći prilično jednostavne, s kojima smo već poznavali. Primjer je pravilo zbroja. Pretpostavimo da smo dali dva koraka (C i E), ako su međusobno isključivi, na snazi ​​je od izvodljiv na nekoliko načina (npr), i učinku E izvodljiv B-načine, kako bi u skladu s bilo kojim od njih (C ili E) može biti A + B načina ,

Teoretski, to je teško razumjeti, pokušavamo prenijeti cijelu točku na jednostavan primjer. Uzmimo prosječan broj učenika jedne klase - recimo, dvadeset i pet. Među njima su petnaest djevojaka i deset dječaka. Svaki dan u klasi dodjeljuje se jedna osoba na dužnosti. Koliko je načina da danas imenuje dužnosnika? Rješenje problema je vrlo jednostavno, pribjegavamo pravilu dodavanja. Tekst problema ne kaže da samo dječaci ili djevojčice mogu biti na dužnosti. Posljedično, oni mogu biti bilo koja od petnaest djevojaka ili bilo kojeg od deset momaka. Primjenom pravila o zbroju dobivamo prilično jednostavan primjer, kojim se učenik osnovne škole lako može nositi: 15 + 10. Nakon brojanja dobivamo odgovor: dvadeset i pet. To jest, postoji samo dvadeset i pet načina za imenovanje dužničke klase za danas.

Pravilo umnožavanja

Pravilo umnožavanja odnosi se na osnovne formule kombinatorika. Počnimo s teorijom. Na primjer, moramo izvršiti nekoliko radnji (a): prva radnja se izvodi na jedan način, drugi na c2 načinima, treći s metodama c3 i tako dalje dok se posljednja a-akcija ne izvodi na isti način. Tada se sve ove akcije (od kojih svi imamo) mogu izvesti na N načine. Kako izračunati nepoznate N? U ovom će nam biti pomogla formula: N = c1 * c2 * c3 * hellip- * sa.

Opet, u teoriji ništa nije jasno, okrenimo se jednostavnom primjeru primjene pravila umnožavanja. Idemo na istu klasu dvadeset i pet ljudi, u kojima petnaest djevojaka i deset dečki proučavaju. Samo ovaj put moramo odabrati dvije osobe na dužnosti. Mogu biti čim dječaci ili djevojčice i dječak s djevojkom. Mi nastavljamo s elementarnom rješenjem problema. Prva osoba na dužnosti izabiremo, kao što smo odlučili u posljednjem odlomku, dobivamo dvadeset i pet mogućih opcija. Druga osoba na dužnosti može biti bilo koji od preostalih ljudi. Imali smo dvadeset i pet učenika, onaj kojeg smo izabrali, tako da druga osoba koja je bila na dužnosti mogla biti bilo koja od preostalih dvadeset četiri osobe. Konačno, primjenjujemo pravilo umnožavanja i utvrdimo da se dvoje ljudi na dužnosti mogu birati na šest stotina načina. Množili smo taj broj za dvadeset i pet i dvadeset četiri.

permutacija

Sada ćemo razmotriti još jednu formulu kombinatorika. U ovom dijelu članka govorimo o permutacijama. Odmah razmotrite problem s primjerom. Uzmi bilijarne kugle imamo n-ti broj. Moramo izračunati: koliko opcija ima za njih organizirati u redu, to jest, sastaviti naručeni set.

Počnimo, ako nemamo kugle, onda imamo iste varijante rasporeda kao nula. A ako imamo jednu kuglu, tada je aranžman isti (matematički to može biti napisano na sljedeći način: P1 = 1). Dvije se kuglice mogu postaviti na dva različita načina: 1,2 i 2,1. Prema tome, P2 = 2. Tri sfere mogu biti raspoređene na šest načina (P3 = 6): 1,2,3-1,3,2-2,1,3-2,3,1-3,2,1-3 , 1.2. A ako nema tri takve kugle, ali deset ili petnaest? Navesti sve moguće opcije za jako dugo vremena, a zatim dolazimo do kombinatorika za spašavanje. Permutacijska formula pomoći će nam pronaći odgovor na pitanje koje nas zanima. Pn = n * P (n-1). Ako pokušavamo pojednostaviti formulu, dobivamo: Pn = n * (n-1) * hellip- * 2 * 1. I to je proizvod prvog prirodnog broja. Takav se broj naziva faktorijalnim, a označava se kao n!

Razmislite o problemu. Voditelj svako jutro gradi svoju momčad u liniji (dvadesetak ljudi). Odvjetnik ima tri najbolja prijatelja - Kostya, Sasha i Lesha. Koja je vjerojatnost da će stajati uz rame? Da bi pronašli odgovor na pitanje, vjerojatnost "dobrog" ishoda treba podijeliti u ukupan broj ishoda. Ukupan broj permutacija je 20! = 2,5 kvintila. Kako izračunati broj "dobrih" ishoda? Pretpostavimo da su Kostya, Sasha i Lesha jedan nadljudac. Onda imamo tek osamnaest predmeta. Broj permutacija u ovom slučaju je 18 = 6,5 kvadrilijuna. Uz sve to, Kostya, Sasha i Lesha se mogu samostalno kretati među sobom u svojim nedjeljivim tri, a to je 3! = 6 opcija. Dakle imamo samo 18 "dobrih" aranžmana! * 3! Možemo pronaći samo potrebnu vjerojatnost: (18! * 3!) / 20! Što je približno 0,016. Ako prevodite u postotak, ispada samo 1,6%.

plasman

Sada ćemo razmotriti još jednu vrlo važnu i neophodnu formulu kombinatorika. Položaj je naša sljedeća pitanje, koju predlažemo da razmotrite u ovom odjeljku članka. Složit ćemo stvari. Pretpostavimo da želimo uzeti u obzir moguće permutacije, samo ne iz cijelog skupa (n), već od manjih (m). To jest, smatramo permutacijama n objekata u m.

Osnovne formule kombinatorika nisu samo učenje nego i njihovo razumijevanje. Čak i unatoč činjenici da su komplicirani jer nemamo jedan parametar, već dva. Pretpostavimo da m = 1, tada A = 1, m = 2, tada A = n * (n - 1). Ako dodatno pojednostavnimo formulu i idemo na snimanje uz pomoć faktorijala, dobivamo potpuno složenu formulu: A = n! / (n-m)!

kombinacija

Razmatrali smo gotovo sve osnovne formule kombinatorika s primjerima. Sada ćemo proći do završne faze razmatranja osnovnog tijeka kombinatorike - poznanstva s kombinacijom. Sada ćemo odabrati m stavke iz našeg postojećeg n, dok ćemo sve odabrati sa svim mogućim sredstvima. Što je onda drugačije od položaja? Nećemo uzeti u obzir red. Ovaj neuredni set bit će kombinacija.

Odmah smo predstavili zapis: C. Uzimamo plasman m loptica od n. Prestanemo obratiti pozornost na red i dobiti ponovljene kombinacije. Da biste dobili broj kombinacija, moramo podijeliti broj položaja m! (m faktor). To jest, C = A / m! Dakle, načine odabira n-kuglica malo je jednako kao i odabir gotovo sve. Ovo je logičan izraz: odabrati nešto malo toga, da baciti gotovo sve. Čak iu ovom stavku važno je napomenuti da se maksimalni broj kombinacija može postići kada pokušavate odabrati polovicu stavki.

Kako odabrati formulu za rješavanje problema?

Detaljno smo ispitali osnovne formule kombinatorika: položaj, permutacija i kombinacija. Sada nam je zadatak olakšati odabir potrebne formule za rješavanje problema kombinatorika. Možemo koristiti sljedeću jednostavnu shemu:

1. Zapitajte se na pitanje: redoslijed stavljanja elemenata uzima se u obzir u tekstu zadatka?
2. Ako je odgovor ne, upotrijebite kombinacijsku formulu (C = n! / (M! * (N-m)!)).
3. Ako nema odgovora, potrebno je odgovoriti na još jedno pitanje: jesu li svi elementi uključeni u kombinaciju?
4. Ako je odgovor pozitivan, upotrijebite permutacijsku formulu (P = n!).
5. Ako je odgovor ne, upotrijebite formulu plasmana (A = n! / (N-m)!).

primjer

Pregledali smo elemente kombinatorika, formula i neka druga pitanja. Sada se obraćamo pravi problem. Zamislite to prije nego što stavi kivi, naranče i bananu.

Prvo pitanje: koliko se načina mogu preurediti? Da bismo to učinili, koristimo permutationsku formulu: P = 3! = 6 načina.

Pitanje dva: koliko načina mogu odabrati jedan plod? To je očito, imamo samo tri mogućnosti - odabir kivija, naranče ili banane, ali primjenjuju se formula kombinacija: C = 3! / (2! * 1!) = 3.

Pitanje tri: koliko načina možete odabrati dva ploda? Koje opcije imamo općenito? Kiwi i narančasti kivi i banana-narančasta i banana. To jest, tri opcije, no lako je provjeriti pomoću kombinacijske formule: C = 3! / (L! * 2!) = 3

Četvrti pitanje: koliko načina možete odabrati tri ploda? Očigledno, možete odabrati tri voća na jedan način: uzmite kiwi, narančastu i bananu. C = 3! / (0! * 3!) = 1.

Pitanje pet: koliko načina mogu odabrati barem jedan plod? Ovo stanje znači da možemo uzeti jedno, dva ili sva tri ploda. Dakle, dodamo C1 + C2 + C3 = 3 + 3 + 1 = 7. To jest, imamo sedam načina da se iz tablice barem jedan plod.