Kombinatorikas elementi. Kombinatorika - pamatjēdzieni un formulas. Permutācijas, izvietojumi, kombinācijas Kombinatorikas piemēri

Kombinatorika ir matemātikas nozare. Kombinatorikas kā zinātnes pamatjēdzieni un formulas tiek pielietotas visās dzīves jomās.

Nav pārsteidzoši, ka tas ir iekļauts 11. klases programmā, kā arī iestājpārbaudījumos daudzās Krievijas Federācijas augstskolās. Tās pamati ir daudzu cilvēka darbības sfēru lietišķajā mākslā.

Tās vēsture sniedzas vairāk nekā 6 gadsimtus senā pagātnē. Pirmās kombinatoriskās problēmas parādījās viduslaiku filozofu un matemātiķu darbos.

Šīs zinātniskās pasaules pārstāvji mēģināja atrast metodes šādu problēmu risināšanai, to pamatnoteikumus un jēdzienus, kā arī izveidot unikālas formulas un vienādojumus tiem, kas ar tiem vēl nebija saskārušies. Šādu informāciju mūsdienās sauc par informāciju “manekeniem”.

Mēģināsim izprast šīs zinātnes jomas aspektus: kādi ir elementi, īpašības, noteikumi, metodes un to galvenais pielietojums mūsu dzīvē? Protams, nav iespējams aptvert visu apgabalu vienā rakstā. Tāpēc visas visvienkāršākās lietas tiks parādītas zemāk.

Kas ir kombinatorika matemātikā

Šī termina būtību piešķir pagājušo gadu grāmatas: šis matemātikas nozare, kas nodarbojas ar operācijām ar daudziem elementiem.

Internetā ir pieejamas datorzinātņu un matemātikas mācību grāmatas bērniem un skolēniem, materiālu un uzdevumu krājumi iesācējiem, kur pieejamā veidā izskaidrota “izklaidējošā” kombinatorika. Mums ir stingri jāizdomā, kā šādas problēmas atrisināt.

Pamatklasēs problēmas par šo tēmu tiek risinātas papildu pulciņos, bet skolās ar padziļinātu matemātikas apguvi - pamatstundās. Turklāt kombinatorikas uzdevumi ir iekļauti visu līmeņu olimpiādēs.

Pamatjēdzieni

Ir vairāki no tiem:

1. Elements– jebkurš objekts vai parādība, kas iekļauta vēlamajā komplektā.
2. Kombinācija– apakškopas, kas oriģinālajā kopā atrodas patvaļīgā secībā.
3. Pārkārtošanās– elementi komplektā ir stingri noteiktā secībā.
4. Izmitināšana– pasūtītās apakškopas oriģinālajā komplektā.

Produkta noteikums

Tas ir viens no pamatnoteikumiem šādu problēmu risināšanā un izklausās šādi:

Izvēloties elementu A nonmetodes un elementa B izvēle nomDažos veidos ir taisnība, ka ir iespējams izvēlēties pāri A un B vienlaikusn* mveidus.

Apskatīsim konkrētus piemērus.

Uzdevums Nr.1.

Kastītē ir 2 bumbiņas un 6 lecamauklas. Cik daudzos veidos var iegūt 1 bumbiņu un 1 lecamauklu?

Atbilde ir vienkārša: 2 * 6 = 12.

Uzdevums Nr.2.

Ir 1 kubs, 2 bumbiņas, 3 ziedi un 4 konfektes. Cik daudzos veidos var uzzīmēt kubu, bumbiņu, ziedu un konfekti?

Risinājums ir līdzīgs: 1 * 2 * 3 * 4 = 24.

Turklāt kreiso pusi var uzrakstīt daudz vienkāršāk: 4!

! šajā gadījumā tā nav pieturzīme, bet faktoriāls. Izmantojot to, jūs varat aprēķināt sarežģītākas iespējas un atrisināt sarežģītas problēmas (ir dažādas formulas, bet par to vēlāk).

