Kombinatorika - osnovni pojmovi i formule s primjerima. Kombinatorika

Elementi kombinatorike

Kombinatorika je znanost o rasporedu elemenata u određeni red i brojanju načina takvog rasporeda.

Kombinatorni princip množenja Ako se jedan dio radnje može izvesti na više načina, a drugi na načine, tada se cijela radnja može izvesti na više načina.

Primjer. Recimo da trebate napraviti set olovaka, olovaka i ravnala. Dostupno:

5 različitih ručki,

7 različitih olovaka,

10 različitih linija.

Na koliko se načina može sastaviti traženi skup?

Riješenje. Radnja u ovom slučaju je napraviti set olovke, olovke i ravnala; Radnja je podijeljena u tri faze (dijela): odaberite olovku, odaberite ravnalo i odaberite olovku. Prvi dio radnje - biranje olovke - može se obaviti na pet načina, drugi dio radnje - biranje olovke - može se obaviti na sedam načina, treći dio radnje - biranje ravnala - može se obaviti. na deset načina. Tada se može izvesti cijela radnja

Broj načina. Oni. moguće je da postoji 350 varijanti ovog skupa.

Primjer. Koliko postoji skupova duljina nula i jedinica?

Riješenje. Radnja u ovom slučaju je sastaviti skup duljina od nula i jedinica.

Skup će biti dovršen ako su sve pozicije (mjesta) popunjene nulama i jedinicama. Radnja je podijeljena na dijelove: ispunite prvo mjesto, drugo itd., ispunite - y položaj. Prvi dio radnje - pisanje prve komponente - može se izvršiti na dva načina: možete napisati 0 ili možete napisati 1, također možete napisati drugu komponentu na dva načina, i tako dalje za sva mjesta u set: na svakom mjestu možete napisati 0 ili 1:

Tada se cijela operacija prema kombinatornom principu množenja može izvesti na više načina:

Kombinatorni princip zbrajanja. Ako se dvije radnje međusobno isključuju i jedna se od njih može izvesti na različite načine, a druga na različite načine, tada se obje radnje mogu izvesti na više načina.

Primjer.

Uzorkovanje volumen iz kompleta je bilo koji niz elemenata skupa.

Ako se elementi u izboru ne ponavljaju, tada se odabir poziva ponovljiv , inače - uzorkovanje s ponavljanjima

Kod uzorkovanja bez ponavljanja, nije važno kako se odabir vrši: svi elementi se uzimaju odjednom ili jedan po jedan (jedan po jedan).

Raspored elemenata odabira u određenom redoslijedu naziva se naručivanje , a uzorak se poziva uredno, inače - poremećen.

Razmotrite uzorkovanje koje se ne ponavlja

Raspored različitih elemenata određenim redoslijedom naziva se preuređenje bez ponavljanja od elemenata.

Na primjer, na skupu od tri elementa moguće su sljedeće permutacije: .

Broj različitih permutacija bez ponavljanja elemenata označava se s i jednak je , tj.

Kombinacija bez ponavljanja elemenata po naziva se neuređen - elementarni podskup - elementarnog skupa. Broj kombinacija bez ponavljanja elemenata jednak je:

Na primjer, trebate izračunati na koliko načina možete napraviti tim od troje ljudi koji će dežurati u grupi od 30 ljudi. Budući da poredak ljudi u brigadi nije je fiksna i ljudi se ne ponavljaju, tada imamo slučaj kombinacije 30 elemenata od 3 bez ponavljanja:

Tako se dežurni tim od tri osobe u grupi od 30 ljudi može odabrati na 4060 različitih načina.

Smještaj bez ponavljanja elemenata po naziva se uređen - elementarni podskup -elementnog skupa.

Teorema.

Broj postavljanja bez ponavljanja elemenata jednak je:

Dokaz. Da biste dobili uređeni -elementni podskup skupa -elementa, morate izvesti dva koraka: odabrati elemente iz (ovo se može učiniti na više načina) i zatim poredati odabrane elemente (ovo se može učiniti na više načina ). Prema kombinatornom principu množenja, cijela operacija dobivanja uređenog elementarnog podskupa elementarnog skupa može se izvesti na više načina.

Svojstva kombinacija bez ponavljanja :

Dokaz.Jer I , onda je ono što se tvrdi očito.

2) (nema dokaza).

Vrijednosti se ne mogu pronaći izračunavanjem formule broja kombinacija, već pomoću takozvanog Pascalovog trokuta. (Blaise Pascal (1623. – 1662.) – francuski matematičar).

Ovaj trokut izgleda ovako:

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

Uzorak njegove konstrukcije je sljedeći: zbrajanjem dva susjedna broja, dobivamo broj ispod između njih. Prvi red je broj kombinacija od 1 (), drugi red je od 2 (- s lijeva na desno), itd.

Razmotrite uzorak s ponavljanjima

Neka postoji izbor elemenata, a elementi iz njih su identični.

1. Broj različitih permutacija na elementima takvog uzorka jednak je:

- broj permutacija s ponavljanjima na skupu elemenata

2. Kombinacija s ponavljanjima iz elemenata pomoću - neuređenog odabira elemenata koji se vraćaju iz skupa koji sadrži elemente:

