Kombinatorika je grana matematike koja proučava pitanje koliko kombinacija određene vrste može biti napravljeno od datih objekata (elemenata).

Pravilo množenja (osnovna formula kombinatorike)

Ukupan broj načina na koje se može odabrati jedan element iz svake grupe i rasporediti ih određenim redoslijedom (tj. dobiti uređeni skup) jednak je:

Primjer 1

Novčić je bačen 3 puta. Koliko različitih rezultata bacanja možete očekivati?

Rješenje

Prvi novčić ima alternative - ili glavu ili rep. Za drugi novčić također postoje alternative itd., tj. .

Potreban broj načina:

Pravilo sabiranja

Ako bilo koje dvije grupe nemaju zajedničke elemente, tada se izbor jednog elementa ili iz , ili iz , ...ili iz može izvršiti na načine.

Primjer 2

Na polici je 30 knjiga, od toga 20 matematičkih, 6 tehničkih i 4 ekonomske. Na koliko načina postoji izbor jedne knjige iz matematike ili ekonomije?

Rješenje

Knjiga iz matematike se može odabrati na načine, a knjiga iz ekonomije na načine.

Prema pravilu sume, postoji način da odaberete knjigu matematike ili ekonomije.

Postavljanje i preuređenje

Placements- To su uređene kolekcije elemenata koji se međusobno razlikuju bilo po sastavu ili po redoslijedu elemenata.

Plasmani bez ponavljanja, kada se odabrani element ne vraća u populaciju prije odabira sljedećeg. Takva selekcija se naziva sekvencijalna selekcija bez ponavljanja, a njen rezultat je postavljanje bez ponavljanja elemenata po .

Broj različitih načina na koje se može izvršiti sekvencijalni odabir bez vraćanja elemenata iz populacije volumena jednak je:

Primjer 3

Dnevni raspored se sastoji od 5 različitih lekcija. Odredite broj opcija rasporeda kada birate između 11 disciplina.

Rješenje

Svaka opcija rasporeda predstavlja skup od 5 disciplina od 11, koje se razlikuju od ostalih opcija i po sastavu i po redoslijedu. zato:

Preuređenja su uređene kolekcije koje se međusobno razlikuju samo po redoslijedu svojih elemenata. Broj svih permutacija skupa elemenata je jednak

Primjer 4

Na koliko načina 4 osobe mogu sjediti za jednim stolom?

Rješenje

Svaka opcija sedenja razlikuje se samo po redosledu učesnika, odnosno radi se o permutaciji 4 elementa:

Položaji sa ponavljanjima, kada se odabrani element vrati u populaciju prije odabira sljedećeg. Ova selekcija se zove sekvencijalna selekcija sa povratkom, a njen rezultat se naziva postavljanje sa ponavljanjem elemenata po .

Ukupan broj različitih načina na koje se može izvršiti selekcija za vraćanje elemenata iz populacije volumena jednak je

Primjer 5

Lift se zaustavlja na 7 spratova. Na koliko načina 6 putnika u kabini lifta može izaći na ove spratove?

Rješenje

Svaki od načina raspodjele putnika po spratovima je kombinacija 6 putnika na 7 spratova, koja se razlikuje od ostalih kombinacija i po sastavu i po svom redoslijedu. Pošto jedan ili više putnika može izaći sa istog sprata, isti putnici se mogu ponoviti. Stoga je broj takvih kombinacija jednak broju postavljanja s ponavljanjima 7 elemenata od 6:

Kombinacije

Kombinacije od n elemenata po k nazivaju se neuređene kolekcije koje se međusobno razlikuju za najmanje jedan element.

Neka se iz opće populacije uzme nekoliko elemenata odjednom (ili se elementi uzimaju uzastopno, ali se redoslijed njihovog pojavljivanja ne uzima u obzir). Kao rezultat takvog istovremenog neuređenog odabira elemenata iz opće populacije volumena, dobijaju se kombinacije koje se nazivaju kombinacije bez ponavljanja od elemenata po .

Broj kombinacija elemenata jednak je:

Primjer 6

U kutiji je 9 jabuka. Na koliko načina možete odabrati 3 jabuke iz kutije?

Rješenje

Svaki izbor sastoji se od 3 jabuke i razlikuje se od ostalih samo po sastavu, odnosno kombinacije su bez ponavljanja 9 elemenata:

Broj načina na koji možete odabrati 3 jabuke od 9:

Neka elementi budu odabrani iz opće populacije volumena, jedan za drugim, i svaki odabrani element se vraća u opću populaciju prije odabira sljedećeg. Ovo bilježi koji su se elementi pojavili i koliko puta, ali ne uzima u obzir redoslijed kojim su se pojavili. Rezultirajući agregati se pozivaju kombinacije sa ponavljanjima od elemenata po .

Broj kombinacija sa ponavljanjem elemenata po:

Primjer 7

Pošta prodaje 3 vrste razglednica. Na koliko načina možete kupiti 6 razglednica?

Ovo je zadatak da pronađete broj kombinacija s ponavljanjima od 3 do 6:

Podjela skupa na grupe

Neka skup različitih elemenata bude podijeljen u grupe poput ove, tada prva grupa uključuje elemente, druga - elemente, treća grupa - elemente i . Ova situacija se zove particionisanje skupa u grupe.

Broj particija na grupe, kada elementi spadaju u prvu, elementi u drugu, a elementi u k-tu grupu, jednak je:

Primjer 8

Grupu od 16 ljudi potrebno je podijeliti u tri podgrupe, od kojih bi prva trebala imati 5 ljudi, druga - 7 ljudi, treća - 4 osobe. Na koliko načina se to može učiniti?

Vrsta i karakteristike: lekcija u otkrivanju i učenju novog znanjarješavanjem praktičnih problema.

Cilj lekcije: naučiti studente da rješavaju kombinatorne probleme koristeći sljedeće metode: 1) konačno pretraživanje; 2) izgradnja stabla mogućih opcija; 3) korišćenjem tabele.

Oprema: komponente obrazovnog kompleksa „Vilenkin. 5",projektor, kompjuter,interaktivna tabla ( ID ) , na svakom stolu su 2 lista (A4 format) sa 7 riješenih razrednih zadataka i 2 lista (A4 format) sa 7 testnih zadataka. Na učiteljskom stolu se nalazi list (format A4) sa 7 riješenih razrednih zadataka i list (format A4) sa 7 testnih zadataka sa njihovim rješenjima, ispisom projektnog zadatka za dom.

Koraci lekcije

Scenski zadaci

Visuals

Aktivnosti nastavnika

Aktivnosti učenika

Formirana UUD

Organizacijski

Prikupite domaći, pripremite se za čas

Slajd na tabli:

“teško za naučiti, lako se boriti”

Molimo vas da sada dostavite sveske za domaće zadatke na provjeru. Da vas podsjetim da danas počinjemo proučavati novu temu.

Polaznici prolaze kroz učionicu i skupljaju sveske.

Samoregulacija, predviđanje i procjena

Ažuriranje teorijskih znanja

Odredite svrhu lekcije

Na tabli: datum i naziv teme: “Kombinatorski problemi”

Ljudi, danas ćemo krenuti na fascinantno putovanje u svijet "Kombinatorike"

Mentalno postavite pitanje: "Šta je ovo?"

Postavljanje ciljeva, refleksija predmeta.

Objašnjenja o novoj stvari

la

Početno upoznavanje sa osnovnim pojmovima,

metode, načini

rješenja

kombinatorni problemi

Slajd na tabli: Riječ "kombinatorika" dolazi od latinske riječi COMBINARE, što znači "spojiti", "kombinirati"

Nastavnik pita šta mislite šta znači riječ kombinatorika?

Nastavnik zastaje, sluša odgovore, a zatim izgovara definiciju.