Uzdevums Nr.3.

Cik divciparu skaitļus var izveidot no 2 cipariem?

Atbilde: 2! = 2.

Uzdevums Nr.4.

Cik desmit ciparu skaitļus var izveidot no 10 cipariem?

Summas noteikums

Tas ir arī kombinatorikas pamatnoteikums.

Ja var izvēlēties Anreizes, un B -mreizes, tad var izvēlēties A vai B (n+ m) vienreiz.

Uzdevums Nr.5.

Kastītē ir 5 sarkani, 3 dzelteni, 7 zaļi, 9 melni zīmuļi. Cik daudzos veidos var izvilkt 1 zīmuli?

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

Kombinācijas ar un bez atkārtojumiem

Šis termins attiecas uz kombinācijām jebkurā secībā no n x m elementu kopas.

Kombināciju skaits ir vienāds ar šādu kombināciju skaitu.

Uzdevums Nr.6.

Kastītē ir 4 dažādi augļi. Cik daudzos veidos jūs varat iegūt 2 dažādus augļus vienlaikus?

Risinājums ir vienkāršs:

Kur ir 4! – 4 elementu kombinācija.

Ar atkārtojumiem nedaudz sarežģītāk, kombinācijas aprēķina, izmantojot šādu formulu:

Uzdevums Nr.7.

Ņemsim to pašu gadījumu, bet ar nosacījumu, ka kastē tiek atgriezts viens auglis.

Šajā gadījumā:

Izvietojumi ar un bez atkārtojumiem

Šī definīcija nozīmē m elementu kopu no n elementu kopas.

Uzdevums Nr.8.

No 3 cipariem ir jāizvēlas 2, lai iegūtu dažādus divciparu skaitļus. Cik daudz iespēju?

Atbilde ir vienkārša:

Bet par ko ar atkārtojumiem?Šeit katru elementu var novietot vairākas reizes! Šajā gadījumā vispārējā formula izskatīsies šādi:

Uzdevums Nr.9.

No 12 latīņu alfabēta burtiem un 10 dabiskās sērijas cipariem jums jāatrod visas iespējas, kā izveidot automašīnas reģiona kodu.

Permutācijas ar un bez atkārtojumiem

Šis termins attiecas uz visām iespējamām n elementu kopas kombinācijām.

10. uzdevums.

Cik iespējamos 5 ciparu skaitļus var izveidot no 5 cipariem? Kā ir ar sešiem cipariem no 6 cipariem? Septiņi cipari no 7 cipariem?

Risinājumi saskaņā ar iepriekš minēto formulu ir šādi:

Bet par ko ar atkārtojumiem? Ja šādā komplektā ir vienādas nozīmes elementi, tad permutāciju būs mazāk!

Uzdevums Nr.11.

Kastītē ir 3 identiski zīmuļi un viena pildspalva. Cik daudz permutāciju jūs varat veikt?

Atbilde ir vienkārša: 4! / (3! * 1!) = 4.

Kombinatoriskas problēmas ar risinājumiem

Iepriekš tika sniegti visu iespējamo problēmu veidu piemēri ar risinājumiem. Šeit mēs centīsimies tikt galā ar sarežģītākiem gadījumiem, kas sastopami mūsu dzīvē.

Uzdevumu veidi	Kas jums jāatrod	Risinājuma metodes
Maģiskais laukums	Skaitlis, kurā skaitļu summai rindās un kolonnās ir jābūt vienādai (tā šķirne ir latīņu kvadrāts).	Atkārtošanās attiecības. Līdzīga problēma tiek atrisināta, taču ar daudz mazāku elementu kopu saskaņā ar zināmiem noteikumiem un formulām.
Izvietojuma problēma	Standarta ražošanas uzdevums (piemēram, savārstījumu tehnoloģijā) ir atrast iespējamos veidus, kā produktu daudzumu sadalīt šūnās noteiktā secībā.	Iekļaušana un izslēgšana. Parasti to izmanto, pierādot dažādus izteicienus.
Problēmas ar tirgotājiem	Mērķis ir atrast visus iespējamos veidus, kā cilvēki nokļūt no punkta A uz punktu B.	Trajektorijas. Šāda veida problēmas raksturo iespējamo risinājumu ģeometriskā konstrukcija.

