Cik daudz dažādu iespēju ir? Kombinatoriskās problēmas (5. klase)

Kombinatorika ir matemātikas nozare, kas pēta jautājumu par to, cik noteikta veida kombinācijas var izveidot no dotajiem objektiem (elementiem).

Reizināšanas noteikums (kombinatorikas pamatformula)

Kopējais veidu skaits, kā no katras grupas var atlasīt vienu elementu un sakārtot tos noteiktā secībā (tas ir, iegūt sakārtotu kopu), ir vienāds ar:

1. piemērs

Monēta tika izmesta 3 reizes. Cik dažādus metienu rezultātus jūs varat sagaidīt?

Risinājums

Pirmajai monētai ir alternatīvas – vai nu galvas, vai astes. Otrajai monētai ir arī alternatīvas utt., t.i. .

Nepieciešamais veidu skaits:

Papildināšanas noteikums

Ja kādas divas grupas un nav kopīgi elementi, tad viena elementa atlasi no , vai no , ...vai no var veikt dažādos veidos.

2. piemērs

Plauktā ir 30 grāmatas, no kurām 20 ir matemātiskās, 6 ir tehniskās un 4 ir ekonomiskās. Cik daudzos veidos var izvēlēties vienu matemātikas vai ekonomikas grāmatu?

Risinājums

Matemātikas grāmatu var atlasīt dažādos veidos, ekonomikas grāmatu - dažādos veidos.

Saskaņā ar summas likumu ir veids, kā izvēlēties matemātikas vai ekonomikas grāmatu.

Izvietojumi un pārkārtojumi

Izvietojumi- Tās ir pasūtītas elementu kolekcijas, kas atšķiras viena no otras vai nu pēc sastāva, vai elementu secības.

Izvietojumi bez atkārtojumiem, kad atlasītais elements netiek atgriezts populācijā pirms nākamā atlases. Šādu atlasi sauc par secīgu atlasi bez atkārtošanās, un tās rezultāts ir izvietojums bez elementu atkārtošanās ar .

Numurs dažādos veidos, ko var izmantot, lai veiktu secīgu atlasi, neatgriežot elementus no kopējās sējuma kopas, ir vienāds ar:

3. piemērs

Dienas grafiks sastāv no 5 dažādas nodarbības. Nosakiet plānošanas opciju skaitu, izvēloties no 11 disciplīnām.

Risinājums

Katra grafika opcija ir 5 disciplīnu komplekts no 11, kas atšķiras no citām opcijām gan pēc sastāva, gan secības. Tāpēc:

Pārkārtojumi ir sakārtotas kolekcijas, kas viena no otras atšķiras tikai ar savu elementu secību. Visu elementu kopas permutāciju skaits ir vienāds ar

4. piemērs

Cik daudzos veidos pie viena galda var sēdēt 4 cilvēki?

Risinājums

Katra sēdvietu iespēja atšķiras tikai dalībnieku secībā, tas ir, tā ir 4 elementu permutācija:

Izvietojumi ar atkārtojumiem, kad atlasītais elements tiek atgriezts populācijā pirms nākamā atlases. Šo atlasi sauc par secīgu atlasi ar atdevi, un tās rezultātu sauc par izvietojumu ar elementu atkārtojumiem, izmantojot .

Kopējais dažādu veidu skaits, kā var veikt atlasi, lai atgrieztu elementus no apjoma kopas, ir vienāds ar

5. piemērs

Lifts apstājas 7 stāvos. Cik dažādos veidos šajos stāvos var izkāpt 6 pasažieri lifta kabīnē?

Risinājums

Katra no metodēm pasažieru sadalīšanai pa stāviem ir 6 pasažieru kombinācija 7 stāvos, kas atšķiras no citām kombinācijām gan pēc sastāva, gan pēc to secības. Tā kā vienā stāvā var izkāpt viens vai vairāki pasažieri, tie paši pasažieri var atkārtoties. Tāpēc šādu kombināciju skaits ir vienāds ar izvietojumu skaitu ar 7 elementu atkārtojumiem no 6:

Kombinācijas

Kombinācijas no n elementiem ar k sauc par nesakārtotām kolekcijām, kas atšķiras viena no otras ar vismaz vienu elementu.

Ļaujiet no kopējās populācijas ņemt vairākus elementus uzreiz (vai elementi tiek ņemti secīgi, bet netiek ņemta vērā to parādīšanās secība). Šādas vienlaicīgas nesakārtotas elementu atlases rezultātā no sējuma vispārējās populācijas tiek iegūtas kombinācijas, kuras tiek sauktas kombinācijas bez atkārtojumiem no elementiem .

Elementu kombināciju skaits ir vienāds ar:

6. piemērs

Kastītē ir 9 āboli. Cik daudzos veidos var atlasīt 3 ābolus no kastes?

Risinājums

Katra izvēle sastāv no 3 āboliem un atšķiras no citiem tikai ar sastāvu, tas ir, tās ir kombinācijas bez 9 elementu atkārtošanās:

Veidu skaits, kā izvēlēties 3 ābolus no 9:

Ļaujiet vienu pēc otra atlasīt elementus no sējuma vispārējās kopas, un katrs atlasītais elements tiek atgriezts vispārējā populācijā pirms nākamā atlases. Tas reģistrē, kuri elementi ir parādījušies un cik reizes, taču netiek ņemta vērā to parādīšanās secība. Iegūtos agregātus sauc kombinācijas ar atkārtojumiem no elementiem .

Kombināciju skaits ar elementu atkārtojumiem:

7. piemērs

Pasta nodaļa pārdod 3 veidu pastkartes. Cik dažādos veidos var iegādāties 6 pastkartes?

Šis ir uzdevums, lai atrastu kombināciju skaitu ar atkārtojumiem no 3 līdz 6:

Kopas sadalīšana grupās

Ļaujiet dažādu elementu kopu sadalīt šādās grupās, tad pirmajā grupā ietilpst elementi, otrajā - elementi, trešajā grupā - elementi un . Šo situāciju sauc par kopas sadalīšanu grupās.

Sadalījumu skaits grupās, kad elementi ietilpst pirmajā, elementi otrajā un elementi k-tā grupa- elementi, ir vienāds ar:

8. piemērs

16 cilvēku grupu nepieciešams sadalīt trīs apakšgrupās, no kurām pirmajā ir 5 cilvēki, otrajā - 7 cilvēki, trešajā - 4 cilvēki. Cik daudzos veidos to var izdarīt?

Kombinatorika ir matemātikas nozare, kas pēta jautājumus par to, cik dažādas kombinācijas, ievērojot noteiktus nosacījumus, var izveidot no dotajiem objektiem. Kombinatorikas pamati ir ļoti svarīgi nejaušu notikumu varbūtību novērtēšanai, jo Tieši tie ļauj mums aprēķināt fundamentāli iespējamo dažādu notikumu attīstības variantu skaitu.

Kombinatorikas pamatformula

Lai ir k elementu grupas, un i-tā grupa sastāv no n i elementiem. Atlasīsim vienu elementu no katras grupas. Tad kopējais skaits N veidus, kādos var izdarīt šādu izvēli, nosaka sakarība N=n 1 *n 2 *n 3 *...*n k .

1. piemērs. Izskaidrosim šo noteikumu ar vienkāršu piemēru. Pieņemsim, ka ir divas elementu grupas, un pirmā grupa sastāv no n 1 elementiem, bet otrā - no n 2 elementiem. Cik daudz dažādi pāri elementus var veidot no šīm divām grupām, lai pārī būtu viens elements no katras grupas? Pieņemsim, ka mēs paņēmām pirmo elementu no pirmās grupas un, to nemainot, izgājām cauri visiem iespējamajiem pāriem, mainot tikai elementus no otrās grupas. Šim elementam var būt n 2 šādi pāri. Tad mēs ņemam otro elementu no pirmās grupas un arī veidojam visus iespējamos pārus. Būs arī n 2 šādi pāri. Tā kā pirmajā grupā ir tikai n 1 elementi, kopējais iespējamo variantu skaits būs n 1 * n 2 .

2. piemērs. Cik trīsciparu pāra skaitļus var izveidot no cipariem 0, 1, 2, 3, 4, 5, 6, ja ciparus var atkārtot?
Risinājums: n 1 =6 (jo kā pirmo ciparu varat ņemt jebkuru skaitli no 1, 2, 3, 4, 5, 6), n 2 =7 (jo kā otro ciparu varat ņemt jebkuru skaitli no 0, 1, 2 , 3, 4, 5, 6), n 3 =4 (jo jebkuru skaitli no 0, 2, 4, 6 var uzskatīt par trešo ciparu).
Tātad, N = n 1 * n 2 * n 3 = 6 * 7 * 4 = 168.

Gadījumā, ja visas grupas sastāv no tas pats numurs elementi, t.i. n 1 =n 2 =...n k =n varam pieņemt, ka katra atlase tiek veikta no vienas un tās pašas grupas, un elements pēc atlases tiek atgriezts grupā. Tad visu atlases metožu skaits ir n k . Šo atlases metodi kombinatorikā sauc paraugi ar atgriešanu.

3. piemērs. Cik četrciparu skaitļus var izveidot no cipariem 1, 5, 6, 7, 8?
Risinājums. Katram četrciparu skaitļa ciparam ir piecas iespējas, kas nozīmē N=5*5*5*5=5 4 =625.

Apsveriet kopu, kas sastāv no n elementiem. Kombinatorikā šo kopu sauc vispārējā populācija.

n elementu izvietojumu skaits ar m

1. definīcija. Nakšņošana no plkst n elementi m kombinatorikā jebkura pasūtīts komplekts no m dažādi elementi, kas atlasīti no iedzīvotājiem n elementi.

4. piemērs. Trīs elementu (1, 2, 3) dažādi izkārtojumi pa diviem būs kopas (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) , 2). Izvietojumi var atšķirties viens no otra gan elementos, gan to secībā.

Izvietojumu skaitu kombinatorikā apzīmē ar A n m un aprēķina pēc formulas:

komentēt: n!=1*2*3*...*n (lasi: “en faktoriāls”), turklāt tiek pieņemts, ka 0!=1.

5. piemērs. Cik ir divciparu skaitļu, kuros desmitciparu un vienību cipars ir atšķirīgi un nepāra?
Risinājums: jo Ja ir pieci nepāra cipari, proti, 1, 3, 5, 7, 9, tad šis uzdevums ir atlasīt un novietot divus no pieciem dažādiem cipariem divās dažādās pozīcijās, t.i. norādītie skaitļi būs:

Definīcija 2. Kombinācija no n elementi m kombinatorikā jebkura nepasūtīts komplekts no m dažādi elementi, kas atlasīti no iedzīvotājiem n elementi.

6. piemērs. Komplektam (1, 2, 3) kombinācijas ir (1, 2), (1, 3), (2, 3).

n elementu kombināciju skaits, katra m

Kombināciju skaitu apzīmē ar C n m un aprēķina pēc formulas:

7. piemērs. Cik daudzos veidos lasītājs var izvēlēties divas grāmatas no sešām pieejamajām?

Risinājums: Metožu skaits ir vienāds ar sešu divu grāmatu kombināciju skaitu, t.i. vienāds:

n elementu permutācijas

Definīcija 3. Permutācija no n elementus sauc par jebkuriem pasūtīts komplektsšie elementi.

7.a piemērs. Visas iespējamās kopas, kas sastāv no trim elementiem (1, 2, 3), permutācijas ir: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2).

Dažādu n elementu permutāciju skaitu apzīmē ar P n un aprēķina pēc formulas P n =n!.

8. piemērs. Cik dažādos veidos plauktā vienā rindā var izkārtot septiņas dažādu autoru grāmatas?

Risinājums:šī problēma ir par permutāciju skaitu septiņi dažādas grāmatas. Ir P 7 =7!=1*2*3*4*5*6*7=5040 veidi, kā sakārtot grāmatas.

Diskusija. Mēs redzam, ka iespējamo kombināciju skaitu var aprēķināt pēc dažādiem noteikumiem (permutācijas, kombinācijas, izvietojumi) un rezultāts būs atšķirīgs, jo Aprēķinu princips un pašas formulas atšķiras. Uzmanīgi apskatot definīcijas, jūs ievērosiet, ka rezultāts ir atkarīgs no vairākiem faktoriem vienlaikus.

Pirmkārt, no cik elementiem mēs varam apvienot to kopas (cik lielas populācija elementi).

Otrkārt, rezultāts ir atkarīgs no mums nepieciešamo elementu kopu lieluma.

Visbeidzot, ir svarīgi zināt, vai elementu secība komplektā mums ir nozīmīga. Paskaidrosim pēdējo faktoru, izmantojot šādu piemēru.

9. piemērs. Ieslēgts vecāku sapulce Klāt 20 cilvēki. Cik dažādu variantu ir vecāku komitejas sastāvam, ja tajā jāiekļauj 5 cilvēki?
Risinājums:Šajā piemērā mūs neinteresē vārdu secība komitejas sarakstā. Ja rezultātā izrādās, ka tajā ietilpst vieni un tie paši cilvēki, tad mums šī ir viena un tā pati iespēja. Tāpēc skaitļa aprēķināšanai varam izmantot formulu kombinācijas no 20 elementiem pa 5 katrā.

Lietas būs savādākas, ja katrs komitejas loceklis sākotnēji būs atbildīgs par noteiktu darba jomu. Tad ar to pašu komisijas saraksta sastāvu tajā, iespējams, ir 5! iespējas permutācijasšī lieta. Dažādu (gan sastāva, gan atbildības jomas) iespēju skaitu šajā gadījumā nosaka skaits izvietojumus no 20 elementiem pa 5 katrā.

Pašpārbaudes uzdevumi
1. Cik trīsciparu pāra skaitļus var izveidot no cipariem 0, 1, 2, 3, 4, 5, 6, ja ciparus var atkārtot?

2. Cik ir piecciparu skaitļu, kas tiek lasīti vienādi no kreisās uz labo un no labās uz kreiso?

3. Klasē ir desmit priekšmeti un piecas mācību stundas dienā. Cik daudzos veidos var izveidot vienas dienas grafiku?

4. Cik daudzos veidos var atlasīt 4 delegātus konferencei, ja grupā ir 20 cilvēki?

5. Cik daudzos veidos var ievietot astoņus dažādus burtus astoņās dažādās aploksnēs, ja katrā aploksnē ir ievietots tikai viens burts?

6. Komisijā, kurā ir divi matemātiķi un seši ekonomisti, jābūt trīs matemātiķiem un desmit ekonomistiem. Cik daudzos veidos to var izdarīt?

Abstrakts par tēmu:

Aizpildījis 10. klases skolnieks “B”

vidusskola №53

Gluhovs Mihails Aleksandrovičs

Naberežnije Čelnijs

2002. gads
Saturs

No kombinatorikas vēstures_______________________________________________________	3
Summas noteikums_________________________________________________________________	4
	-