Reč "kombinatorika" dolazi od latinske reči COMBINARE, što znači "spojiti", "kombinovati"

Djeca odgovaraju postavljajući hipoteze

Slušajte pažljivo, pročitajte definiciju na brošuri

Predlaganje i testiranje hipoteza.

Kliznite po ploči

Za zaključavanje kofera kombinovanom bravom koja se sastoji od bilo koja dva broja. Vlasnik kofera je odlučio da koristi samo brojeve 1, 2 i 3. Na koliko načina može izabrati šifru?

Ovaj problem se može riješiti korištenjem stabla mogućih opcija ili pretraživanjem svih mogućih opcija.

Pažljivo slušaju, gledaju slajd, razmišljaju, pamte.

Smisleno citanje.

Slajd na tabli:

Rješenje sa mogućim stablom

Opcije

DRVO MOGUĆIH OPCIJA Često procesPogodno je izvršiti nabrajanje konstruisanjem posebnog kola - tzvstablo mogućih opcija

Nacrtajte korijen drveta, da biste to učinili, stavite znak *.

Za odabir prve cifre koda, imamo tri opcije: 1; 2; 3. Dakle, nacrtajte tri grane iz korijena drveta i stavite brojeve 1 na njihove krajeve; 2; 3.

Za odabir druge cifre postoje iste tri opcije. Izvodimo "grančice"

Analiza objekata.

Slajd na tabli:

Rješenje grube sile

Odgovarajući kodovi su dvocifreni brojevi koji se mogu sastaviti od cifara

1, 2, 3. Sve takve brojeve ćemo ispisati rastućim redom. Ova metoda nabrajanja omogućit će nam da ne propustimo nijedan kod i da u isto vrijeme ne ponovimo nijedan od njih.

Od početka zapisujemo rastućim redom sve kodove koji počinju brojem 1: 11, 12, 13. Zatim upisujemo u rastućem redoslijedu kodove koji počinju brojem 2: 21, 22, 23.

Zatim zapisujemo u rastućem redoslijedu kodove koji počinju brojem 3: 31, 32, 33

Dakle, postoji 9 načina za odabir

kodovi: 11, 12, 13, 21, 22, 23, 31, 32, 33.

Pažljivo slušaju, gledaju slajdove, razmišljaju, analiziraju, klasifikuju, pamte.

Analiza objekata.

Izbor kriterijumskih osnova za poređenje, seriranje, klasifikaciju objekata.

Kreiranje i transformacija modela i dijagrama za rješavanje problema ovisno o specifičnim uvjetima.

Konsolidacija novih znanja

Pokazati praktičnu primjenu teorijskih znanja

kroz njihovu primenu u rešavanju praktičnih problema

Kliznite po tabli sa uslovom zadatka br. 1

U trpezariji za doručak možete izabrati picu, lepinju, sendvič, a možete ga popiti čajem i sokom. Od koliko opcija doručka možete birati?

Kliznite po ploči s rješenjem

Slajd prikazuje stablo mogućih opcija

prvi nivo "PIĆE"

dvije opcije: ČAJ, SOK.

drugi nivo tri opcije: PIZZA, BUN, SENDVIČ.

Ukupno šest OPCIJA za doručak:

ČAJ+PIZA, ČAJ+GROPA, ČAJ+SENDVIČ, SOK+PIZA, SOK+GRIP, SOK+SENDVIČ.

Pažljivo slušaju, gledaju slajdove, razmišljaju, analiziraju, klasifikuju, pamte.

Uvod u profesije.

Analiza objekata.

Izbor kriterijumskih osnova za poređenje, seriranje, klasifikaciju objekata.

Kreiranje i transformacija modela i dijagrama za rješavanje problema ovisno o specifičnim uvjetima.

Prevucite na ploču sa uslovima zadatka br. 2

Od zemlje „Matematika“ do zemlje „Književnost“ vode tri puta, a od zemlje „Književnost“ do zemlje „Fizičko vaspitanje“ vode četiri puta. Na koliko načina možete stići od zemlje “Matematika” do

Država “Fizičko vaspitanje” kroz zemlju “Književnost”?

Kliznite po ploči s rješenjem

Crtež će nam pomoći da riješimo ovaj problem.

Hajdemo kroz sve "PUTEVE"

Označimo puteve koji dolaze iz zemlje “MATEMATIKA” na sljedeći način: M1, M2, M3,

i iz “LITERATURE” L1, L2, L3, L4.

Idemo kroz M1+L1, M1+L2, M1+L3, M1+L4, M2+L1, M2+L2, M2+L3,

M2+L4, M3+L1, M3+L2, M3+L3, M3+L4

Guraj

Djeca razmišljaju o tome da umnože broj puteva

Ili možete uzeti i pomnožiti broj puteva 3 * 4 = 12

Pažljivo slušaju, gledaju slajdove, razmišljaju, analiziraju, klasifikuju, pamte.

Upoznajte se sa modelima i dijagramima za rešavanje problema u zavisnosti od specifičnih uslova.

Prevucite na ploču sa uslovima zadatka br. 3

Sigurna šifra se sastoji od slova i brojeva, pri čemu je slovo na prvom mjestu (na primjer, A7). Koliko se različitih verzija šifre može napraviti koristeći slova A, B, C i brojeve 3, 7, 9?

Kliznite po ploči s rješenjem

2) Za odabir kodnog slova, imamo tri opcije: A; B ; C. Stoga su iz korijena drveta izvučene tri grane i na njihovim krajevima postavljena slova: A; B ; C.

3) Za odabir broja, postoje iste tri opcije. Izvodimo "grančice"

Krećući se od korijena drveta duž grana, dobićemo sve moguće kodove

A3, A7, A9, B3, B7, B9, C3, C7, C9

Or Ukupno 3*3=9 opcija

Pažljivo slušaju, gledaju slajdove, razmišljaju, analiziraju, klasifikuju, pamte.

Upoznajte se sa modelima i dijagramima za rešavanje problema u zavisnosti od specifičnih uslova.

Prevucite na tablu sa uslovima zadatka br. 4

Nekoliko zemalja odlučilo je da kao simbol svoje države koristi zastavu u obliku tri horizontalne pruge jednake širine, ali različitih boja: bijela, plava, crvena. Koliko zemalja može koristiti takve simbole, pod uslovom da svaka država ima svoju zastavu, različitu od drugih?

Kliznite po ploči s rješenjem

Prva metoda: označite boje pruga s prvim slovima naziva boja

B – bijela, K – crvena, C – plava.

Rešimo grubom silom:

BSK, BKS, SBK, SKB, KBS, KSB

Ukupno postoji šest opcija.

Drugi način:

Uzmite olovke i nacrtajte zastavice

Pažljivo slušaju, gledaju slajdove, razmišljaju, analiziraju, klasifikuju, pamte.

Upoznajte se sa modelima i dijagramima za rešavanje problema u zavisnosti od specifičnih uslova.

Prevucite na tablu sa uslovima zadatka br. 5

U porodici ima 4 osobe, a za stolom u kuhinji su 4 stolice. Porodica je odlučila da svako veče tokom večere sedi na ove 4 stolice na drugačiji način. Koliko dana članovi porodice mogu ovo raditi bez ponavljanja?

Kliznite po ploči s rješenjem

Drugo rješenje

Radi jasnoće, obojimo stolice u različite boje.

Popravimo crvenu stolicu na vrhu i preuredimo ostale tri, dobićemo šest opcija.

Uradićemo istu operaciju sa preostalim bojama, dobićemo 6 * 4 = 24 različite opcije.

Drugi način:

Svaki član porodice može sesti na prvu stolicu, odnosno 4 opcije; na drugom – 3 osobe, pošto jedan član porodice već sjedi; za trećeg – 2 osobe as

dvoje sjede; na četvrtom je samo jedan jer tri člana porodice već sjede.

Dakle, pomnožimo sve opcije