Secinājums

Ir vērts studēt šo zinātni, jo straujās tehnoloģiju modernizācijas laikmetā būs nepieciešami speciālisti, kas var sniegt dažādus risinājumus noteiktām praktiskām problēmām.

KOMBINATORIKA

Kombinatorika ir matemātikas nozare, kas pēta elementu atlases un sakārtošanas problēmas no noteiktas pamatkopas saskaņā ar dotajiem noteikumiem. Kombinatorikas formulas un principi tiek lietoti varbūtību teorijā, lai aprēķinātu nejaušu notikumu iespējamību un attiecīgi iegūtu gadījuma lielumu sadalījuma likumus. Tas savukārt ļauj pētīt masu nejaušo parādību modeļus, kas ir ļoti svarīgi, lai pareizi izprastu statistikas modeļus, kas izpaužas dabā un tehnoloģijā.

Saskaitīšanas un reizināšanas noteikumi kombinatorikā

Summas noteikums. Ja divas darbības A un B ir viena otru izslēdzošas un darbību A var veikt m veidos, bet B – n veidos, tad vienu no šīm darbībām (vai nu A, vai B) var veikt n + m veidos.

1. piemērs.

Klasē ir 16 zēni un 10 meitenes. Cik daudzos veidos jūs varat norīkot vienu dežurantu?

Risinājums

Pienākumos var norīkot vai nu zēnu vai meiteni, t.i. dežurants var būt jebkurš no 16 zēniem vai jebkura no 10 meitenēm.

Izmantojot summas likumu, konstatējam, ka vienu dežurantu var norīkot 16+10=26 veidos.

Produkta noteikums. Lai būtu k darbības, kas jāveic secīgi. Ja pirmo darbību var veikt n 1 veidos, otro darbību n 2 veidos, trešo n 3 veidos un tā tālāk līdz k-ajai darbībai, kuru var veikt n k veidos, tad visas k darbības kopā var veikt :

veidus.

2. piemērs.

Klasē ir 16 zēni un 10 meitenes. Cik daudzos veidos var iecelt divus dežurantus?

Risinājums

Par pirmo dežurantu var iecelt vai nu zēnu, vai meiteni. Jo Klasē ir 16 zēni un 10 meitenes, tad pirmo dežurantu var nozīmēt 16+10=26 veidos.

Pēc tam, kad esam izvēlējušies pirmo dežurantu, varam izvēlēties otro no atlikušajiem 25 cilvēkiem, t.i. 25 veidi.

Atbilstoši reizināšanas teorēmai divus pavadoņus var izvēlēties 26*25=650 veidos.

Kombinācijas bez atkārtošanās. Kombinācijas ar atkārtojumiem

Klasiska kombinatorikas problēma ir kombināciju skaita problēma bez atkārtojumiem, kuras saturu var izteikt ar jautājumu: cik daudz veidus Var izvēlēties m no n dažādas preces?

3. piemērs.

Dāvanā jāizvēlas 4 no 10 dažādām grāmatām. Cik daudzos veidos to var izdarīt?

Risinājums

Mums jāizvēlas 4 grāmatas no 10, un izvēles secībai nav nozīmes. Tādējādi jums jāatrod 10 elementu kombināciju skaits no 4:

.

Apsveriet kombināciju ar atkārtojumu skaitu problēmu: ir r identiski objekti katrā no n dažādajiem veidiem; cik daudz veidus Var izvēlēties m() no šie (n*r) preces?