- broj različitih kombinacija s ponavljanjem elemenata prema

3. Postavljanje s ponavljanjem elemenata - rasporedom različitih loptica u različitim ćelijama

- broj različitih plasmana s ponavljanjima

Primjer . Koliko se različitih riječi od 4 slova može sastaviti od simbola?

Riješenje.Drugim riječima, potrebno je pronaći broj permutacija s ponavljanjima na 4 elementa uzorka u kojem su dva elementa ista:

Primjer . Koliko se različitih permutacija može napraviti od slova riječi ABAKAN?

Riješenje.Morate pronaći broj permutacija na skupu od 6 elemenata, među od kojih postoje tri elementa isti su:

.

Pravo generalizacija formula koja se razmatra: broj različitih permutacija na skupu elemenata, među kojima postoji

Elementi prve vrste,

Elementi druge vrste,

Elementi - vrsta

jednako:

Primjer. Koliko se permutacija može dobiti od slova riječi ZVONO?

Riješenje.Morate pronaći broj permutacija s ponavljanjima na skupu od 8 slova, među kojima su:

pismo K se ponavlja 2 puta;

pismo O se ponavlja 3 puta;

slovo L se ponavlja 2 puta

pismo I to se ponavlja 1 put.

Tako, .

Primjer. Na koliko se načina može napraviti komplet od 5 čokolada ako postoje tri vrste čokolada, po 10 svake vrste?

Riješenje.Budući da kod sastavljanja čokoladnog seta redoslijed čokolada nije bitan, za izračun koristimo formulu kombinacija s ponavljanjima:

Primjer. Na koliko se načina u 9 vagona može smjestiti 7 ljudi?

Riješenje.Budući da prema uvjetima zadatka u jednom vagonu može sjediti više osoba, a kako raspored sjedenja ovisi o tome tko je u kojem vagonu, koristimo formulu sjedenja s ponavljanjima:

Primjer. Na koliko se načina u 9 vagona može smjestiti 7 ljudi, po jedan u vagon?

Riješenje.Budući da prema uvjetima zadatka u jednom vagonu može sjediti samo jedna osoba, a kako raspored sjedenja ovisi o tome tko je u kojem vagonu, bez ponavljanja koristimo formulu sjedenja:

Isti problem može se riješiti primjenom kombinatornog principa množenja: radnja sjedenja 7 osoba podijeljena je u 7 faza: sjedenje prvog putnika, sjedenje drugog putnika, ..., sjedenje sedmog putnika. Prva faza - postavljanje prvog putnika na 9 načina, drugog putnika također na 9 načina itd. :

Primjer. Koliko se različitih signala može napraviti od četiri zastavice različitih boja, ako se svaki signal mora sastojati od najmanje dvije zastavice?

Riješenje. Možete stvoriti signal od dvije zastavice, od tri ili od četiri. Navedene situacije se međusobno isključuju (dvije zastavice nisu tri ili četiri), pa izračunajmo na koliko se načina može generirati signal u svakoj od navedenih situacija i zbrojimo rezultate.

Radnja sastavljanja signala podrazumijeva odabir zastavica od četiri i njihovo postavljanje određenim redoslijedom. Dakle, u svakom slučaju morate izvršiti dva koraka: prvi je odabir potvrdnih okvira, drugi je raspored odabranih potvrdnih okvira određenim redoslijedom.

Sastavljamo signale od dvije zastavice: možete odabrati dvije od četiri zastavice na različite načine, a odabrana dva potvrdna okvira možete rasporediti određenim redoslijedom na više načina. Dakle, prema kombinatornom principu množenja, moguće je stvoriti različite signale od dvije zastavice. načine. To znači da možete stvoriti različite signale od četiri zastavice.

Primijenimo sada kombinatorni princip zbrajanja: sve postoji signale s najmanje dvije zastavice.

Primjer. Broj automobila sastoji se od tri slova i tri broja. Koliko se različitih brojeva može sastaviti od 10 brojeva i abecede od 30 slova.

Očito je da je broj svih mogućih kombinacija 10 znamenki s 4 10 000.

Broj svih mogućih kombinacija od 30 slova po dva jednak je .

Ako uzmemo u obzir mogućnost ponavljanja slova, tada je broj kombinacija koje se ponavljaju 30 (jedna mogućnost ponavljanja za svako slovo). Ukupno, ukupan broj dvoslovnih kombinacija je 900.

Ako se broju doda još jedno slovo iz abecede od 30 slova, tada se broj kombinacija povećava 30 puta, tj. doseže 27 000 kombinacija.

Konačno, jer Svaka kombinacija slova može se povezati s brojčanom kombinacijom, tada je ukupan broj registarskih pločica 270.000.000.

Npr. Nikiforova

Razmotrimo problem brojanja uzoraka iz zadanog skupa u općem obliku. Neka bude neki set N, koja se sastoji od n elementi. Svaki podskup koji se sastoji od m elementi se mogu razmatrati ne uzimajući u obzir njihov redoslijed, ili uzimajući ga u obzir, tj. kada mijenjate redoslijed, prijeđite na drugi m– uzorkovanje.

Formulirajmo sljedeće definicije:

Plasmani bez ponavljanja

Postavljanje bez ponavljanjan elementi pom Nkoji sadržimraznih elemenata.

Iz definicije proizlazi da se dva rasporeda međusobno razlikuju, kako po elementima tako i po redoslijedu, čak i ako su elementi isti.

Teorem 3. Broj postavljanja bez ponavljanja jednak je umnošku m faktora, od kojih je najveći broj n . Zapiši:

Permutacije bez ponavljanja

Permutacije izn elementi se nazivaju različiti poredci skupaN.

Iz ove definicije slijedi da se dvije permutacije razlikuju samo u redoslijedu elemenata i mogu se smatrati posebnim slučajem plasmana.

Teorem 4. Broj različitih permutacija bez ponavljanja izračunava se formulom

Kombinacije bez ponavljanja

Kombinacija bez ponavljanjan elementi pom poziva se svaki neuređeni podskup skupaNkoji sadržim raznih elemenata.

Iz definicije proizlazi da se dvije kombinacije razlikuju samo u elementima, redoslijed nije bitan.

Teorem 5. Broj kombinacija bez ponavljanja izračunava se pomoću jedne od sljedećih formula:

Primjer 1. U sobi ima 5 stolica. Na koliko ih načina možete postaviti na njih?

a) 7 osoba; b) 5 osoba; c) 3 osobe?

Riješenje: a) Prije svega, trebate odabrati 5 ljudi od 7 koji će sjediti na stolicama. Može se
put. Svakim izborom određene petice možete proizvesti
prestrojavanja. Prema teoremu množenja, potreban broj metoda slijetanja je jednak.

Komentar: Zadatak se može riješiti koristeći se samo teoremom umnoška, ​​razmišljajući na sljedeći način: za sjedenje na 1. stolici postoji 7 opcija, na 2. stolici 6 opcija, na 3. -5, na 4. -4 i na 5-. th -3. Tada je broj načina da se 7 ljudi smjesti na 5 stolica . Rješenja obje metode su dosljedna, jer

b) Rješenje je očito -

V) - broj izbora zauzetih stolica.

- broj sjedećih mjesta za tri osobe na tri odabrane stolice.

Ukupan broj izbora je .

Nije teško provjeriti formule
;

;

Broj svih podskupova skupa koji se sastoji od n elementi.

Ponovite položaje

Postavljanjem uz ponavljanje odn elementi pom zove se svaki uređeni podskup skupaN, koja se sastoji odm elemenata tako da bilo koji element može biti uključen u ovaj podskup od 1 domputa, ili u potpunosti izostati iz njega.

Broj plasmana s ponavljanjem označen je sa i izračunava se pomoću formule koja je posljedica teorema množenja:

Primjer 2. Neka je N = (a, b, c) skup od tri slova. Nazovimo bilo koji skup slova uključen u ovaj skup riječju. Nađimo broj riječi duljine 2 koje se mogu sastaviti od ovih slova:
.

Komentar: Očito, plasmani s ponavljanjem također se mogu uzeti u obzir kada
.

Primjer 3. Trebate pomoću slova (a, b) sastaviti sve moguće riječi duljine 3. Na koliko se načina to može učiniti?

Odgovor:

Kombinatorika je grana matematike. Osnovni pojmovi i formule kombinatorike kao znanosti primjenjuju se u svim sferama života.

Nije iznenađujuće da je uključen u program 11. razreda, kao iu prijemne ispite na mnogim sveučilištima u Ruskoj Federaciji. Njegovi temelji leže u primijenjenoj umjetnosti mnogih sfera ljudske djelatnosti.

Njegova povijest seže više od 6 stoljeća unatrag. Prvi kombinatorni problemi pojavili su se u djelima filozofa i matematičara srednjeg vijeka.

Predstavnici tog znanstvenog svijeta pokušavali su pronaći metode za rješavanje takvih problema, njihova temeljna pravila i koncepte, te uspostaviti jedinstvene formule i jednadžbe za one koji se s njima još nisu susreli. Takve se informacije u naše vrijeme nazivaju informacijama "za lutke".

Pokušajmo razumjeti aspekte ovog područja znanosti: koji su elementi, svojstva, pravila, metode i njegova glavna primjena u našim životima? Naravno, nemoguće je obuhvatiti cijelo područje u jednom članku. Stoga će sve najosnovnije stvari biti predstavljene u nastavku.

Što je kombinatorika u matematici

Bit ovog izraza daju knjige prošlih godina: ovo grana matematike koja se bavi operacijama nad mnogim elementima.

Na internetu postoje udžbenici iz informatike i matematike za djecu i školarce, zbirke materijala i zadataka za početnike, gdje je na pristupačan način objašnjena “zabavna” kombinatorika. Moramo čvrsto smisliti kako riješiti takve probleme.

U osnovnim razredima problemi na ovu temu rješavaju se u dodatnim klubovima, au školama s produbljenim učenjem matematike - na glavnim satovima. Osim toga, zadaci kombinatorike uključeni su u olimpijade na svim razinama.

Osnovni koncepti

Ima ih nekoliko:

1. Element– bilo koji predmet ili pojava uključena u željeni skup.
2. Kombinacija– podskupovi smješteni proizvoljnim redoslijedom u izvornom skupu.
3. Preuređenje– elementi u skupu su u strogo definiranom redoslijedu.
4. Smještaj– uređeni podskupovi u izvornom skupu.

Pravilo proizvoda

Jedno je od osnovnih pravila kod rješavanja ovakvih problema i zvuči ovako:

Prilikom odabira elementa A iznmetode i izbor elementa B izmNa neki način istina je da je moguće odabrati par A i B u isto vrijemen* mnačine.

Pogledajmo konkretne primjere.

Zadatak br. 1.

Kutija sadrži 2 lopte i 6 užadi za skakanje. Na koliko načina možete dobiti 1 loptu i 1 uže za skakanje?

Odgovor je jednostavan: 2 * 6 = 12.

Zadatak br. 2.

Ima 1 kocku, 2 kuglice, 3 cvijeta i 4 bombona. Na koliko načina se može nacrtati kocka, lopta, cvijet i bombon?

Rješenje je slično: 1 * 2 * 3 * 4 = 24.

Štoviše, lijeva strana se može napisati mnogo jednostavnije: 4!

! u ovom slučaju to nije interpunkcijski znak, već faktorijel. Pomoću njega možete izračunati složenije opcije i riješiti teške probleme (postoje različite formule, ali više o tome kasnije).

Zadatak br. 3.

Koliko se dvoznamenkastih brojeva može sastaviti od 2 znamenke?

Odgovor: 2! = 2.

Zadatak br. 4.

Koliko se deseteroznamenkastih brojeva može sastaviti od 10 znamenki?

Pravilo zbroja

Ovo je ujedno i osnovno pravilo kombinatorike.

Ako se A može izabratinputa, a B -mputa, tada se može izabrati A ili B (n+ m) jednom.

Zadatak br. 5.

U kutiji se nalazi 5 crvenih, 3 žute, 7 zelenih i 9 crnih olovaka. Na koliko načina možete izvući bilo koju olovku?

Odgovor: 5 + 3 + 7 + 9 = 24.

Kombinacije sa i bez ponavljanja

Ovaj izraz se odnosi na kombinacije bilo kojim redoslijedom iz skupa od n x m elemenata.

Broj kombinacija jednak je broju takvih kombinacija.

Zadatak br. 6.

Kutija sadrži 4 različita voća. Na koliko načina možete dobiti 2 različita voća u isto vrijeme?

Rješenje je jednostavno:

Gdje je 4! – kombinacija 4 elementa.

S ponavljanjima malo kompliciranije, kombinacije se izračunavaju pomoću sljedeće formule:

Zadatak br. 7.

Uzmimo isti slučaj, ali pod uvjetom da se jedan plod vrati u kutiju.

U ovom slučaju:

Plasmani sa i bez ponavljanja

Ova definicija označava skup od m elemenata iz skupa od n elemenata.

Zadatak br. 8.

Od 3 znamenke, trebate odabrati 2 da biste dobili različite dvoznamenkaste brojeve. Koliko opcija?

Odgovor je jednostavan:

Ali što s tim? s ponavljanjima? Ovdje se svaki element može postaviti nekoliko puta! U ovom slučaju, opća formula će izgledati ovako:

Zadatak br. 9.

Od 12 slova latinične abecede i 10 znamenki prirodnog niza trebate pronaći sve mogućnosti za sastavljanje regionalnog koda automobila.

Permutacije sa i bez ponavljanja

Ovaj izraz se odnosi na sve moguće kombinacije skupa n elemenata.

Zadatak br. 10.

Koliko se mogućih 5-znamenkastih brojeva može sastaviti od 5 znamenki? Što je sa šest znamenki od 6 znamenki? Sedam znamenki od 7 znamenki?

Rješenja, prema gornjoj formuli, su sljedeća:

Ali što s tim? s ponavljanjima? Ako u takvom skupu postoje elementi jednake važnosti, tada će biti manje permutacija!

Zadatak br. 11.

U kutiji se nalaze 3 iste olovke i jedna olovka. Koliko permutacija možete napraviti?

Odgovor je jednostavan: 4! / (3! * 1!) = 4.

Kombinatorni zadaci s rješenjima

Gore su navedeni primjeri svih mogućih vrsta problema s rješenjima. Ovdje ćemo se pokušati pozabaviti složenijim slučajevima s kojima se susrećemo u životu.

Vrste zadataka	Ono što trebate pronaći	Metode rješenja
Magični kvadrat	Slika u kojoj zbroj brojeva u recima i stupcima mora biti isti (njena je varijanta latinski kvadrat).	Relacije ponavljanja. Sličan problem je riješen, ali s puno manjim skupom elemenata prema poznatim pravilima i formulama.
Problem postavljanja	Standardni proizvodni zadatak (primjerice u patchwork tehnologiji) je pronaći moguće načine rastavljanja količina proizvoda u ćelije određenim redoslijedom.	Uključivanja i isključenja. U pravilu se koristi pri dokazivanju raznih izraza.
Problemi oko trgovaca	Poanta je pronaći sve moguće načine da ljudi dođu od točke A do točke B.	Trajektorije. Ovu vrstu problema karakterizira geometrijska konstrukcija mogućih rješenja.