4*3*2*1= 24

Pažljivo slušaju, gledaju slajdove, razmišljaju, analiziraju, klasifikuju, pamte.

Upoznajte se sa modelima i dijagramima za rešavanje problema u zavisnosti od specifičnih uslova.

Prevucite na tablu sa uslovima zadatka br. 6

Vasya je odlučio otići na Novu godinu

karneval u kostimu mušketira. U iznajmljivanju mu je ponuđen izbor: tri vrste pantalona, ​​dva kamizola, tri šešira. Koliko se različitih karnevalskih kostima može napraviti od ovih predmeta?

Kliznite po ploči s rješenjem

Označimo: prva kapica Š1, druga – Š2, treća – Š3

1) na slajdu je prikazan korijen drveta, u obliku znaka *.

2) pantalone prvog nivoa tri;

3) kamisol drugog nivoa dva;

4) treći nivo tri kape;

Ukupno 18 opcija

Ili jednostavno pomnožite "nivoe"

3*2*3=18

Pažljivo slušaju, gledaju slajdove, razmišljaju, analiziraju, klasifikuju, pamte.

Upoznajte se sa modelima i dijagramima za rešavanje problema u zavisnosti od specifičnih uslova.

Prevucite na tablu sa uslovima zadatka br. 7

Kada su se sreli, 7 patuljaka su se rukovali. Koliko je rukovanja obavljeno?

Sedam patuljaka je odlučilo da razmene fotografije. Koliko fotografija vam treba?

Kliznite po ploči s rješenjem: a)

Kliznite po ploči sa rješenjem: b)

Ova dva zadatka su vrlo slična, ali se ipak razlikuju

Prilikom rješavanja takvih problema bolje je koristiti tablicu.

1) Nacrtajmo tabelu 8*8, prvi red i prva kolona su patuljci.

2) Precrtajmo dijagonalu tabele na isti način na koji patuljak ne može da pozdravi samog sebe.

3) Ćelije su ko je koga pozdravio.

4) Donji deo tabele ponavlja gornji.

Prvi patuljak je rekao zdravo drugom = drugi patuljak je rekao zdravo prvom.

Ukupno je 21 rukovanje.

Problem b) razlikuje se od a) po tome što je potreban

smatrajte dno tabele kao

prvi patuljak je dao fotografiju drugom, NEJEDNAKO drugi patuljak je dao fotografiju prvom.

Ukupno 42 fotografije.

Pažljivo slušaju, gledaju slajdove, razmišljaju, analiziraju, klasifikuju, pamte.

Upoznajte se sa modelima i dijagramima za rešavanje problema u zavisnosti od specifičnih uslova.

Sistematizacija znanja

Sistematizirati metode za rješavanje kombinatornih problema.

Slajdovi na tabli

I sljedeći slajd,

Slajdovi rješenja zadatka br. 7

Upoznali smo se sa tri metode rešavanja: 1) stablo opcija; 2) preterivanje;

3) tabelarni prikaz podataka

Pažljivo slušaju, gledaju slajdove, razmišljaju, analiziraju, klasifikuju, pamte.

Sistematizacija znanja u tri

metode.

Ovladavanje novim znanjem

Dajte definiciju

razvoj kombinatornih problema.

Kliznite po ploči

Zamolite djecu da svojim riječima definišu koncept „kombinatornih problema“.

Odgovori na pitanje

Uspostavljanje analogija.

Vještina povjerovana

vat.

Identifikujte tri metode za rješavanje problema ove vrste.

Sljedeći slajd;

Slajd za rješavanje zadatka br.7

Zamolite djecu da svojim riječima govore o tri metode rješavanja

kombinatorni problemi

Odgovori na pitanje

Vještina povjerovana

vat.

Odabir najefikasnijih načina rješavanja problema ovisno o konkretnim rješenjima

Izvući zaključak o multivarijantnom rješenju kombinatornih problema

Slajd

Pitajte djecu da li mislite da se svi kombinatorni problemi mogu riješiti različitim metodama?

Nakon prikazivanja slajda, fizičko vaspitanje. samo minut (3 učenika se pozivaju na ploču i sjede za svojim stolovima na različite načine)

Odgovori na pitanje

Kreirajte modele i dijagrame za rješavanje problema ovisno o specifičnim uvjetima

Reflex

ove

Samostalan rad u grupama, malim grupama, individualno.

dijagonale

na pola

jednaka

pod pravim uglom

Da

Da

Da

Na svakom stolu nalazi se list (A4 format) sa sedam zadataka (Prilog br. 1)

Slajd sa odgovorima

Tabela na tabli (timski odgovori)

Coman-

da #1

Coman-

da #2

7 a

7 b

Iz razreda se biraju dva tima od 8-12 ljudi. Dobiju zadatak:

1. Raspodijeli po zadatku: jedan ili dva učenika po zadatku.

2. Za rješenje nije dodijeljeno više od 7 minuta.

Napomena: nastavnik može kreirati timove, nema zadatka po zadatku, samo se sama djeca moraju rasporediti u roku od 1 minute. Ako ne mogu, onda će na osnovu lokacije djece učenik dobiti svoj zadatak.

1. za svako tačno rešeno

tim će dobiti 1 bod za zadatak

1. provjerava razred: odgovori timova su ispisani na tabli. Djeca koja su riješila svoj problem izgovaraju odgovor, a dežurni ga zapisuje.

2. tačne odgovore na slajdu

Učenici koji nisu uključeni u timove rješavaju bilo koji broj zadataka od sedam po svom izboru.

Samostalan rad obavljati u timu, u paru, pojedinačno.

Kombinacija individualnog samostalnog rada i timske saradnje

Objašnjenja domaćeg zadatka

Obezbedite

dječije razumijevanje svrhe, sadržaja i metoda implementacije

domaći zadaci.

Svaki učenik na svom stolu ima tekst ovog domaćeg zadatka.

zadaci.

Projektna domaća zadaća

Smisli tri za svakoga

bilo kakvih kombinatornih problema.

Grupa ne više od 5 osoba

Ove zadatke ćemo (nastavnik i učenici) ubuduće koristiti u kviz takmičenjima, i to ne samo u razredu, već iu školi.

Odnosno, napravićemo banku "zadataka za kvizove"

Razmislite o uslovima za ispunjavanje zadatka:

1) pojedinačno ili u grupi;

2) šta koristiti pri izradi zadataka, koje resurse.

Samoregulacija

cija, razvoj samosvesti, odgovornosti

nema veze

Dodatak br. 1

Zadatak br. 1

U trpezariji za doručak možete izabrati lepinju, pitu sa kupusom, pitu sa krompirom, sendvič, a možete ga popiti čajem ili kompotom. Od koliko opcija doručka možete birati?

Zadatak br. 2

Od zemlje „Matematika“ do zemlje „Književnost“ vode četiri puta, a od zemlje „Književnost“ do zemlje „Fizičko vaspitanje“ pet puteva. Na koliko načina možete stići od zemlje “Matematika” do

zemlja “Fizičko vaspitanje” preko zemlje “Književnost”?

Zadatak br. 3

Sigurna šifra se sastoji od slova i brojeva, pri čemu je slovo na prvom mjestu (na primjer, A7). Koliko se različitih verzija šifre može napraviti koristeći slova A, M, F i brojeve 1, 4, 6, 9?

Zadatak br. 4

Nekoliko zemalja odlučilo je da kao simbol svoje države koristi zastavu u obliku četiri horizontalne pruge jednake širine, ali različitih boja: bijela, plava, crvena, zelena. Koliko zemalja može koristiti takve simbole, pod uslovom da svaka država ima svoju zastavu, različitu od drugih?

Problem #5

U porodici je 5 osoba, a za stolom u kuhinji je 5 stolica. Porodica je odlučila da svako veče tokom večere sedi na ovih 5 stolica na drugačiji način. Koliko dana članovi porodice mogu ovo raditi bez ponavljanja?