.

4. piemērs.

Konditorejas veikalā tika pārdotas 4 veidu kūkas: Napoleonu, eklēru, smilšu kūkas un kārtainās mīklas. Cik dažādos veidos var iegādāties 7 kūkas?

Risinājums

Jo Starp 7 kūkām var būt viena veida kūkas, tad 7 kūku iegādes veidu skaitu nosaka kombināciju skaits ar atkārtojumiem no 7 līdz 4.

.

Izvietojumi bez atkārtošanās. Izvietojumi ar atkārtojumiem

Klasiska kombinatorikas problēma ir izvietojumu skaita problēma bez atkārtojumiem, kuras saturu var izteikt ar jautājumu: cik daudz veidus Var izvēlēties Un pastu Autors m atšķirīgs vietām m no n dažādi preces?

5. piemērs.

Dažam laikrakstam ir 12 lappuses. Uz šī laikraksta lappusēm nepieciešams ievietot četras fotogrāfijas. Cik daudzos veidos to var izdarīt, ja nevienā laikraksta lapā nedrīkst būt vairāk par vienu fotogrāfiju?

Risinājums.

Šajā uzdevumā mēs ne tikai atlasām fotogrāfijas, bet izvietojam tās noteiktās laikraksta lappusēs, un katrā laikraksta lappusē nedrīkst būt vairāk par vienu fotogrāfiju. Tādējādi problēma tiek samazināta līdz klasiskajai problēmai noteikt izvietojumu skaitu bez 12 elementu atkārtojumiem no 4 elementiem:

Tādējādi 4 fotogrāfijas uz 12 lapām var sakārtot 11 880 veidos.

Klasiska kombinatorikas problēma ir arī izvietojumu skaita problēma ar atkārtojumiem, kuras saturu var izteikt ar jautājumu: cik daudz veidus Var Tubarmija Un pastu Autors m atšķirīgs vietām m no n preces,Argatavs kuras Tur ir tas pats?

6. piemērs.

Zēnam joprojām bija zīmogi ar cipariem 1, 3 un 7 no viņa galda spēļu komplekta. Viņš nolēma izmantot šos zīmogus, lai uzliktu piecciparu skaitļus uz visām grāmatām, lai izveidotu katalogu. Cik dažādus piecciparu skaitļus var izveidot zēns?

Permutācijas bez atkārtošanās. Permutācijas ar atkārtojumiem

Klasiska kombinatorikas problēma ir permutāciju skaita problēma bez atkārtošanās, kuras saturu var izteikt ar jautājumu: cik daudz veidus Var pastu n dažādi preces ieslēgts n dažādi vietas?

7. piemērs.

Cik četru burtu “vārdus” jūs varat izveidot no vārda “laulība” burtiem?

Risinājums

Kopējā populācija ir vārda “laulība” 4 burti (b, p, a, k). “Vārdu” skaitu nosaka šo 4 burtu permutācijas, t.i.

Gadījumā, ja starp atlasītajiem n elementiem ir identiski (atlase ar atgriešanos), permutāciju ar atkārtojumu skaitu problēmu var izteikt ar jautājumu: Cik daudzos veidos var pārkārtot n objektus, kas atrodas n dažādās vietās, ja starp n objektiem ir k dažāda veida (k< n), т. е. есть одинаковые предметы.

8. piemērs.

Cik dažādas burtu kombinācijas var izveidot no vārda "Misisipi" burtiem?

Risinājums

Ir 1 burts "m", 4 burti "i", 3 burti "c" un 1 burts "p", kopā 9 burti. Tāpēc permutāciju skaits ar atkārtojumiem ir vienāds ar

PAMATA KOPSAVILKUMS SADAĻAI "KOMBINATORIKA"