Produkta noteikums__________________________________________________	4
Uzdevumu piemēri_________________________________________________________________	-
Krustošas kopas_______________________________________________________	5
Uzdevumu piemēri_________________________________________________________________	-
Eilera apļi__________________________________________________________________	-
Izvietojumi bez atkārtošanās__________________________________________________	6
Uzdevumu piemēri_________________________________________________________________	-
Permutācijas bez atkārtojumiem_______________________________________________________	7
Uzdevumu piemēri_________________________________________________________________	-
Kombinācijas bez atkārtojumiem__________________________________________________	8
Uzdevumu piemēri_________________________________________________________________	-
Izvietojumi un kombinācijas bez atkārtošanās______________________________	9
Uzdevumu piemēri_________________________________________________________________	-
Permutācijas ar atkārtojumiem_______________________________________________________	9
Uzdevumu piemēri_________________________________________________________________	-
Uzdevumi priekš neatkarīgs lēmums ________________________________	10
Bibliogrāfija________________________________________	11

No kombinatorikas vēstures

Kombinatorikas piedāvājumi dažādi veidi savienojumi, kurus var veidot no ierobežotas kopas elementiem. Daži kombinatorikas elementi Indijā bija zināmi jau 2. gadsimtā. BC e. Nīdieši prata aprēķināt skaitļus, kurus tagad sauc par “kombinācijām”. 12. gadsimtā Bhaskara aprēķināja dažu veidu kombinācijas un permutācijas. Tiek uzskatīts, ka Indijas zinātnieki pētīja savienojumus saistībā ar to izmantošanu poētikā, dzejas struktūras zinātnē un poētiskie darbi. Piemēram, saistībā ar iespējamo n zilbju pēdas uzsvērto (garo) un neuzsvērto (īso) zilbju kombināciju aprēķināšanu. Kā zinātniska disciplīna kombinatorika veidojās 17. gadsimtā. Grāmatā “Aritmētikas teorija un prakse” (1656) franču autors A. arī velta veselu nodaļu kombinācijām un permutācijām.
B. Paskāls savā “Traktātā par aritmētisko trīsstūri” un “Traktātā par skaitļu secībām” (1665) izklāstīja binomiālo koeficientu doktrīnu. P. Fermā zināja par sakarībām starp matemātisko kvadrātu un cirtaini skaitļi ar savienojuma teoriju. Terminu “kombinatorika” sāka lietot pēc tam, kad Leibnics 1665. gadā publicēja savu darbu “Diskurss par kombinēšanas mākslu”, kurā tas pirmo reizi tika dots. zinātniskais pamatojums kombināciju un permutāciju teorijas. J. Bernulli pirmo reizi pētīja izvietojumus savas grāmatas “Ars conjectandi” (prognozēšanas māksla) otrajā daļā 1713. gadā. Mūsdienu kombināciju simboliku dažādi izglītības rokasgrāmatu autori ierosināja tikai 19. gadsimtā.

Visu kombinatorisko formulu daudzveidību var secināt no diviem galvenajiem apgalvojumiem par ierobežotas kopas– summas noteikums un produkta noteikums.

Summas noteikums

Ja galīgās kopas nekrustojas, tad X U Y (vai) elementu skaits ir vienāds ar kopas X elementu skaita un kopas Y elementu skaita summu.

Tas ir, ja pirmajā plauktā ir X grāmatas, bet otrajā – Y grāmatas, varat atlasīt grāmatu no pirmā vai otrā plaukta X+Y veidā.

Problēmu paraugi

Studentam jāveic praktiskie darbi matemātikā. Viņam tika piedāvāts izvēlēties 17 tēmas algebrā un 13 tēmas ģeometrijā. Cik daudzos veidos viņš var izvēlēties vienu tēmu praktiskais darbs?

Risinājums: X=17, Y=13

Pēc summas noteikuma X U Y=17+13=30 tēmas.

Ir 5 biļetes uz naudas loteriju, 6 biļetes uz sporta loteriju un 10 biļetes uz auto loteriju. Cik daudzos veidos jūs varat izvēlēties vienu biļeti no sporta loterijas vai auto loterijas?

Risinājums: tā kā skaidras naudas un apģērbu izloze nav saistīta ar izvēli, ir tikai 6 + 10 = 16 iespējas.

Produkta noteikums

Ja elementu X var atlasīt k veidos, un elements Y-m veidi tad pāri (X,Y) var izvēlēties k*m veidos.

Tas ir, ja pirmajā plauktā ir 5 grāmatas un otrajā - 10, tad jūs varat izvēlēties vienu grāmatu no pirmā plaukta un vienu no otrā plaukta 5 * 10 = 50 veidos.

Problēmu paraugi

Grāmatsējējam jāiesē 12 dažādas grāmatas sarkanos, zaļos un brūnos iesējumos. Cik daudzos veidos viņš to var izdarīt?

Risinājums: Ir 12 grāmatas un 3 krāsas, kas nozīmē, ka saskaņā ar izstrādājuma noteikumu ir iespējami 12 * 3 = 36 iesiešanas varianti.