Zaključak

Vrijedno je proučavati ovu znanost, jer će u doba brze modernizacije tehnologije biti potrebni stručnjaci koji mogu ponuditi različita rješenja za određene praktične probleme.

Sažetak na temu:

Ispunila učenica 10. razreda “B”

53. srednja škola

Gluhov Mihail Aleksandrovič

Naberežnije Čelni

2002. godine
Sadržaj

Iz povijesti kombinatorike____________________________________________________	3
Pravilo zbroja________________________________________________________________	4
	-
Pravilo proizvoda________________________________________________	4
Primjeri zadataka_____________________________________________________________	-
Skupovi koji se sijeku____________________________________________________	5
Primjeri zadataka_____________________________________________________________	-
Eulerove kružnice_____________________________________________________________	-
Plasmani bez ponavljanja________________________________________________	6
Primjeri zadataka_____________________________________________________________	-
Permutacije bez ponavljanja________________________________________________	7
Primjeri zadataka_____________________________________________________________	-
Kombinacije bez ponavljanja____________________________________________________	8
Primjeri zadataka_____________________________________________________________	-
Položaji i kombinacije bez ponavljanja__________________________	9
Primjeri zadataka_____________________________________________________________	-
Permutacije s ponavljanjem________________________________________________	9
Primjeri zadataka_____________________________________________________________	-
Zadaci za samostalno rješavanje________________________________	10
Bibliografija___________________________________	11

Iz povijesti kombinatorike

Kombinatorika se bavi raznim vrstama veza koje se mogu formirati iz elemenata konačnog skupa. Neki elementi kombinatorike bili su poznati u Indiji već u 2. stoljeću. PRIJE KRISTA e. Nydijci su znali izračunati brojeve, koji se danas nazivaju "kombinacije". U 12.st. Bhaskara je izračunao neke vrste kombinacija i permutacija. Vjeruje se da su indijski znanstvenici proučavali spojeve u vezi s njihovom upotrebom u poetici, proučavanju strukture stihova i pjesničkih djela. Na primjer, u vezi s izračunom mogućih kombinacija naglašenih (dugih) i nenaglašenih (kratkih) slogova stope od n slogova. Kao znanstvena disciplina kombinatorika se formirala u 17. stoljeću. U knjizi “Teorija i praksa aritmetike” (1656.), francuski autor A. također posvećuje cijelo jedno poglavlje kombinacijama i permutacijama.
B. Pascal u svojoj “Raspravi o aritmetičkom trokutu” iu svojoj “Raspravi o numeričkim redovima” (1665.) iznio je doktrinu binomnih koeficijenata. P. Fermat je znao za veze matematičkih kvadrata i figuriranih brojeva s teorijom spojeva. Pojam “kombinatorika” počeo se koristiti nakon što je Leibniz objavio svoje djelo “Rasprava o umijeću kombiniranja” 1665. godine, koje je prvi put dalo znanstvenu osnovu za teoriju kombinacija i permutacija. J. Bernoulli prvi je proučavao položaje u drugom dijelu svoje knjige “Ars conjectandi” (umijeće predviđanja) 1713. godine. Moderni simbolizam kombinacija predložili su razni autori obrazovnih priručnika tek u 19. stoljeću.

Čitava raznolikost kombinatornih formula može se izvesti iz dvije osnovne tvrdnje o konačnim skupovima - pravila zbroja i pravila umnoška.

Pravilo zbroja

Ako se konačni skupovi ne sijeku, tada je broj elemenata skupa X U Y (ili) jednak zbroju broja elemenata skupa X i broja elemenata skupa Y.

To jest, ako je X knjiga na prvoj polici, a Y na drugoj, tada možete odabrati knjigu s prve ili druge police na X+Y načina.

Uzorak problema

Učenik mora obaviti praktični rad iz matematike. Na izbor mu je ponuđeno 17 tema iz algebre i 13 tema iz geometrije. Na koliko načina može odabrati jednu temu za praktični rad?

Rješenje: X=17, Y=13

Prema pravilu zbroja X U Y=17+13=30 tema.

U ponudi je 5 srećki za novčanu lutriju, 6 srećki za sportsku lutriju i 10 listića za lutriju automobila. Na koliko načina možete odabrati jedan listić sportske lutrije ili auto lutrije?

Rješenje: Budući da lutrija za novac i odjeću nije uključena u izbor, postoji samo 6 + 10 = 16 opcija.

Pravilo proizvoda

Ako se element X može izabrati na k načina, a element Y na m načina, tada se par (X,Y) može izabrati na k*m načina.

Odnosno, ako je na prvoj polici 5 knjiga, a na drugoj 10, tada možete izabrati jednu knjigu s prve police i jednu s druge na 5 * 10 = 50 načina.

Uzorak problema

Knjigovezac mora uvezati 12 različitih knjiga u crvene, zelene i smeđe uveze. Na koliko načina to može učiniti?

Rješenje: Postoji 12 knjiga i 3 boje, što znači da je prema pravilu proizvoda moguće 12 * 3 = 36 opcija uveza.

Koliko ima peteroznamenkastih brojeva koji se jednako čitaju slijeva nadesno i zdesna nalijevo?