Lai izveidotu atbilstošos kombinatorisko problēmu matemātiskos modeļus, mēs izmantosim kopu teorijas matemātiskais aparāts. Var gadīties, ka dotajā komplektā nav svarīga elementu secība, bet svarīga ir tikai kopas sastāvs. Bet ir problēmas, kurās elementu secība ir būtiska.

1. definīcija: Pasūtiet daudzās no elementi ir tā elementu numerācija ar naturāliem skaitļiem, t.i. iestatīt displeju
daudziem
.

2. definīcija: Tiek izsaukta kopa ar noteiktu secību pasūtīts komplekts.

Acīmredzot komplektu, kas satur vairāk nekā vienu elementu, var pasūtīt vairāk nekā vienā veidā.

Piemēram, no diviem burtiem Un Jūs varat izveidot pasūtītu komplektu divos dažādos veidos:

Un
.

Trīs burti ,Un var secēt sešos veidos:

,
,
,
,
,
.

Četriem burtiem, uzskaitot, mēs iegūstam 24 dažādas sakārtotas secības.

Noteiktas kopas elementu sakārtotas secības var uzskatīt par šo elementu sadalījumiem vai izkārtojumiem secībā.

3. definīcija: Dota galīga kopa
no elementi. Jebkurš komplekts tiks izsaukti dotās kopas elementi (un kopas elementi var atkārtoties). -kārtību .

Izmantojot izkārtojuma jēdzienu, tiek ieviestas kombinatorikas pamatdefinīcijas: kombinācijas, izvietojumi un permutācijas. Turklāt katru no šiem jēdzieniem var atkārtot vai neatkārtoties. Šajā sadaļā mēs aplūkosim kombinatoriskās formulas bez atkārtošanās.

Pārkārtojumi bez atkārtošanās.

4. definīcija: Ļaujiet
- ierobežots kopums elementi. Permutācijas no dažādi komplekta elementi
visas vietas tiek izsauktas elementi noteiktā secībā. Norāda: (no franču vārda permutācija- pārkārtošana).

Pasūtītie komplekti tiek uzskatīti par atšķirīgiem, ja tie atšķiras pēc elementiem vai secības.

5. definīcija: Tiek izsauktas dažādas sakārtotas kopas, kas atšķiras tikai ar savu elementu secību permutācijas no šī daudzuma.

Pēdējā definīcija ir formulēta no kopu teorijas pozīcijas.

6. definīcija: Darbs secīgie naturālie skaitļi matemātikā tiek apzīmēti ar un zvaniet faktoriāls .

Apzīmēšanas izvēle izsaukuma zīme var būt saistīta ar to, ka pat salīdzinoši mazām vērtībām numuru ļoti liels. Piemēram,
,
,
,
,
,, utt.

1. teorēma: Permutāciju skaits no dažādus elementus aprēķina pēc formulas:

Pierādījums. Apsveriet patvaļīgu kopu elementi. Veidosim no tiem visdažādākās vienošanās elementi. Sakārtojuma pirmajā vietā varat ievietot jebkuru no elementi ( pirmā elementa izvēles metodes). Kad pirmais elements ir atlasīts un neatkarīgi no tā, kā tas ir atlasīts, var atlasīt otro elementu
veidā. Atliek atlasīt trešo elementu
metode utt. Pēdējais elements ir attiecīgi atlasīts vienā veidā. Tad, pateicoties kombinatoriskajam reizināšanas principam, šādu izkārtojumu skaits būs vienāds ar:

Teorēma ir pierādīta.

1. piemērs: Cik daudzos veidos trīs draugi var ieņemt vietas ar numuru 1, 2 un 3 kinoteātrī?

Risinājums. Meklēto metožu skaits būs vienāds ar permutāciju skaitu bez trīs elementu atkārtojumiem:
veidus. Ja nepieciešams, šīs metodes var sakārtot.