Cik piecciparu skaitļu ir vienādi nolasāmi no kreisās puses uz labo un no labās uz kreiso?

Risinājums: šādos skaitļos pēdējais cipars būs tāds pats kā pirmais, un priekšpēdējais cipars būs tāds pats kā otrais. Trešais cipars būs jebkas. To var attēlot formā XYZYX, kur Y un Z ir jebkuri skaitļi, un X nav nulle. Tas nozīmē, ka saskaņā ar produkta noteikumu ciparu skaits, ko var vienādi nolasīt gan no kreisās puses uz labo, gan no labās puses uz kreiso, ir 9*10*10=900 opcijas.

Krustošas kopas

Bet gadās, ka kopas X un Y krustojas, tad tās izmanto formulu

, kur X un Y ir kopas un ir krustošanās laukums. Problēmu paraugi

20 cilvēki zina angļu valodu un 10 zina vācu valodu, no kuriem 5 zina gan angļu, gan vācu valodu. Cik cilvēku ir kopā?

Atbilde: 10+20-5=25 cilvēki.

Arī bieži par dzidrs šķīdums problēmas, izmantojot Eilera apļus. Piemēram:

No 100 tūristiem, kas ceļo uz ārzemēm, vācu valoda 30 cilvēki runā angliski, 28 runā franču valodā, 8 cilvēki runā angliski un franču valodā, 5 runā vāciski un franciski, 3 runā visās trīs valodās ?

Risinājums: Izteiksim šīs problēmas stāvokli grafiski. Apzīmēsim ar apli tos, kas zina angļu valodu, otru apli ar tiem, kas zina franču valodu, un ar trešo apli tos, kas zina vācu valodu.

Trīs tūristi runā visās trīs valodās, kas nozīmē, ka kopējā apļu daļā ievadām skaitli 3. Angļu un franču valoda To runā 10 cilvēki, un 3 no viņiem runā arī vācu valodā. Līdz ar to 10-3=7 cilvēki runā tikai angļu un franču valodā.

Tāpat mēs atklājam, ka 8-3 = 5 cilvēki runā tikai angļu un vācu valodā, un 5-3 = 2 tūristi runā vācu un franču valodā. Mēs ievadām šos datus attiecīgajās daļās.

Tagad noteiksim, cik cilvēku runā tikai vienā no uzskaitītajām valodām. Vācu valodu zina 30 cilvēki, bet 5+3+2=10 no tiem runā citās valodās, tāpēc vācu valodu zina tikai 20 cilvēki. Tāpat mēs atklājam, ka 13 cilvēki runā tikai angliski un 30 cilvēki runā tikai franču valodā.

Atbilstoši problēmai ir tikai 100 tūristu. 20+13+30+5+7+2+3=80 tūristi zina vismaz vienu valodu, līdz ar to 20 cilvēki nerunā nevienā no šīm valodām.

Izvietojumi bez atkārtošanās.

Cik tālruņa numurus var izveidot no 6 cipariem, lai visi cipari būtu atšķirīgi?

Šis ir izvietošanas problēmas piemērs bez atkārtošanās. Šeit ir ievietoti 10 skaitļi no 6, un opcijas, kurās vieni un tie paši skaitļi ir dažādās secībās, tiek uzskatīti par atšķirīgiem.

Ja X kopa, kas sastāv no n elementiem, m≤n, tad kopas X n elementu izvietojumu m sauc par sakārtotu kopu X, kas satur m elementus.

Visu n elementu izkārtojumu skaits ar m tiek apzīmēts ar

n! - n-faktoriāls (faktoriāls) ir skaitļu reizinājums naturālajā rindā no 1 līdz jebkuram skaitlim n Uzdevums

Cik daudzos veidos 4 zēni var uzaicināt četras no sešām meitenēm dejot?

Risinājums: divi zēni nevar uzaicināt vienu un to pašu meiteni vienlaikus. Un iespējas, kurās vienas un tās pašas meitenes dejo ar dažādiem zēniem, tiek uzskatītas par atšķirīgām, tāpēc:

Iespējami 360 varianti.

Permutācijas bez atkārtošanās

Gadījumā, ja n=m (sk. izvietojumus bez atkārtošanās) n elementu m sauc par kopas x permutāciju.

Visu n elementu permutāciju skaitu apzīmē ar P n.

Derīgs n=m:

Problēmu paraugi

Cik dažādus sešciparu skaitļus var izveidot no cipariem 0, 1, 2, 3, 4,5, ja cipari skaitļā neatkārtojas?

1) No šiem skaitļiem atrodiet visu permutāciju skaitu: P 6 =6!=720

2) 0 nevar būt skaitļa priekšā, tāpēc no šī skaitļa jāatņem to permutāciju skaits, kurās 0 atrodas priekšā. Un tas ir P 5 = 5! = 120.

P 6 -P 5 = 720-120 = 600

Nerātnais mērkaķis

Jā, greizkājainā Miška

Sākām spēlēt kvartetu

Beidz, brāļi, apstājies! –