Rješenje: U takvim brojevima posljednja znamenka bit će ista kao prva, a pretposljednja znamenka bit će ista kao druga. Treća znamenka bit će bilo što. To se može prikazati u obliku XYZYX, gdje su Y i Z bilo koji brojevi, a X nije nula. To znači da je prema pravilu umnoška broj znamenki koje se mogu čitati jednako i slijeva na desno i s desna na lijevo 9*10*10=900 opcija.

Presječni skupovi

No događa se da se skupovi X i Y sijeku, tada koriste formulu

, gdje su X i Y skupovi, a područje presjeka. Uzorak problema

20 ljudi zna engleski, a 10 njemački, od čega 5 i engleski i njemački. Koliko ljudi ima ukupno?

Odgovor: 10+20-5=25 ljudi.

Eulerove kružnice također se često koriste za vizualno rješavanje problema. Na primjer:

Od 100 turista koji idu na putovanje u inozemstvo, 30 ljudi govori njemački, 28 - engleski, 42 - francuski, 8 ljudi govori istovremeno engleski i njemački, 10 - engleski i francuski, 5 - njemački i francuski, 3 - sva tri jezici. turisti ne govore nijedan jezik?

Riješenje: Izrazimo stanje ovog problema grafički. Kružićem označimo one koji znaju engleski, drugim krugom one koji znaju francuski, a trećim krugom one koji znaju njemački.

Tri turista govore sva tri jezika, što znači da u općem dijelu krugova upisujemo broj 3. 10 ljudi govori engleski i francuski, a njih 3 i njemački. Shodno tome, 10-3=7 ljudi govori samo engleski i francuski.

Slično, nalazimo da 8-3 = 5 ljudi govori samo engleski i njemački, a 5-3 = 2 turista govori njemački i francuski. Te podatke unosimo u odgovarajuće dijelove.

Odredimo sada koliko ljudi govori samo jedan od navedenih jezika. 30 ljudi zna njemački, ali njih 5+3+2=10 govori druge jezike, dakle samo 20 ljudi zna njemački. Slično, nalazimo da 13 ljudi govori samo engleski, a 30 ljudi govori samo francuski.

Prema problemu je samo 100 turista. 20+13+30+5+7+2+3=80 turista zna barem jedan jezik, dakle 20 ljudi ne govori nijedan od ovih jezika.

Plasmani bez ponavljanja.

Koliko se telefonskih brojeva može sastaviti od po 6 znamenki, tako da sve znamenke budu različite?

Ovo je primjer problema postavljanja bez ponavljanja. Ovdje je postavljeno 10 brojeva od 6. A opcije u kojima su isti brojevi u različitim redoslijedima smatraju se različitima.

Ako je X-skup koji se sastoji od n elemenata, m≤n, tada se raspored bez ponavljanja n elemenata skupa X u m naziva uređenim skupom X koji sadrži m elemenata. Naziva se uređeni skup X koji sadrži m elemenata.

Broj svih rasporeda n elemenata s m je označen sa

n! - n-faktorij (faktor faktor) je umnožak brojeva u prirodnom nizu od 1 do bilo kojeg broja n Zadatak

Na koliko načina 4 dječaka mogu pozvati četiri od šest djevojčica na ples?

Riješenje: dva dječaka ne mogu pozvati istu djevojku u isto vrijeme. A opcije u kojima iste djevojke plešu s različitim dječacima smatraju se različitima, dakle:

Moguće 360 ​​opcija.

Permutacije bez ponavljanja

U slučaju n=m (vidi rasporede bez ponavljanja) od n elemenata od m naziva se permutacija skupa x.

Broj svih permutacija od n elemenata označen je s P n.

Vrijedi za n=m:

Uzorak problema

Koliko se različitih šesteroznamenkastih brojeva može sastaviti od znamenki 0, 1, 2, 3, 4.5 ako se brojevi ne ponavljaju?

1) Odredite broj svih permutacija iz ovih brojeva: P 6 =6!=720

2) 0 ne može biti ispred broja, pa se od tog broja mora oduzeti broj permutacija u kojima je 0 ispred. A ovo je P 5 =5!=120.

P 6 -P 5 =720-120=600

Zločesti majmun

Da, klupava Miška

Počeli smo svirati kvartet

Stanite, braćo, stanite! –

Majmun viče, - čekaj!

Kako bi trebala ići glazba?

Uostalom, ne sjedite tako...

I ovako i onako promijenili mjesta - opet ne ide muzika.

U ovom ćemo članku govoriti o posebnoj grani matematike koja se naziva kombinatorika. Formule, pravila, primjeri rješavanja problema - sve to možete pronaći ovdje čitajući članak do samog kraja.

Dakle, što je ovaj odjeljak? Kombinatorika se bavi pitanjem brojanja bilo kojih predmeta. Ali 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, kod kartanja – kolika je vjerojatnost da protivnik ima aduta? Ili ovaj primjer: kolika je vjerojatnost da ćete iz vreće s dvadeset klikera dobiti bijelu? Upravo za ovakvu vrstu problema potrebno je poznavati barem osnove ove grane matematike.

Kombinatorne konfiguracije