Tiek sauktas vārda burtu permutācijas anagrammas . Anagrammas, ko 3. gadsimtā pirms mūsu ēras atklāja grieķu gramatiķis Likofrons, joprojām piesaista valodnieku, dzejnieku un literatūras cienītāju uzmanību. Vārdu spēļu meistari papildus erudīcijai un lielam vārdu krājumam zina daudzus ar kombinatoriskām prasmēm saistītus noslēpumus, no kuriem viens ir anagrammas. Bieži vien no visām permutācijām ir jāizvēlas tās, kurām ir noteikta īpašība. Piemēram, starp vārda anagrammām "kurmis", no kuriem ir tikai
, tikai viens, neskaitot pašu vārdu "kurmis", jēga krievu valodā – "tiesa".

Papildus lineārajām permutācijām var apsvērt apļveida (vai cikliskas) permutācijas. Šajā gadījumā permutācijas, kas rotācijas laikā pārvēršas viena par otru, tiek uzskatītas par vienādām un nav jāskaita.

2. teorēma: Apļveida permutāciju skaits no dažādi elementi ir vienādi

2. piemērs: Cik veidos 7 bērni var pievienoties apaļajai dejai?

Risinājums. 7 bērnu lineāro permutāciju skaits būs vienāds ar
. Ja apaļā deja jau ir izveidota, tad tai paredzētas 7 apļveida permutācijas, kas griežoties pārveidojas viena par otru. Šīs permutācijas nevajadzētu skaitīt, tāpēc būs 7 elementu apļveida permutācijas .

Izvietojumi bez atkārtošanās.

7. definīcija: Lai ir dažādi priekšmeti. Vienošanās no elementi no elementi (
) tiek saukti izvietojumi bez atkārtojumiem . Norādīt: . Šeit ir domāts, ka elementi aranžējumos neatkārtojas.

Šajā definīcijā būtiska ir šāda nostāja: abi pasākumi ir atšķirīgi, ja tie atšķiras vismaz vienā elementā vai elementu secībā.

Sniegsim citu izvietojumu definīciju, kas ir līdzvērtīga oriģinālajai un ir vieglāk saprotama.

8. definīcija: Tiek sauktas ierobežotas sakārtotas kopas izvietojumus.

3. teorēma: Visu izvietojumu skaits no elementi no elementi bez atkārtojumiem tiek aprēķināti pēc formulas:

Pierādījums. Lai ir patvaļīga kopa
, kas sastāv no elementi. Jums ir jāizvēlas no šīs šķirnes dažādi elementi. Turklāt izvēles secība ir svarīga.

Elementu atlase tiek veikta pakāpeniski. Var izvēlēties pirmo izkārtojuma elementu Dažādi ceļi. Pēc tam no atlikušajiem komplekta elementiem
tiek izvēlēts otrais sakārtojuma elements
veidā. Ir iespējams izvēlēties trešo elementu
metode utt. Pēc tam izvēlēties - th elements mums ir
veidā. Tāpēc saskaņā ar reizināšanas noteikumu šādu izkārtojumu skaits būs vienāds ar:

Pēc definīcijas šādi pasākumi ir izvietojumi. Q.E.D.

3. piemērs: Sapulcē 25 cilvēku sastāvā tiek izvēlēts prezidijs 3 cilvēku sastāvā: 1) priekšsēdētājs, 2) vietnieks, 3) sekretārs. Cik daudz iespēju ir izvēlēties prezidiju?

Risinājums. Izvēloties trīs cilvēkus no 25, mēs ņemam vērā, ka atlases secība ir svarīga, tāpēc prezidiju skaits būs vienāds ar:

komentēt: Izvietojumu skaitu bez atkārtojumiem var atrast arī, izmantojot formulu:

. (3)

Ja formulas (3) daļas saucējs
, tad tas ir vispārpieņemts
.

komentēt: Formula (3) ir kompakta, bet, risinot uzdevumus, ērtāk izmantot formulu (2). Daļskaitli formulas (3) labajā pusē var samazināt līdz veselam skaitlim. Šis skaitlis ir vienāds ar skaitli formulas (2) labajā pusē.