Pērtiķis kliedz, - pagaidi!

Kā mūzikai vajadzētu iet?

Galu galā tu tā nesēdi...

Un šitā un tā viņi mainīja sēdvietas - atkal mūzika neiet.

Daudzās kombinatoriskajās problēmās tieši atrast mūs interesējošo iespēju skaitu izrādās grūti. Tomēr, nedaudz mainot problēmas apstākļus, varat atrast vairākas iespējas, kas zināmas reizes pārsniedz oriģinālo. Šo tehniku sauc daudzkārtēja skaitīšanas metode.

1. Cik anagrammu ir vārdam KLASE?

Grūtības ir tādas, ka šajā vārdā ir divi identiski burti C. Mēs īslaicīgi tos uzskatīsim par atšķirīgiem un apzīmēsim C 1 un C 2. Tad anagrammu skaits būs vienāds ar 5! = 120. Bet tie vārdi, kas atšķiras viens no otra tikai ar burtu C 1 un C 2 pārkārtošanu, patiesībā ir viena un tā pati anagramma! Tāpēc 120 anagrammas tiek sadalītas identisku pāros, t.i. nepieciešamais anagrammu skaits ir 120/2 = 60.

2. Cik anagrammu ir vārdam CHARADA?

Saskaitot trīs burtus A kā dažādus burtus A 1, A 2, A 3, mēs iegūstam 6! anagrammas Bet vārdi, kas veidoti viens no otra, tikai pārkārtojot burtus A 1, A 2, A 3, patiesībā ir viena un tā pati anagramma. Jo ir 3! burtu A 1, A 2, A 3 permutācijas, sākotnēji iegūtas 6! Anagrammas ir sadalītas grupās pa 3! identiski, un dažādu anagrammu skaits izrādās 6!/3! = 120.

3. Cik ir četru ciparu skaitļu, kas satur vismaz vienu pāra ciparu?

Atradīsim “nevajadzīgo” četrciparu skaitļu skaitu, kuru ierakstā ir tikai nepāra cipari. Tādu skaitļu ir 5 4 = 625 Bet kopā ir 9000 četrciparu skaitļu, tātad nepieciešamais “vajadzīgo” skaitļu skaits ir 9000 – 625 = 8375.

Atrodiet anagrammu skaitu vārdiem VERESK, BALAGAN, CITYMAN.
Atrodiet anagrammu skaitu vārdiem BAOBABS, BALLĀDE, GRIEŠANA, ANAGRAMMA, MATEMĀTIKA, KOMBINATORIKA, AIZSARDZĪBA.
Cik daudzos veidos jūs varat izmitināt 7 apmeklētājus trīs viesnīcas numuros: vienvietīgā, divvietīgā un četrvietīgā?
Ledusskapī ir divi āboli, trīs bumbieri un četri apelsīni. Katru dienu deviņas dienas pēc kārtas Petijai tiek dots viens auglis. Cik daudzos veidos to var izdarīt?
No septiņiem labākajiem skolas slēpotājiem jāizlasa komanda trīs cilvēku sastāvā dalībai pilsētas sacensībās. Cik daudzos veidos to var izdarīt?
Pirms eksāmena profesors pusei eksaminējamo solīja likt sliktu atzīmi. Uz eksāmenu ieradās 20 skolēni. Cik daudzos veidos viņš var izpildīt savu solījumu?
Cik vārdu var izveidot no pieciem burtiem A un ne vairāk kā trīs burtiem B?
Ir pieejams šokolādes, zemeņu un piena saldējums. Cik veidos var nopirkt trīs saldējumus?
Gatavojot picu, sieram tiek pievienoti dažādi komponenti, lai nodrošinātu īpašu garšu. Bila rīcībā ir sīpoli, sēnes, tomāti, paprika un anšovi, ko visu, viņaprāt, var pievienot sieram. Cik picu veidu Bils var pagatavot?
Noziedzīgās izrēķināšanās aculiecinieks atcerējās, ka noziedznieki aizbēga ar mersedesu, kura numura zīmē bija burti T, Z, U un cipari 3 un 7 (cipars ir rinda, kurā vispirms ir trīs burti un pēc tam trīs cipari) . Cik ir šādu skaitļu?
Cik diagonāļu ir izliektā n-kvadrāts?
Cik daudz lietu tur ir? n- ciparu numuri?
Cik ir desmit ciparu skaitļu, kuriem ir vismaz divi vienādi cipari?
Kauliņš tiek izmests trīs reizes. Starp visām iespējamām rezultātu secībām ir tādas, kurās sešinieks tiek izmests vismaz vienu reizi. Cik tādu ir?
Cik piecciparu skaitļu apzīmējumā ir cipars 1?
Cik daudzos veidos var šaha galds baltie un melnie karaļi, lai viens otru nedauzītu?
Cik dalītāju ir skaitlim 10800?