Problem #6

Vasja je odlučio da ode na novogodišnji karneval obučen kao musketar. U iznajmljivanju mu je ponuđen izbor: četiri vrste pantalona, ​​dvije kamizole, dva šešira. Koliko se različitih karnevalskih kostima može napraviti od ovih predmeta?

Problem br. 7

Kada su se sreli, 4 patuljka su se rukovala. Koliko je rukovanja obavljeno?

Pet patuljaka je odlučilo da razmene fotografije. Koliko fotografija vam treba?

Dodatak br. 2

Domaća zadaća (projektna aktivnost)

Projektna domaća zadaća

Smisli tri za svakoga

bilo kakvih kombinatornih problema.

Kada dođete do problema možete koristiti: Udžbenik „Vilenkin. Matematika 5; druge knjige; Internet resursi.

Možete se pridružiti grupama, ali uslov je

Svakom učeniku preostaju tri zadatka.

Grupa ne više od 5 osoba

3) UMK „Matematika Dorofejeva 5”;

4) Internet resursi (gif1000)

Treba napomenuti da je kombinatorika samostalna grana više matematike (a ne dio tervera) i o ovoj disciplini su napisani teški udžbenici čiji sadržaj, ponekad, nije lakši od apstraktne algebre. Međutim, mali dio teorijskog znanja bit će nam dovoljan, a u ovom članku pokušat ću u pristupačnom obliku analizirati osnove teme s tipičnim kombinatornim problemima. I mnogi od vas će mi pomoći ;-)

sta cemo da radimo? U užem smislu, kombinatorika je izračunavanje različitih kombinacija koje se mogu napraviti iz određenog skupa diskretno objekata. Pod objektima se podrazumijevaju bilo koji izolirani predmeti ili živa bića - ljudi, životinje, gljive, biljke, insekti itd. Istovremeno, kombinatoriku uopće nije briga što se set sastoji od tanjira griz kaše, lemilice i močvarne žabe. Od suštinske je važnosti da se ovi objekti mogu nabrojati - postoje tri (diskretnost) a bitno je da nijedan od njih nije identičan.

Bavili smo se dosta toga, sada o kombinacijama. Najčešći tipovi kombinacija su permutacije objekata, njihov izbor iz skupa (kombinacija) i distribucija (pozicioniranje). Hajde da vidimo kako se to sada dešava:

Permutacije, kombinacije i plasmani bez ponavljanja

Nemojte se plašiti nejasnih termina, pogotovo jer neki od njih zaista nisu baš dobri. Počnimo s repom naslova - šta znači “ nema ponavljanja"? To znači da ćemo u ovom dijelu razmatrati skupove koji se sastoje od razne objekata. Na primjer, ... ne, neću ponuditi kašu sa lemilom i žabom, bolje je nešto ukusnije =) Zamislite da su se na stolu ispred vas materijalizirale jabuka, kruška i banana ( ako ih imate, situacija se može simulirati u stvarnosti). Plodove polažemo s lijeva na desno sljedećim redoslijedom:

jabuka/kruška/banana

Prvo pitanje: Na koliko načina se mogu preurediti?

Jedna kombinacija je već napisana gore, a sa ostalima nema problema:

jabuka/banana/kruška
kruška / jabuka / banana
kruška / banana / jabuka
banana/jabuka/kruška
banana/kruška/jabuka

Ukupno: 6 kombinacija ili 6 permutacije.

Dobro, nije bilo teško nabrojati sve moguće slučajeve, ali šta ako ima više objekata? Sa samo četiri različita voća, broj kombinacija će se značajno povećati!

Molimo otvorite referentni materijal (zgodno je odštampati priručnik) a u tački br. 2 pronaći formulu za broj permutacija.

Bez muke - 3 objekta se mogu preurediti na različite načine.

Drugo pitanje: Na koliko načina možete izabrati a) jedno voće, b) dva voća, c) tri voća, d) barem jedno voće?

Zašto odabrati? Tako smo u prethodnoj tački podigli apetit - da bismo jeli! =)

a) Jedno voće se može izabrati, očigledno, na tri načina - uzeti ili jabuku, krušku ili bananu. Formalni obračun se vrši prema formula za broj kombinacija:

Unos u ovom slučaju treba shvatiti na sljedeći način: "na koliko načina možete odabrati 1 voće od tri?"

b) Nabrojimo sve moguće kombinacije dva voća:

jabuka i kruška;
jabuka i banana;
kruške i banane.

Broj kombinacija može se lako provjeriti pomoću iste formule:

Unos se shvata na sličan način: "na koliko načina možete izabrati 2 voća od tri?"

c) I na kraju, postoji samo jedan način da odaberete tri voća:

Usput, formula za broj kombinacija ostaje značajna za prazan uzorak:
Na ovaj način ne možete odabrati ni jedno voće - u stvari, ništa ne uzimajte i to je to.

d) Na koliko načina možete uzeti barem jedan voće? Uslov „barem jedan“ podrazumeva da smo zadovoljni sa 1 voćem (bilo koji) ili bilo koja 2 voća ili sva 3 voća:
koristeći ove metode možete odabrati barem jedno voće.

Čitaoci koji su pažljivo proučili uvodnu lekciju na teorija vjerovatnoće, već smo nešto pogodili. Ali više o značenju znaka plus kasnije.

Za odgovor na sledeće pitanje potrebna su mi dva volontera... ...Pa pošto niko neće, onda ću te zvati u tablu =)

Pitanje tri: Na koliko načina možete podijeliti po jedno voće Daši i Nataši?

Da biste podijelili dva ploda, prvo ih trebate odabrati. Prema paragrafu "be" prethodnog pitanja, to se može uraditi na načine, prepisat ću ih:

jabuka i kruška;
jabuka i banana;
kruške i banane.

Ali sada će biti dvostruko više kombinacija. Uzmimo u obzir, na primjer, prvi par voća:
Dašu možete počastiti jabukom, a Natašu kruškom;
ili obrnuto - Daša će dobiti krušku, a Nataša jabuku.

I takva permutacija je moguća za svaki par voća.

Zamislite istu grupu studenata koja je išla na ples. Na koliko načina se dečak i devojčica mogu upariti?

Na načine možete odabrati 1 mladića;
načini na koje možete izabrati 1 djevojku.

Dakle, jedan mladić I Možete izabrati jednu devojku: načine.

Kada se iz svakog skupa odabere 1 objekat, važi sledeći princip brojanja kombinacija: “ svaki objekat iz jednog skupa može formirati par sa svima objekt drugog skupa."

Odnosno, Oleg može pozvati bilo koju od 13 djevojaka na ples, Evgeny također može pozvati bilo koju od trinaest, a ostali mladi ljudi imaju sličan izbor. Ukupno: mogući parovi.

Treba napomenuti da u ovom primjeru „povijest“ formiranja para nije bitna; međutim, ako se uzme u obzir inicijativa, broj kombinacija se mora udvostručiti, jer svaka od 13 djevojčica može pozvati bilo kojeg dječaka na ples. Sve zavisi od uslova određenog zadatka!

Sličan princip vrijedi i za složenije kombinacije, na primjer: na koliko načina možete izabrati dva mladića? I dve devojke da učestvuju u KVN skeču?

Union I jasno nagoveštava da kombinacije treba pomnožiti:

Moguće grupe umjetnika.

drugim riječima, svaki par dječaka (45 jedinstvenih parova) može nastupiti sa bilo koji par djevojaka (78 unikatnih parova). A ako uzmemo u obzir raspodjelu uloga između sudionika, kombinacija će biti još više. ...Stvarno želim, ali ću se ipak suzdržati od nastavka kako vam ne bih usadio odbojnost prema studentskom životu =).