Razmatrajući problematiku temeljnih pojmova i formula kombinatorike, ne možemo ne obratiti pozornost na kombinatorne konfiguracije. Koriste se ne samo za formuliranje, već i za rješavanje različitih primjera. Primjeri takvih modela su:

• smještaj;
• preuređenje;
• kombinacija;
• sastav brojeva;
• cijepanje broja.

Kasnije ćemo detaljnije govoriti o prva tri, ali ćemo u ovom odjeljku obratiti pozornost na sastav i particije. Kada govore o sastavu određenog broja (na primjer, a), misle na predstavljanje broja a kao uređenog zbroja određenih pozitivnih brojeva. A particija je neuređeni zbroj.

Sekcije

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

• nabrajan;
• strukturalni;
• ekstremno;
• Ramseyeva teorija;
• vjerojatnosni;
• topološki;
• beskonačan.

U prvom slučaju govorimo o kalkulativnoj kombinatorici, problemi se odnose na nabrajanje ili prebrojavanje različitih konfiguracija koje tvore elementi skupova. Tim se skupovima u pravilu nameću određena ograničenja (različitost, nerazličivost, mogućnost ponavljanja itd.). 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. Probabilistička kombinatorika je u stanju odgovoriti na pitanje – kolika je vjerojatnost da dati skup ima određeno svojstvo. Kao što možda pretpostavljate, topološka kombinatorika primjenjuje metode u topologiji. I konačno, sedma točka - beskonačna kombinatorika proučava primjenu kombinatoričkih metoda na beskonačne skupove.

Pravilo sabiranja

Među kombinatoričkim formulama možete pronaći vrlo jednostavne, s kojima smo već dosta dugo upoznati. Primjer je pravilo zbroja. Pretpostavimo da su nam zadane dvije radnje (C i E), ako se one međusobno isključuju, radnja C se može izvesti na nekoliko načina (na primjer, a), a radnja E se može izvesti na b-načine, tada bilo koji od njih ( C ili E) može se izvesti na a + b načine.

U teoriji je to prilično teško razumjeti; pokušat ćemo prenijeti cijelu poantu na jednostavnom primjeru. Uzmimo prosječan broj učenika u jednom razredu – recimo da je dvadeset i pet. Među njima je petnaest djevojčica i deset dječaka. Svakom razredu svaki dan raspoređena je jedna dežurna osoba. Na koliko načina danas postoji imenovanje razrednika? Rješenje problema je vrlo jednostavno, pribjeći ćemo pravilu zbrajanja. U tekstu zadatka ne piše da mogu dežurati samo dječaci ili samo djevojčice. Dakle, to može biti bilo koja od petnaest djevojčica ili bilo koji od deset dječaka. Primjenom pravila zbroja dobivamo prilično jednostavan primjer s kojim se lako snalazi osnovnoškolac: 15 + 10. Nakon prebrojavanja dobivamo odgovor: dvadeset pet. Odnosno, postoji samo dvadeset i pet načina za dodjeljivanje klase na dužnosti za danas.

Pravilo množenja

Osnovne formule kombinatorike također uključuju pravilo množenja. Počnimo s teorijom. Recimo da trebamo izvesti nekoliko radnji (a): prva radnja se izvodi na 1 način, druga - na 2 načina, treća - na 3 načina, i tako dalje do posljednje a-radnje, izvedene na 3 načina. Tada se sve ove akcije (kojih imamo ukupno) mogu izvesti na N načina. Kako izračunati nepoznati N? U tome će nam pomoći formula: N = c1 * c2 * c3 *…* ca.

Opet, u teoriji ništa nije jasno, pa prijeđimo na jednostavan primjer primjene pravila množenja. Uzmimo isti razred od dvadeset i pet ljudi, u kojem je petnaest djevojčica i deset dječaka. Samo ovaj put trebamo izabrati dvoje ljudi na dužnosti. Mogu biti samo dječaci ili djevojčice, ili dječak i djevojčica. Prijeđimo na elementarno rješenje problema. Biramo prvog dežurnog, kako smo odlučili u zadnjem odlomku, 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 je drugi dežurni mogao biti bilo koji od preostalih dvadeset i četiri. Konačno, primjenjujemo pravilo množenja i otkrivamo da se dva časnika na dužnosti mogu izabrati na šest stotina načina. Taj smo broj dobili množenjem dvadeset pet i dvadeset četiri.

Preuređenje

Sada ćemo pogledati još jednu kombinatoričku formulu. U ovom dijelu članka govorit ćemo o permutacijama. Predlažemo da odmah razmotrimo problem koristeći primjer. Uzmimo kugle za bilijar, imamo ih n-ti broj. Moramo prebrojati koliko ima opcija da ih posložimo u niz, odnosno da napravimo uređen skup.