Veltīts noteiktas, parasti galīgas kopas elementu atlases un sakārtošanas problēmu risināšanai saskaņā ar dotajiem noteikumiem. Piemēram, cik daudzos veidos var izvēlēties 6 kārtis no 36 kāršu klāja vai cik veidos var izveidot rindu, kas sastāv no 10 cilvēkiem utt. Katrs kombinatorikas noteikums nosaka veidu, kā izveidot noteiktu konstrukciju, kas sastāv no sākotnējās kopas elementiem un tiek izsaukta kombinācija. Kombinatorikas galvenais mērķis ir saskaitīt to kombināciju skaitu, kuras var izveidot no sākotnējās kopas elementiem saskaņā ar doto noteikumu. Vienkāršākie kombinatorisko konstrukciju piemēri ir permutācijas, izvietojumi un kombinācijas.

Kombinatorikas dzimšana kas saistīti ar darbu B. Paskāls un P. Fermā par azartspēlēm, lielu ieguldījumu sniedza Leibnics, Bernulli un Eilers. Šobrīd interese par kombinatoriku ir saistīta ar datoru attīstību. Kombinatorikā mūs interesēs iespēja definēt kvantitatīvi dažādas galīgo kopu apakškopas varbūtības aprēķināšanai klasiskā veidā.

Lai noteiktu kopas kardinalitāti, kas atbilst konkrētam notikumam, ir lietderīgi izprast divus kombinatorikas noteikumus: reizinājuma likumu un summas likumu (dažkārt tos sauc attiecīgi par reizināšanas un saskaitīšanas principiem).

Produkta noteikums:ļaut no kaut kādas ierobežotas kopas

Var izvēlēties 1. objektu k 1 veids,

2. objekts - k 2 veidi

n- objekts - k n veidus. (1.1)

Pēc tam patvaļīgs saraksts n var atlasīt objektus no šīs kopas k 1 ,k 2 , …, k n veidus.

1. piemērs. Cik trīsciparu skaitļu ir ar dažādiem cipariem?

Risinājums. Decimālajā sistēmā ir desmit cipari: 0,1,2,3,4,5,6,7,8,9. Pirmajā vietā var būt jebkurš no deviņiem cipariem (izņemot nulli). Otrajā vietā ir jebkurš no atlikušajiem 9 cipariem, izņemot atlasīto. Ieslēgts pēdējā vieta kāds no atlikušajiem 8 cipariem.

Saskaņā ar produkta noteikumu 9·9·8 = 648 trīsciparu skaitļiem ir dažādi cipari.

2. piemērs. No punkta Ir 3 ceļi, kas ved uz punktu, un 4 ceļi no punkta uz punktu. Cik daudzos veidos jūs varat ceļot no iekšā cauri?

Risinājums. Punktā ir 3 veidi, kā izvēlēties ceļu uz punktu, un punktā ir 4 veidi, kā nokļūt līdz punktam. Saskaņā ar reizināšanas principu ir 3x4 = 12 veidi, kā iegūt no punkta uz punktu .

Summas noteikums: ja ir izpildīti nosacījumi (1.1.), var izvēlēties jebkuru no objektiem k 1 +k 2 +…+k n veidus.

3. piemērs. Cik daudzos veidos var izvēlēties vienu zīmuli no kastes, kurā ir 5 sarkani, 7 zili, 3 zaļi zīmuļi?

Risinājums. Vienu zīmuli, pēc summas likuma, var izvēlēties 5+7+3 = 15 veidos.

4. piemērs. Izlaid viņu no pilsētas Pilsētā var nokļūt ar vienu gaisa maršrutu, diviem vilcienu maršrutiem un trīs autobusu maršrutiem. Cik daudzos veidos jūs varat nokļūt no pilsētas? pilsētā ?

Risinājums. Šeit ir izpildīti visi saskaitīšanas principa nosacījumi, tāpēc saskaņā ar šo principu mēs iegūstam 1+2+3 = 6 veidus.

Apskatīsim piemēru, kas ilustrē atšķirību starp reizināšanas un saskaitīšanas principiem.

5. piemērs. Elektronikas veikalā tiek pārdoti trīs zīmolu televizori un divu veidu videomagnetofoni. Pircējam ir iespēja iegādāties televizoru vai videomagnetofonu. Cik dažādos veidos viņš var veikt vienu pirkumu? Cik dažādus komplektus ar televizoru un magnetofonu var iegādāties šajā veikalā, ja pircējs gatavojas pirkt gan televizoru, gan videomagnetofonu pa pāriem?

Risinājums. Vienu televizoru var izvēlēties trīs veidos, bet magnetofonu – divos pārējos veidos. Tad televizoru vai magnetofonu var nopirkt 3+2=5 veidos.

Otrajā gadījumā vienu televizoru var izvēlēties trīs veidos, pēc tam videomagnetofonu var izvēlēties divos veidos. Tāpēc reizināšanas principa dēļ televizoru un videomagnetofonu var iegādāties 3 × 2 = 6 veidos.

Tagad apskatīsim piemērus, kuros tiek piemēroti abi kombinatorikas noteikumi: gan reizināšanas, gan saskaitīšanas princips.