4. piemērs: Cik divu burtu vārdu (burti netiek atkārtoti) var izveidot no 33 krievu alfabēta burtiem?

Risinājums.Šajā gadījumā runa nav par vārdiem lingvistiskā nozīmē, bet gan ar patvaļīgas sastāva burtu kombinācijām.

Tad dažādu 2 burtu kombināciju skaits, kas izvēlēti no 33 alfabēta burtiem, būs vienāds ar:

.

Šajā gadījumā svarīga ir burtu secība. Ja vienā vārdā nomainīsiet 2 burtus, jūs saņemsiet jaunu vārdu.

komentēt: Permutācija bez atkārtojumiem ir īpašs izvietojumu gadījums bez atkārtojumiem, kad
. Mēs varam teikt, ka permutācija no elementu izvietojums elementi no elementi:

Dažās kombinatorikas uzdevumos objektu secībai noteiktā kopā nav nozīmes. Svarīgi ir tikai tas, kuri elementi to veido. Šādās situācijās mums ir darīšana kombinācijas.

Kombinācijas bez atkārtošanās.

9. definīcija: Kombinācijas nav atkārtojumu no kādas kopas elementi atbilstoši elementi (
) ir izkārtojumi, kas atšķiras viens no otra sastāvu, Bet nav kārtībā elementi. Norādīt: (no franču vārda kombinācija- kombinācija).

Šajā gadījumā vienošanās svarīgs ir sastāvs, nevis elementu secība apakškopā. Ja divi izkārtojumi atšķiras tikai elementu secībā, tad no kombināciju viedokļa tie nav atšķirami. Elementi šajos izkārtojumos neatkārtojas.

No kopu teorijas viedokļa kombināciju definīciju var formulēt dažādi.

10. definīcija: Tiek sauktas ierobežotas nesakārtotas kopas kombinācijas.

Tādējādi kombinācijas ir elementu atlase, kurā to secība ir pilnīgi nesvarīga.

Kombinācijas no elementi no elementiem ir jābūt mazāk nekā atbilstošo izvietojumu. Tas izriet no tā, ka nav nepieciešams skaitīt viena sastāva veidojumus.

4. teorēma: Kombināciju skaits tiek atrasts pēc šādas formulas:

. (4)

Pierādījums. Ja no patvaļīgas - atlasīta elementu kopa elementi, tad tos var numurēt
vairākos veidos, kas vienādi ar . Atlikušais
elementus var numurēt
,
, …,Kopā
veidus. Turklāt pati atlase elementi no elementus var īstenot veidus. Tātad mēs saņēmām
numerācijas iespējas visam komplektam elementi, kas ir tikai . Tāpēc mums ir
, no kurienes mēs iegūstam:

.

Teorēma ir pierādīta.

komentēt: Daļa (4) labajā pusē var tikt samazināta līdz veselam skaitlim.

No kombināciju skaita formulas izriet:

,
,
.

Formulu (4) var pārveidot šādā formā:
. Tas parāda, ka izvietojumu skaits V reizinot atbilstošo kombināciju skaitu . Citiem vārdiem sakot, saskaitīt visas kombinācijas , ir jāizslēdz no visiem izvietojumiem apakškopas, kas atšķiras pēc kārtas (būs gabali), t.i. dalīts ar .

5. piemērs: Cik daudzos veidos jūs varat izvēlēties 3 dažādas krāsas no pieejamajām piecām?

Risinājums. Krāsu izvēles secībai nav nozīmes. Vienīgais, kam ir nozīme, ir izvēlētās krāsas. Tāpēc iespēju skaits ir vienāds ar:
.

6. piemērs: Cik daudzos veidos var uzšūt trīskrāsu svītrainus karogus, ja ir materiāls piecās dažādās krāsās?