Pravilo za množenje kombinacija vrijedi i za veći broj množitelja:

Problem 8

Koliko ima trocifrenih brojeva koji su djeljivi sa 5?

Rješenje: radi jasnoće, označimo ovaj broj sa tri zvjezdice: ***

IN stotine mesta Možete napisati bilo koji od brojeva (1, 2, 3, 4, 5, 6, 7, 8 ili 9). Nula nije prikladna, jer u ovom slučaju broj prestaje biti trocifreni.

Ali unutra desetke mjesto(“u sredini”) možete odabrati bilo koju od 10 cifara: .

Prema uslovu, broj mora biti djeljiv sa 5. Broj je djeljiv sa 5 ako se završava na 5 ili 0. Dakle, u nižem redu zadovoljavamo se sa 2 cifre.

Ukupno, postoji: trocifreni brojevi koji su djeljivi sa 5.

U ovom slučaju, rad se dešifruje na sljedeći način: „9 načina na koje možete odabrati broj stotine mesta I 10 načina da odaberete broj desetke mjesto I 2 načina ulaska jedinica cifra»

Ili još jednostavnije: “ svaki od 9 cifara do stotine mesta kombajni sa svakim od 10 cifara desetke mjesto i sa svakim od dvije cifre do jedinica cifra».

Odgovori: 180

A sada...

Da, skoro sam zaboravio na obećani komentar na problem broj 5, u kojem Boru, Dimi i Volodji može da se podeli po jedna karta na različite načine. Množenje ovdje ima isto značenje: načini uklanjanja 3 karte iz špila I u svakom uzorak ih preuredi na načine.

A sada problem koji treba riješiti sami... sad ću smisliti nešto zanimljivije... neka bude o istoj ruskoj verziji blackjacka:

Problem 9

Koliko dobitnih kombinacija od 2 karte ima kada se igra "poen"?

Za one koji ne znaju: dobitna kombinacija je 10 + ACE (11 poena) = 21 poen i, uzmimo u obzir dobitnu kombinaciju od dva asa.

(redoslijed karata u bilo kojem paru nije bitan)

Kratko rješenje i odgovor na kraju lekcije.

Usput, nemojte smatrati primjer primitivnim. Blackjack je gotovo jedina igra za koju postoji matematički zasnovan algoritam koji vam omogućava da pobijedite kazino. Zainteresovani mogu lako pronaći mnogo informacija o optimalnoj strategiji i taktici. Istina, takvi majstori vrlo brzo završe na crnoj listi svih ustanova =)

Vrijeme je za konsolidaciju materijala pokrivenog s nekoliko solidnih zadataka:

Problem 10

Vasya kod kuće ima 4 mačke.

a) na koliko načina se mačke mogu smjestiti u uglove prostorije?
b) na koliko načina možete pustiti mačke u šetnju?
c) na koliko načina Vasja može pokupiti dvije mačke (jednu lijevo, drugu desno)?

Hajde da odlučimo: prvo, opet treba obratiti pažnju na činjenicu da se problem rješava drugačije predmete (čak i ako su mačke identični blizanci). Ovo je veoma važan uslov!

a) Tišina mačaka. Podložno ovom izvršenju sve mačke odjednom
+ njihova lokacija je važna, tako da ovdje postoje permutacije:
koristeći ove metode možete smjestiti mačke u uglove sobe.

Ponavljam da je prilikom permutiranja bitan samo broj različitih objekata i njihova relativna pozicija. Ovisno o Vasjinom raspoloženju, ona može sjesti životinje u polukrug na sofi, u nizu na prozorskoj dasci itd. – u svim slučajevima bit će 24 permutacije Radi praktičnosti, zainteresirani mogu zamisliti da su mačke višebojne (na primjer, bijele, crne, crvene i tabby) i navesti sve moguće kombinacije.

b) Na koliko načina možete pustiti mačke u šetnju?

Pretpostavlja se da mačke idu u šetnju samo kroz vrata, a pitanje implicira ravnodušnost u pogledu broja životinja - u šetnju mogu ići 1, 2, 3 ili sve 4 mačke.

Računamo sve moguće kombinacije:

Na načine možete pustiti jednu mačku (bilo koju od četiri) u šetnju;
načine na koje možete pustiti dvije mačke u šetnju (navedite opcije sami);
na način na koji možete pustiti tri mačke u šetnju (jedna od četiri sjedi kod kuće);
Na ovaj način možete osloboditi sve mačke.

Vjerovatno ste pogodili da rezultirajuće vrijednosti treba zbrojiti:
načine na koje možete pustiti mačke u šetnju.

Za entuzijaste nudim komplikovanu verziju problema - kada bilo koja mačka u bilo kom uzorku može nasumično izaći van, i kroz vrata i kroz prozor na 10. spratu. Bit će primjetan porast kombinacija!

c) Na koliko načina Vasja može uzeti dvije mačke?

Situacija uključuje ne samo odabir 2 životinje, već i njihovo stavljanje u svaku ruku:
Na ove načine možete pokupiti 2 mačke.

Drugo rješenje: pomoću metoda možete odabrati dvije mačke I načini sadnje svaki par pri ruci:

Odgovori: a) 24, b) 15, c) 12

Pa, da očistim svoju savjest, nešto konkretnije o množenju kombinacija... Neka Vasya ima 5 dodatnih mačaka =) Na koliko načina možete pustiti 2 mačke u šetnju? I 1 mačka?

Odnosno, sa svaki može se pustiti nekoliko mačaka svaki mačka.

Još jedna harmonika za samostalno rješenje:

Problem 11

Tri putnika su se ukrcala u lift u zgradi od 12 spratova. Svi, bez obzira na ostale, mogu sa jednakom vjerovatnoćom izaći na bilo koji (počevši od 2.) sprata. na koliko načina:

1) putnici mogu sići na istom spratu (redosled izlaska nije bitan);
2) dvije osobe mogu sići na jednom spratu, a treće na drugom;
3) ljudi mogu izaći na različite spratove;
4) mogu li putnici izaći iz lifta?

I tu često opet pitaju, pojašnjavam: ako 2 ili 3 osobe izlaze na istom spratu, onda redosled izlaska nije bitan. RAZMISLITE, koristite formule i pravila za dodavanje/množenje kombinacija. U slučaju poteškoća, korisno je da putnici daju imena i nagađaju u kojim kombinacijama mogu izaći iz lifta. Nema potrebe da se uzrujavate ako nešto ne uspije, na primjer, tačka broj 2 je prilično podmukla, međutim, jedan od čitatelja je pronašao jednostavno rješenje i još jednom se zahvaljujem na vašim pismima!

Potpuno rješenje sa detaljnim komentarima na kraju lekcije.

Poslednji pasus je posvećen kombinacijama koje se takođe često javljaju - prema mojoj subjektivnoj proceni, u otprilike 20-30% kombinatornih problema:

Permutacije, kombinacije i plasmani s ponavljanjima

Navedene vrste kombinacija su navedene u paragrafu br. 5 referentnog materijala Osnovne formule kombinatorike, međutim, neki od njih možda neće biti vrlo jasni nakon prvog čitanja. U ovom slučaju, preporučljivo je prvo se upoznati s praktičnim primjerima, a tek onda shvatiti opću formulaciju. idemo:

Permutacije s ponavljanjima

U permutacijama s ponavljanjima, kao u "običnim" permutacijama, svih mnogo objekata odjednom, ali postoji jedna stvar: u ovom skupu se ponavlja jedan ili više elemenata (objekata). Ispunite sljedeći standard:

Problem 12

Koliko se različitih kombinacija slova može dobiti preuređivanjem kartica sa sljedećim slovima: K, O, L, O, K, O, L, b, Ch, I, K?