6. piemērs. Grozā ir 12 āboli un 10 apelsīni. Vaņa izvēlas vai nu ābolu, vai apelsīnu. Pēc tam Nadja no atlikušajiem augļiem izvēlas gan ābolu, gan apelsīnu. Cik šādas izvēles ir iespējamas?

Risinājums. Vaņa var izvēlēties ābolu 12 veidos, apelsīnu 10 veidos. Ja Vaņa izvēlas ābolu, tad Nadja var izvēlēties ābolu 11 veidos, bet apelsīnu 10 veidos. Ja Vaņa izvēlas apelsīnu, tad Nadja var izvēlēties ābolu 12 veidos, bet apelsīnu 9 veidos. Tādējādi Vaņa un Nadja var izdarīt savu izvēli dažādos veidos.

7. piemērs. Ir 3 vēstules, no kurām katru var nosūtīt uz 6 adresēm. Cik daudzos veidos to var izdarīt?

Risinājums. Šajā problēmā mums jāapsver trīs gadījumi:

a) visas vēstules tiek nosūtītas uz dažādām adresēm;

b) visas vēstules tiek nosūtītas uz vienu adresi;

c) uz vienu adresi tiek nosūtītas tikai divas vēstules.

Ja visas vēstules tiek nosūtītas uz dažādām adresēm, tad šādu metožu skaits ir viegli atrodams pēc reizināšanas principa: n 1 = 6 × 5 × 4 = 120 veidi. Ja visas vēstules sūta uz vienu adresi, tad tādas metodes būs n 2 = 6. Tātad atliek aplūkot tikai trešo gadījumu, kad uz vienu adresi tiek nosūtītas tikai 2 vēstules. Mēs varam atlasīt vēstuli 3 veidos, un mēs varam to nosūtīt uz jebkuru izvēlēto adresi 6 veidos. Atlikušās divas vēstules uz atlikušajām adresēm varam nosūtīt 5 veidos. Tāpēc uz vienu adresi varam nosūtīt tikai divas vēstules n 3 = 3 × 6 × 5 = 90 veidi. Tādējādi jūs varat nosūtīt 3 vēstules uz 6 adresēm saskaņā ar pievienošanas principu

veidus.

Parasti kombinatorika uzskata par idealizētu nejaušās atlases eksperimentu. k elementi no n. Šajā gadījumā elementi: a) netiek atgriezti atpakaļ (atlases shēma bez atgriešanas); b) atgriezties atpakaļ (atlases shēma ar atgriešanu).

1. Atlases shēma bez atgriešanas

Izmitināšana no n elementi k ir jebkurš pasūtīts komplekts k piederošie elementi n- elementu komplekts. Dažādi izkārtojumi atšķiras viens no otra vai nu elementu secībā, vai pēc sastāva.

Izvietojumu skaits no n elementi k apzīmē un aprēķina pēc formulas

(1.2)

Kur n! = 1×2×3×…× n, 1! = 1, 0! = 1.

8. piemērs. Konkursā piedalās 10 cilvēki, no kuriem trīs iegūs 1., 2., 3. vietu. Cik daudz dažādu iespēju ir?

Risinājums. Šajā gadījumā svarīga ir vietu sadales secība. Dažādu iespēju skaits ir vienāds

Pārkārtošanās no n elementus sauc par izvietojumu n elementi n. Permutāciju skaits no n elementi pārstāv Pn un aprēķināts, izmantojot formulu

(1.3)

9. piemērs. Cik daudzos veidos ir iespējams sakārtot 10 grāmatas plauktā?

Risinājums. Kopējais izkārtojuma metožu skaits tiek definēts kā 10 elementu permutāciju skaits (1.3) un ir vienāds ar R 10 = 10! = 3628 800.

2. Atlases shēma ar atgriešanu

Ja izvēloties k elementi no n, elementi tiek atgriezti atpakaļ un pasūtīti, tad viņi saka, ka šis izvietojumi ar atkārtojumiem .

Izvietojumu skaits ar atkārtojumiem:

11. piemērs. Viesnīcā ir 10 numuri, no kuriem katrā var izmitināt četrus cilvēkus. Cik izmitināšanas iespēju ir četriem viesiem, kas ierodas?

Risinājums. Katrs nākamais viesis no 4 var tikt ievietots jebkurā no 10 istabām, jo tiek apsvērta idealizēta pieredze, tāpēc kopējais izvietojumu skaits saskaņā ar izvietojuma formulu ar atkārtojumiem (1,5) ir vienāds ar

Ja izvēloties k elementi no n elementi tiek atgriezti atpakaļ bez turpmākas pasūtīšanas, tad tiek uzskatīts, ka tas tā ir kombinācijas ar atkārtojumiem. Kombināciju skaits ar atkārtojumiem no n elementi k definēts:

12. piemērs. Veikals pārdod 10 veidu kūkas. Cits pircējs izsita čeku par trim kūkām. Pieņemot, ka jebkura preču kopa ir vienlīdz iespējama, nosakiet iespējamo pasūtījumu skaitu.

Risinājums. Vienlīdz iespējamo pasūtījumu skaits pēc formulas (1.6) ir vienāds ar