Risinājums. Svarīga ir svītru atlases secība, tāpēc šādu karodziņu skaits ir:
.

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, 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 ar 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 četrciparu 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.

1. Atrodiet anagrammu skaitu vārdiem VERESK, BALAGAN, CITYMAN.
2. Atrodiet anagrammu skaitu vārdiem BAOBABS, BALLĀDE, GRIEŠANA, ANAGRAMMA, MATEMĀTIKA, KOMBINATORIKA, AIZSARDZĪBA.
3. Cik daudzos veidos var izmitināt 7 apmeklētājus trīs viesnīcas numuros: vienvietīgā, divvietīgā un četrvietīgā?
4. 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?
5. 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?
6. Pirms eksāmena profesors pusei eksaminējamo solīja likt sliktas atzīmes. Uz eksāmenu ieradās 20 skolēni. Cik daudzos veidos viņš var izpildīt savu solījumu?
7. Cik vārdu var izveidot no pieciem burtiem A un ne vairāk kā trīs burtiem B?
8. Ir pieejams šokolādes, zemeņu un piena saldējums. Cik veidos var nopirkt trīs saldējumus?
9. 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?
10. 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?
11. Cik diagonāļu ir izliektā n-kvadrāts?
12. Cik daudz lietu tur ir? n- ciparu numuri?
13. Cik ir desmit ciparu skaitļu, kuriem ir vismaz divi identiski cipari?
14. 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?
15. Cik piecciparu skaitļu apzīmējumā ir cipars 1?
16. Cik daudzos veidos balto un melno ķēniņu var novietot uz šaha galdiņa, netrāpot viens otram?
17. Cik dalītāju ir skaitlim 10800?

Abstrakts par tēmu:

Aizpildījis 10. klases skolnieks “B”

53. vidusskola

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_________________________________________________________________	-
Problēmas patstāvīgam risinājumam___________________________________	10
Bibliogrāfija________________________________________	11

No kombinatorikas vēstures

Kombinatorika nodarbojas ar dažāda veida savienojumiem, 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 un poētisko darbu struktūras izpēti. 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) arī franču autors A. kombinācijām un permutācijām velta veselu nodaļu.
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 matemātisko kvadrātu un skaitļu skaitļu sakarībām ar savienojumu teoriju. Terminu “kombinatorika” sāka lietot pēc tam, kad Leibnics 1665. gadā publicēja savu darbu “Diskurss par kombinēšanas mākslu”, kas pirmo reizi sniedza zinātnisku pamatojumu kombināciju un permutāciju teorijai. 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 iegūt no diviem pamata apgalvojumiem, kas attiecas uz ierobežotām kopām - summas likuma un reizinājuma noteikuma.

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 piemēri

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 praktiskajam darbam?

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 izvēlēties k veidos, bet elementu Y — m, tad pāri (X,Y) var izvēlēties k*m veidos.

Tas ir, ja pirmajā plauktā ir 5 grāmatas, bet 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 piemēri

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 kā 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 piemēri

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.

Lai vizuāli atrisinātu problēmu, bieži tiek izmantoti arī Eilera apļi. Piemēram:

No 100 tūristiem, kas dodas ārzemju ceļojumā, 30 cilvēki runā vāciski, 28 - angliski, 42 - franču valodā, 10 - angļu un franču valodā, 5 - vācu un franču valodā, 3 - visi trīs. tūristi nerunā nevienā valodā?

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 vispārējā aprindu daļā ievadām skaitli 3. 10 cilvēki runā angliski un franciski, un 3 no tiem runā arī vāciski. Līdz ar to 10-3=7 cilvēki runā tikai angļu un franču valodā.

Līdzīgi mēs atklājam, ka 8-3=5 cilvēki runā tikai angļu un vācu valodā, bet 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 izvietošanu 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 piemēri

Cik dažādus sešciparu skaitļus var izveidot no cipariem 0, 1, 2, 3, 4,5, ja cipari cipari 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 ir 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.