Rješenje: u slučaju da su sva slova različita, tada bi se morala primijeniti trivijalna formula, ali je potpuno jasno da će za predloženi set karata neke manipulacije raditi „u praznom hodu“, na primjer, ako zamijenite bilo koje dvije karte sa slovima “K” “ u bilo kojoj riječi, dobijate istu riječ. Štaviše, fizički karte mogu biti veoma različite: jedna može biti okrugla sa ispisanim slovom „K“, druga može biti četvrtasta sa nacrtanim slovom „K“. Ali prema značenju zadatka, čak i takve karte smatraju se istim, budući da uvjet pita o kombinacijama slova.

Sve je krajnje jednostavno - samo 11 kartica, uključujući i slovo:

K – ponovljeno 3 puta;
O – ponovljeno 3 puta;
L – ponovljeno 2 puta;
b – ponovljeno 1 put;
H – ponovljeno 1 put;
I - ponovljeno 1 put.

Provjerite: 3 + 3 + 2 + 1 + 1 + 1 = 11, to je ono što je trebalo provjeriti.

Prema formuli broj permutacija sa ponavljanjima:
mogu se dobiti različite kombinacije slova. Više od pola miliona!

Da biste brzo izračunali veliku faktorijalnu vrijednost, zgodno je koristiti standardnu ​​Excel funkciju: unesite u bilo koju ćeliju =ČINJENICA(11) i pritisnite Enter.

U praksi je sasvim prihvatljivo ne napisati opštu formulu i, osim toga, izostaviti jedinične faktorijele:

Ali preliminarni komentari o ponovljenim pismima su potrebni!

Odgovori: 554400

Još jedan tipičan primjer permutacija s ponavljanjem javlja se u problemu postavljanja šahovskih figura, koji se može naći u skladištu gotova rješenja u odgovarajućem pdf-u. A za nezavisno rješenje, smislio sam manje formulisan zadatak:

Problem 13

Aleksej se bavi sportom, a 4 dana u nedelji - atletikom, 2 dana - vežbama snage i 1 dan odmora. Na koliko načina može sebi da kreira nedeljni raspored?

Formula ovdje ne funkcionira jer uzima u obzir slučajne zamjene (na primjer, zamjena vježbi snage u srijedu s vježbama snage u četvrtak). I opet - u stvari, iste 2 treninga snage mogu se jako razlikovati jedna od druge, ali u kontekstu zadatka (sa stanovišta rasporeda) smatraju se istim elementima.

Rješenje u dva reda i odgovor na kraju lekcije.

Kombinacije sa ponavljanjima

Karakteristična karakteristika ove vrste kombinacije je da se uzorak izvlači iz nekoliko grupa, od kojih se svaka sastoji od identičnih objekata.

Danas su svi vredno radili, pa je vrijeme da se osvježite:

Problem 14

Studentska menza prodaje kobasice u tijestu, kolače od sira i krofne. Na koliko načina možete kupiti pet pita?

Rješenje: odmah obratite pažnju na tipičan kriterijum za kombinacije sa ponavljanjima - prema uslovu, nije skup objekata kao takvih koji se nudi na izbor, već razne vrste objekti; Pretpostavlja se da je u prodaji najmanje pet hot dogova, 5 kolača od sira i 5 krofni. Pite u svakoj grupi su, naravno, različite - jer apsolutno identične krofne mogu se simulirati samo na kompjuteru =) Međutim, fizičke karakteristike pita nisu bitne za svrhu problema, a hrenovke / kolači od sira / krofne u svojim grupama se smatraju istim.

Šta bi moglo biti u uzorku? Prije svega, treba napomenuti da će u uzorku sigurno biti identičnih pita (pošto biramo 5 komada, a postoje 3 vrste na izbor). Ovdje postoje opcije za svaki ukus: 5 viršle, 5 kolača od sira, 5 krofni, 3 viršle + 2 kolača od sira, 1 hot dog + 2 kolača od sira + 2 krofne itd.

Kao i kod "običnih" kombinacija, redosled odabira i postavljanja pita u selekciji nije bitan - samo ste odabrali 5 komada i to je to.

Koristimo formulu broj kombinacija sa ponavljanjima:
Na ovaj način možete kupiti 5 pita.

Bon appetit!

Odgovori: 21

Kakav zaključak se može izvući iz mnogih kombinatornih problema?

Ponekad je najteže razumjeti stanje.

Sličan primjer za nezavisno rješenje:

Problem 15

Novčanik sadrži prilično veliki broj kovanica od 1, 2, 5 i 10 rubalja. Na koliko načina se tri novčića mogu izvaditi iz novčanika?

U svrhu samokontrole, odgovorite na nekoliko jednostavnih pitanja:

1) Mogu li svi novčići u uzorku biti različiti?
2) Navedite „najjeftiniju“ i „najskuplju“ kombinaciju novčića.

Rješenje i odgovori na kraju lekcije.

Iz ličnog iskustva mogu reći da su kombinacije s ponavljanjima najrjeđi gost u praksi, što se ne može reći za sljedeće vrste kombinacija:

Položaji sa ponavljanjima

Iz skupa koji se sastoji od elemenata biraju se elementi, a redoslijed elemenata u svakoj selekciji je važan. I sve bi bilo u redu, ali prilično neočekivana šala je da možemo odabrati bilo koji predmet iz originalnog skupa koliko god puta želimo. Slikovito rečeno, “mnoštvo se neće smanjiti”.

Kada se to dešava? Tipičan primjer je kombinovana brava s nekoliko diskova, ali zbog tehnološkog razvoja relevantnije je uzeti u obzir njenog digitalnog potomka:

Problem 16

Koliko četvorocifrenih PIN kodova postoji?

Rješenje: zapravo, za rješavanje problema dovoljno je poznavanje pravila kombinatorike: na načine možete odabrati prvu cifru PIN koda I načina - druga cifra PIN koda I na toliko načina - treći I isti broj - četvrti. Dakle, prema pravilu množenja kombinacija, četverocifreni pin kod se može sastaviti na: načine.

A sada koristeći formulu. U skladu sa uslovom, nudi nam se set brojeva iz kojih se biraju i raspoređuju brojevi određenim redosledom, dok se brojevi u uzorku mogu ponoviti (tj. bilo koja cifra originalnog skupa može se koristiti proizvoljan broj puta). Prema formuli za broj plasmana sa ponavljanjima:

Odgovori: 10000

Šta mi ovdje pada na pamet... ...ako bankomat "pojede" karticu nakon trećeg neuspješnog pokušaja unosa PIN koda, onda su šanse da ga nasumično podignete vrlo male.

A ko je rekao da kombinatorika nema praktičnog značenja? Kognitivni zadatak za sve čitaoce sajta:

Problem 17

Prema državnom standardu, registarska tablica automobila sastoji se od 3 broja i 3 slova. U ovom slučaju, broj sa tri nule je neprihvatljiv, a slova se biraju iz skupa A, B, E, K, M, N, O, P, S, T, U, X (koriste se samo ona ćirilična slova čiji se pravopis podudara sa latiničnim slovima).

Koliko se različitih registarskih tablica može kreirati za regiju?

Usput, nije ih toliko mnogo. U velikim regijama nema dovoljno takve količine, pa za njih postoji nekoliko kodova za natpis RUS.

Rješenje i odgovor nalaze se na kraju lekcije. Ne zaboravite da koristite pravila kombinatorike ;-) ...Hteo sam da pokažem šta je ekskluzivno, ali se pokazalo da nije ekskluzivno =) Pogledao sam na Wikipediji - tamo ima kalkulacija, mada bez komentara. Iako u obrazovne svrhe, vjerovatno ga je malo tko riješio.

Naša uzbudljiva lekcija je došla do kraja, i na kraju želim reći da niste gubili vrijeme - iz razloga što kombinatoričke formule nalaze još jednu vitalnu praktičnu primjenu: nalaze se u raznim problemima u teorija vjerovatnoće,
i u problemi koji uključuju klasično određivanje vjerovatnoće– posebno često =)