Krenimo, ako nemamo muda, onda imamo i nula opcija za plasman. A ako imamo jednu kuglicu, raspored je također isti (matematički se to može napisati na sljedeći način: P1 = 1). Dvije kuglice se mogu postaviti na dva različita načina: 1,2 i 2,1. Dakle, P2 = 2. Tri kuglice se mogu rasporediti na šest načina (P3 = 6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. Što ako nema tri takve lopte, nego deset ili petnaest? Trebalo bi jako dugo nabrajati sve moguće opcije, a onda nam u pomoć dolazi kombinatorika. Formula permutacije pomoći će nam pronaći odgovor na pitanje koje nas zanima. Pn = n * P (n-1). Ako pokušamo pojednostaviti formulu, dobivamo: Pn = n* (n - 1) *…* 2 * 1. A ovo je umnožak prvih prirodnih brojeva. Ovaj broj se naziva faktorijel, a označava se kao n!

Razmotrimo problem. Svakog jutra savjetnik postrojava svoju četu (dvadeset ljudi). U timu su tri najbolja prijatelja - Kostya, Sasha i Lesha. Kolika je vjerojatnost da će stati jedan 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 "dobre" rezultate? Pretpostavimo da su Kostya, Sasha i Lesha jedan supermen. Onda imamo 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 to je još 3! = 6 opcija. To znači da imamo ukupno 18 “dobrih” aranžmana! * 3! Sve što trebamo učiniti je pronaći željenu vjerojatnost: (18! * 3!) / 20! Što je otprilike jednako 0,016. Preračuna li se u postotke, ispada samo 1,6%.

Smještaj

Sada ćemo pogledati još jednu vrlo važnu i potrebnu kombinatoričku formulu. Položaj je naše sljedeće pitanje, koje vas pozivamo da razmotrite u ovom odjeljku članka. Idemo na komplikacije. Pretpostavimo da želimo razmotriti moguće permutacije, ne iz cijelog skupa (n), već iz manjeg (m). To jest, razmatramo permutacije n stavki po m.

Osnovne formule kombinatorike treba ne samo zapamtiti, već i razumjeti. Iako postaju kompliciraniji, jer nemamo jedan parametar, već dva. Pretpostavimo da je m = 1, zatim A = 1, m = 2, zatim A = n * (n - 1). Ako formulu dodatno pojednostavimo i prijeđemo na zapis pomoću faktorijela, dobivamo potpuno lakonsku formulu: A = n! / (n - m)!

Kombinacija

Pregledali smo gotovo sve osnovne kombinatoričke formule s primjerima. Sada prijeđimo na završnu fazu razmatranja osnovnog kolegija kombinatorike – upoznavanje kombinacija. Sada ćemo odabrati m stavki od n koje imamo, i birat ćemo sve na sve moguće načine. Kako se to onda razlikuje od plasmana? Redoslijed nećemo uzeti u obzir. Ovaj neuređeni skup bit će kombinacija.

Odmah uvedimo oznaku: C. Postavljanje m kuglica izuzimamo iz n. Prestajemo paziti na redoslijed i završavamo s ponavljanjem kombinacija. Da bismo dobili broj kombinacija potrebno je broj plasmana podijeliti s m! (m faktorijel). Odnosno, C = A / m! Dakle, postoji samo nekoliko načina za odabir od n kuglica, što je približno jednako broju načina za odabir gotovo svih njih. Za to postoji logičan izraz: izabrati malo je isto što i izbaciti gotovo sve. Ovdje je također važno spomenuti da se maksimalan broj kombinacija može postići kada se pokušava odabrati polovica stavki.

Kako odabrati formulu za rješavanje problema?

Detaljno smo ispitali osnovne formule kombinatorike: postavljanje, permutaciju i kombinaciju. Sada je naš zadatak olakšati odabir potrebne formule za rješavanje kombinatoričkog problema. Možete koristiti sljedeću prilično jednostavnu shemu:

1. Zapitajte se: je li u tekstu zadatka uzet u obzir redoslijed kojim su elementi postavljeni?
2. Ako je odgovor ne, upotrijebite formulu kombinacije (C = n! / (m! * (n - m)!)).
3. Ako je odgovor negativan, potrebno je odgovoriti na drugo pitanje: jesu li svi elementi uključeni u kombinaciju?
4. Ako je odgovor potvrdan, upotrijebite formulu permutacije (P = n!).
5. Ako je odgovor ne, upotrijebite formulu za plasman (A = n! / (n - m)!).

Primjer

Razmotrili smo elemente kombinatorike, formule i još neka pitanja. Sada prijeđimo na razmatranje pravog problema. Zamislite da ispred sebe imate kivi, naranču i bananu.

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

Drugo pitanje: na koliko načina možete odabrati jedno voće? To je očito, imamo samo tri mogućnosti - izabrati kivi, naranču ili bananu, ali primijenimo formulu kombinacije: C = 3! / (2! * 1!) = 3.

Treće pitanje: na koliko načina možete odabrati dva voća? Koje mogućnosti uopće imamo? Kivi i naranče; kivi i banana; naranča i banana. Odnosno, postoje tri opcije, ali to je lako provjeriti pomoću kombinacije formule: C = 3! / (1! * 2!) = 3

Četvrto pitanje: na koliko načina možete 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.

Peto pitanje: na koliko načina možete odabrati barem jedno voće? Ovaj uvjet znači da možemo uzeti jednu, dvije ili sve tri voćke. Dakle, zbrajamo C1 + C2 + C3 = 3 + 3 + 1 = 7. Odnosno, imamo sedam načina da uzmemo barem jedno voće sa stola.