Hvala svima na aktivnom učešću i vidimo se uskoro!

Rješenja i odgovori:

Zadatak 2: Rješenje: pronađite broj svih mogućih permutacija 4 karte:

Kada se kartica sa nulom stavi na 1. mjesto, broj postaje trocifren, tako da ove kombinacije treba isključiti. Neka nula bude na prvom mjestu, tada se preostale 3 cifre u nižim znamenkama mogu preurediti na različite načine.

Napomena : jer Budući da postoji samo nekoliko kartica, ovdje je lako navesti sve opcije:
0579
0597
0759
0795
0957
0975

Dakle, od predloženog skupa možemo napraviti:
24 – 6 = 18 četvorocifrenih brojeva
Odgovori : 18

Zadatak 4: Rješenje: na načine na koje možete odabrati 3 karte od 36. I
2) "Najjeftiniji" set sadrži 3 novčića rublje, a "najskuplji" - 3 novčića od deset rubalja.

Problem 17: Rješenje: koristeći ove metode, možete kreirati digitalnu kombinaciju broja automobila, dok jednu od njih (000) treba isključiti: .
koristeći ove metode, možete kreirati kombinaciju slova broja registarske tablice.
Prema pravilu množenja kombinacija, zbroj se može napraviti:
registarske tablice
(svaki digitalna kombinacija je kombinovana sa svakim kombinacija slova).
Odgovori : 1726272

U mnogim kombinatornim problemima, direktno pronalaženje broja opcija koje nas zanimaju ispada da je teško. Međutim, uz određenu promjenu uvjeta problema, možete pronaći brojne opcije koje premašuju original za poznati broj puta. Ova tehnika se zove metoda višestrukog brojanja.

1. Koliko anagrama ima riječ RAZRED?

Poteškoća je u tome što u ovoj riječi postoje dva identična slova C. Privremeno ćemo ih smatrati različitim i označavati C 1 i C 2. Tada će broj anagrama biti jednak 5! = 120. Ali one riječi koje se razlikuju jedna od druge samo preuređivanjem slova C 1 i C 2 su zapravo isti anagram! Stoga je 120 anagrama podijeljeno u parove identičnih, tj. potreban broj anagrama je 120/2 = 60.

2. Koliko anagrama ima riječ CHARADA?

Računajući tri slova A kao različita slova A 1, A 2, A 3, dobijamo 6! anagrami Ali riječi koje se prave jedna od druge samo preuređivanjem slova A 1, A 2, A 3 zapravo su isti anagram. Jer ih ima 3! permutacije slova A 1, A 2, A 3, originalno dobijenih 6! Anagrami su podijeljeni u grupe po 3! identičan, a broj različitih anagrama ispada 6!/3! = 120.

3. Koliko ima četverocifrenih brojeva koji sadrže barem jednu parnu cifru?

Nađimo broj "nepotrebnih" četverocifrenih brojeva, čiji zapis sadrži samo neparne cifre. Takvih brojeva ima 5 4 = 625, ali ima ukupno 9000 četvorocifrenih brojeva, tako da je potreban broj „potrebnih“ brojeva 9000 – 625 = 8375.

1. Pronađite broj anagrama za riječi VERESK, BALAGAN, CITYMAN.
2. Pronađite broj anagrama za riječi BAOBAB, BALADA, TURN, ANAGRAM, MATEMATIKA, KOMBINATORIKA, ODBRANA.
3. Na koliko načina možete ugostiti 7 posetilaca u tri hotelske sobe: jednokrevetne, dvokrevetne i četvorokrevetne?
4. U frižideru se nalaze dve jabuke, tri kruške i četiri narandže. Svaki dan devet dana zaredom Petya dobija po jedan komad voća. Na koliko načina se to može učiniti?
5. Od sedam najboljih skijaša škole, za učešće na gradskim takmičenjima mora se izabrati ekipa od tri. Na koliko načina se to može učiniti?
6. Profesor je prije ispita obećao da će dati loše ocjene polovini ispitanika. Na ispit je došlo 20 studenata. Na koliko načina može ispuniti svoje obećanje?
7. Koliko se riječi može sastaviti od pet slova A i ne više od tri slova B?
8. Dostupni su sladoled od čokolade, jagoda i mlijeka. Na koliko načina možete kupiti tri sladoleda?
9. Prilikom pripreme pice siru se dodaju različite komponente kako bi se dobio poseban ukus. Bill ima na raspolaganju luk, pečurke, paradajz, papriku i inćune, a sve to, po njegovom mišljenju, može da se doda siru. Koliko vrsta pizza Bill može napraviti?
10. Svjedok zločinačkog obračuna prisjetio se da su kriminalci pobjegli mercedesom na čijoj su tablici bila slova T, Z, U i brojevi 3 i 7 (broj je red koji prvo sadrži tri slova, a zatim tri broja) . Koliko ima takvih brojeva?
11. Koliko dijagonala ima u konveksnoj n-kvadrat?
12. Koliko stvari ima? n-digitalni brojevi?
13. Koliko ima desetocifrenih brojeva koji imaju najmanje dvije identične cifre?
14. Kocka se baca tri puta. Među svim mogućim nizovima rezultata, postoje i oni u kojima se bar jednom baca šestica. koliko ih ima?
15. Koliko petocifrenih brojeva ima cifru 1 u svom zapisu?
16. Na koliko načina se bijeli i crni kralj mogu postaviti na šahovsku ploču, a da se ne udare jedan drugog?
17. Koliko djelitelja ima broj 10800?

Za konstruisanje odgovarajućih matematičkih modela kombinatornih problema koristićemo se matematički aparat teorije skupova. Može se desiti da u datom skupu nije važan redosled elemenata, već je važan samo sastav skupa. Ali postoje problemi u kojima je redoslijed elemenata bitan.

Definicija 1: Red u mnogim od elementi je numerisanje njegovih elemenata prirodnim brojevima, tj. podesiti prikaz
za mnoge
.

2. definicija: Poziva se skup sa datim redosledom naručeni set.

Očigledno, skup koji sadrži više od jednog elementa može se naručiti na više načina.

Na primjer, od dva slova I Naručeni skup možete konstruirati na dva različita načina:

I
.

Tri slova ,I može se nizati na šest načina:

,
,
,
,
,
.

Za četiri slova, nabrajanjem dobijamo 24 različita uređena niza.

Uređeni nizovi elemenata određenog skupa mogu se smatrati distribucijama ili rasporedima ovih elemenata u nizu.

Definicija 3: Neka je dat konačan skup
od elementi. Bilo koji set elementi datog skupa (a elementi u skupu se mogu ponavljati) će biti pozvani -aranžmani .

Kroz koncept aranžmana uvode se osnovne definicije kombinatorike: kombinacije, plasmani i permutacije. Štaviše, svaki od ovih pojmova može se ponavljati ili bez ponavljanja. Ovaj dio će razmotriti kombinatorne formule bez ponavljanja.

Prestrojavanja bez ponavljanja.

definicija 4: Neka
- konačan skup elementi. Permutacije od razne elemente kompleta
sve lokacije su pozvane elemenata određenim redosledom. Označio: (od francuske riječi permutacija- preuređenje).

Uređeni skupovi se smatraju različitim ako se razlikuju bilo po svojim elementima ili po svom redoslijedu.

Definicija 5: Pozivaju se različiti uređeni skupovi koji se razlikuju samo po redoslijedu svojih elemenata permutacije ovog mnoštva.

Posljednja definicija je formulirana sa pozicije teorije skupova.

Definicija 6: Posao uzastopni prirodni brojevi u matematici se označavaju sa i nazovi faktorijel .

Izbor za određivanje uzvičnik može biti zbog činjenice da čak i za relativno male vrijednosti broj veoma veliki. na primjer,
,
,
,
,
,,itd.

Teorema 1: Broj permutacija od različiti elementi se izračunavaju po formuli:

Dokaz. Razmotrimo proizvoljan skup od elementi. Hajde da napravimo sve vrste aranžmana od ovih elementi. Na prvo mjesto aranžmana možete staviti bilo koji od elementi ( metode za odabir prvog elementa). Kada je prvi element odabran i bez obzira na to kako je odabran, može se odabrati drugi element
način. Za odabir trećeg elementa ostaje
metoda itd. Posljednji element se odabire u skladu s tim na jedan način. Tada će, zbog kombinatornog principa množenja, broj takvih rasporeda biti jednak:

Teorema je dokazana.

Primjer 1: Na koliko načina tri prijatelja mogu zauzeti mjesta pod brojevima 1, 2 i 3 u bioskopu?

Rješenje. Broj traženih metoda će biti jednak broju permutacija bez ponavljanja tri elementa:
načine. Ako je potrebno, ove metode se mogu razvrstati.

Permutacije slova riječi se nazivaju anagrami . Otkriven u 3. veku pre nove ere grčki gramatičar Likofron, anagrami i danas privlače pažnju lingvista, pesnika i ljubitelja književnosti. Majstori igara riječima, osim erudicije i velikog rječnika, znaju mnoge tajne vezane za kombinatorne vještine, od kojih su jedna anagrami. Često je potrebno među svim permutacijama odabrati one koje imaju određeno svojstvo. Na primjer, među anagramima riječi "krtica", kojih ima samo
, samo jedan, ne računajući samu riječ "krtica", ima smisla na ruskom – "sud".

Pored linearnih permutacija, mogu se uzeti u obzir i kružne (ili ciklične) permutacije. U ovom slučaju, permutacije koje se transformišu jedna u drugu tokom rotacije smatraju se istim i ne treba ih računati.

Teorema 2: Broj kružnih permutacija od različiti elementi su jednaki

Primjer 2: Na koliko načina se 7 djece može uključiti u kolo?

Rješenje. Broj linearnih permutacija 7 djece bit će jednak
. Ako je okrugli ples već formiran, tada postoji 7 kružnih permutacija za njega, koje se pretvaraju jedna u drugu prilikom okretanja. Ove permutacije ne treba računati, tako da će biti kružne permutacije 7 elemenata .

Položaji bez ponavljanja.

Definicija 7: Neka bude razne predmete. Aranžmani iz elementi po elementi (
) se zovu plasmani bez ponavljanja . Odrediti: . Ovdje se misli na to da se elementi u aranžmanima ne ponavljaju.

U ovoj definiciji, sljedeća pozicija je bitna: ta dva aranžmana su različita, ako se razlikuju u najmanje jednom elementu ili redoslijedu elemenata.

Hajde da damo još jednu definiciju plasmana, ekvivalentnu originalnoj, lakšu za razumevanje.

Definicija 8: Konačno uređeni skupovi se nazivaju plasmani.

Teorema 3: Broj svih plasmana od elementi po elementi bez ponavljanja se izračunavaju po formuli:

Dokaz. Neka postoji proizvoljan skup
, koji se sastoji od elementi. Morate birati između ove sorte raznih elemenata. Štaviše, redosled izbora je važan.

Izbor elemenata se vrši u fazama. Može se odabrati prvi element aranžmana na razne načine. Zatim od preostalih elemenata skupa
izabran je drugi element aranžmana
način. Moguće je odabrati treći element
metoda itd. Zatim da izaberem - element koji imamo
način. Dakle, prema pravilu množenja, broj takvih aranžmana će biti jednak:

Po definiciji, takvi aranžmani su plasmani. Q.E.D.

Primjer 3: Sastanak od 25 ljudi bira predsjedništvo od 3 osobe: 1) predsjedavajući, 2) zamjenik, 3) sekretar. Koliko postoji opcija za izbor prezidijuma?

Rješenje. Prilikom odabira tri osobe od 25, napominjemo da je redoslijed izbora važan, pa će broj predsjedništva biti jednak:

komentar: Broj plasmana bez ponavljanja se također može pronaći pomoću formule:

. (3)

Ako je imenilac razlomka iz formule (3)
, onda je to opšte prihvaćeno
.

komentar: Formula (3) je kompaktna, ali je pri rješavanju zadataka pogodnije koristiti formulu (2). Razlomak na desnoj strani formule (3) može se svesti na cijeli broj. Ovaj broj je jednak broju na desnoj strani formule (2).

Primjer 4: Koliko riječi od dva slova (slova se ne ponavljaju) može se napraviti od 33 slova ruske abecede?

Rješenje. U ovom slučaju ne radi se o riječima u lingvističkom smislu, već o slovnim kombinacijama proizvoljnog sastava.

Tada će broj različitih kombinacija od 2 slova odabrana od 33 slova abecede biti jednak:

.

U ovom slučaju, redosled slova je važan. Ako promijenite 2 slova u riječi, dobićete novu riječ.

komentar: Permutacija bez ponavljanja je poseban slučaj postavljanja bez ponavljanja kada
. Možemo reći da je permutacija iz elemenata je postavljanje elementi po elementi:

U nekim kombinatoričkim problemima, poredak objekata u određenom skupu nije bitan. Važno je samo koji elementi ga čine. U takvim situacijama imamo posla kombinacije.

Kombinacije bez ponavljanja.

Definicija 9: Kombinacije nema ponavljanja od elementi nekog skupa prema elementi (
) su aranžmani koji se međusobno razlikuju kompozicija, Ali nije u redu elementi. Odrediti: (od francuske riječi combinaison- kombinacija).

U ovom slučaju, u aranžmanima Važna je kompozicija, a ne redosled elemenata u podskupu. Ako se dva rasporeda razlikuju samo po redoslijedu elemenata, onda se s gledišta kombinacija ne razlikuju. Elementi u ovim aranžmanima se ne ponavljaju.

Sa stanovišta teorije skupova, definicija kombinacija može se drugačije formulisati.

Definicija 10: Konačni neuređeni skupovi se nazivaju kombinacije.

Dakle, kombinacije su izbor elemenata u kojima je njihov redoslijed potpuno nevažan.

Kombinacije od elementi po trebalo bi da ima manje elemenata od odgovarajućih plasmana. To proizilazi iz činjenice da nije potrebno brojati formacije istog sastava.

Teorema 4: Broj kombinacija nalazi se po sljedećoj formuli:

. (4)

Dokaz. Ako iz proizvoljnog -skup elemenata odabran elemenata, onda se mogu numerisati
na više načina jednakih . Preostalo
elementi mogu biti numerisani
,
, …,ukupno
načine. Štaviše, sama selekcija elementi iz elementi se mogu implementirati načine. Dakle, dobili smo
opcije numeracije za kompletan set elemenata, kojih samo ima . Stoga imamo
, odakle dobijamo:

.

Teorema je dokazana.

komentar: Razlomak na desnoj strani (4) može se svesti na cijeli broj.

Iz formule za broj kombinacija slijedi:

,
,
.

Formula (4) se može transformisati u oblik:
. Ovo pokazuje da je broj plasmana V puta broj odgovarajućih kombinacija . Drugim riječima, prebrojati sve kombinacije , moraju biti isključeni iz svih plasmana podskupovi koji se razlikuju po redu (postojaće komada), tj. podijeljeno po .

Primjer 5: Na koliko načina možete izabrati 3 različite boje od pet dostupnih?

Rješenje. Redoslijed odabira boja nije važan. Bitno je samo koje su boje odabrane. Stoga je broj opcija jednak:
.

Primjer 6: Na koliko načina se trobojne prugaste zastavice mogu sašiti ako postoji materijal u pet različitih boja?

Rješenje. Redoslijed odabira pruga je važan, pa je broj takvih zastavica jednak:
.