Šajā rakstā galvenā uzmanība tiks pievērsta īpašai matemātikas sadaļai, ko sauc par kombinatoriku. Formulas, noteikumi, problēmu risināšanas piemēri – to visu var atrast šeit, izlasot rakstu līdz pašām beigām.
Tātad, kas ir šī sadaļa? Kombinatorika nodarbojas ar jebkuru objektu skaitīšanas jautājumu. Bet šajā gadījumā objekti nav plūmes, bumbieri vai āboli, bet gan kaut kas cits. Kombinatorika palīdz mums atrast notikuma iespējamību. Piemēram, spēlējot kārtis, kāda ir varbūtība, ka pretiniekam ir trumpis? Vai arī šāds piemērs - kāda ir iespējamība, ka no divdesmit bumbiņu maisa dabūsi tieši b altu? Tieši šāda veida uzdevumiem mums ir jāzina vismaz šīs matemātikas sadaļas pamati.
Kombinatoriskās konfigurācijas
Ņemot vērā jautājumu par kombinatorikas pamatjēdzieniem un formulām, mēs nevaram nepievērst uzmanību kombinatoriskajām konfigurācijām. Tos izmanto ne tikai formulēšanai, bet arī dažādu kombinatorisku uzdevumu risināšanai. Šādu modeļu piemēri:
- izvietojums;
- permutācija;
- kombinācija;
- skaitļu sastāvs;
- dalīts numurs.
Par pirmajiem trim sīkāk parunāsim vēlāk, taču šajā sadaļā pievērsīsim uzmanību kompozīcijai un sadalīšanai. Kad viņi runā par noteikta skaitļa sastāvu (teiksim, a), viņi domā skaitļa a attēlojumu kā dažu pozitīvu skaitļu sakārtotu summu. Un sadalīšana ir nesakārtota summa.
Sadaļas
Pirms ķeramies tieši pie kombinatorikas formulām un uzdevumu izskatīšanas, ir vērts pievērst uzmanību tam, ka kombinatorikai, tāpat kā citām matemātikas sadaļām, ir savas apakšnodaļas. Tie ietver:
- uzskaitāms;
- strukturāls;
- extreme;
- Remzija teorija;
- probabilistic;
- topoloģisks;
- bezgalīgs.
Pirmajā gadījumā runa ir par uzskaitāmo kombinatoriku, problēmās tiek aplūkota dažādu konfigurāciju uzskaitīšana vai saskaitīšana, kuras veido kopu elementi. Parasti šīm kopām tiek noteikti daži ierobežojumi (atšķiramība, neatšķiramība, atkārtošanās iespēja utt.). Un šo konfigurāciju skaits tiek aprēķināts, izmantojot saskaitīšanas vai reizināšanas likumu, par kuru mēs runāsim nedaudz vēlāk. Strukturālā kombinatorika ietver grafiku un matroīdu teorijas. Ekstremālās kombinatorikas problēmas piemērs ir, kura ir lielākā grafa dimensija, kas apmierina šādas īpašības… Ceturtajā rindkopā mēs minējām Remzija teoriju, kas pēta regulāru struktūru klātbūtni nejaušās konfigurācijās. Varbūtībaskombinatorika spēj atbildēt uz jautājumu – kāda ir varbūtība, ka dotajai kopai ir noteikta īpašība. Kā jūs varētu nojaust, topoloģiskā kombinatorika izmanto metodes topoloģijā. Un visbeidzot, septītais punkts – bezgalīgā kombinatorika pēta kombinatorikas metožu pielietojumu bezgalīgām kopām.
Papildināšanas noteikums
Starp kombinatorikas formulām var atrast pavisam vienkāršas, ar kurām esam pazīstami jau sen. Piemērs ir summas noteikums. Pieņemsim, ka mums ir dotas divas darbības (C un E), ja tās ir viena otru izslēdzošas, darbību C var veikt vairākos veidos (piemēram, a), un darbību E var veikt b-veidos, tad jebkurš no tiem (C vai E) var izdarīt a + b veidā.
Teorētiski to ir diezgan grūti saprast, mēs centīsimies nodot visu būtību ar vienkāršu piemēru. Ņemsim vidējo skolēnu skaitu vienā klasē – pieņemsim, ka tas ir divdesmit pieci. Viņu vidū ir piecpadsmit meitenes un desmit zēni. Katru dienu klasē tiek nozīmēts viens dežurants. Cik daudzos veidos šodien var iecelt klases dežurantu? Problēmas risinājums ir diezgan vienkāršs, mēs izmantosim pievienošanas noteikumu. Uzdevuma tekstā nav teikts, ka dežūrēt drīkst tikai zēni vai tikai meitenes. Tāpēc tā varētu būt jebkura no piecpadsmit meitenēm vai jebkurš no desmit zēniem. Piemērojot summas noteikumu, mēs iegūstam diezgan vienkāršu piemēru, ar kuru sākumskolas skolēns var viegli tikt galā: 15 + 10. Aprēķinot, mēs saņemam atbildi: divdesmit pieci. Tas ir, ir tikai divdesmit pieci veidipiešķirt šodienas darba stundu.
Reizināšanas kārtula
Reizināšanas likums pieder arī kombinatorikas pamatformulām. Sāksim ar teoriju. Pieņemsim, ka mums ir jāveic vairākas darbības (a): pirmā darbība tiek veikta 1 veidos, otrā - 2 veidos, trešā - 3 veidos un tā tālāk, līdz tiek veikta pēdējā a darbība. Tad visas šīs darbības (kuras mums ir kopā) var veikt N veidos. Kā aprēķināt nezināmo N? Formula mums palīdzēs: N \u003d c1c2c3…ca.
Atkal, teorētiski nekas nav skaidrs, pāriesim pie vienkārša reizināšanas likuma piemērošanas piemēra. Ņemsim to pašu divdesmit piecu cilvēku klasi, kurā mācās piecpadsmit meitenes un desmit zēni. Tikai šoreiz mums jāizvēlas divi pavadoņi. Tie var būt tikai zēni vai meitenes, vai zēns ar meiteni. Mēs pievēršamies elementāram problēmas risinājumam. Mēs izvēlamies pirmo pavadoni, kā mēs nolēmām pēdējā rindkopā, mēs iegūstam divdesmit piecus iespējamos variantus. Otrā dežurējošā persona var būt jebkura no atlikušajām personām. Mums bija divdesmit pieci skolēni, mēs izvēlējāmies vienu, kas nozīmē, ka jebkurš no atlikušajiem divdesmit četriem cilvēkiem var būt otrais dežūrējošs. Visbeidzot, mēs piemērojam reizināšanas noteikumu un atklājam, ka divus pavadoņus var izvēlēties sešsimt veidos. Mēs ieguvām šo skaitli, reizinot divdesmit piecus un divdesmit četrus.
Mainīt
Tagad mēs apsvērsim vēl vienu kombinatorikas formulu. Šajā raksta sadaļā mēsParunāsim par permutācijām. Nekavējoties apsveriet problēmu ar piemēru. Ņemsim biljarda bumbiņas, mums ir n-tais to skaits. Mums jāaprēķina: cik ir iespēju tos sakārtot pēc kārtas, tas ir, izveidot pasūtītu komplektu.
Sāksim, ja mums nav bumbas, tad mums ir arī nulles izvietojuma iespējas. Un, ja mums ir viena bumbiņa, tad arī izkārtojums ir vienāds (matemātiski to var uzrakstīt šādi: Р1=1). Divas bumbiņas var izkārtot divos dažādos veidos: 1, 2 un 2, 1. Tāpēc Р2=2. Trīs bumbiņas var izkārtot sešos veidos (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Un ja šādas bumbas nav trīs, bet desmit vai piecpadsmit? Visu iespējamo variantu saraksts ir ļoti garš, tad mums talkā nāk kombinatorika. Permutācijas formula palīdzēs mums atrast atbildi uz mūsu jautājumu. Pn=nP(n-1). Mēģinot vienkāršot formulu, mēs iegūstam: Pn=n (n - 1) … 21. Un tas ir pirmo naturālo skaitļu reizinājums. Šādu skaitli sauc par faktoriālu un apzīmē ar n!
Apsvērsim problēmu. Vadītājs katru rītu veido savu nodaļu rindā (divdesmit cilvēki). Atdalījumā ir trīs labākie draugi - Kostja, Saša un Leša. Kāda ir iespējamība, ka viņi būs viens otram blakus? Lai atrastu atbildi uz jautājumu, “laba” iznākuma varbūtība ir jāsadala ar kopējo rezultātu skaitu. Kopējais permutāciju skaits ir 20!=2,5 kvintiljoni. Kā saskaitīt "labo" rezultātu skaitu? Pieņemsim, ka Kostja, Saša un Leša ir viens supermens. Tad mēsMums ir tikai astoņpadsmit priekšmeti. Permutāciju skaits šajā gadījumā ir 18=6,5 kvadriljoni. Ar visu to Kostja, Saša un Leša var patvaļīgi pārvietoties savā starpā savā nedalāmajā trīskāršā, un tas ir vēl 3!=6 iespējas. Tātad mums kopā ir 18 “labi” zvaigznāji!3! Mums tikai jāatrod vēlamā varbūtība: (18!3!) / 20! Kas ir aptuveni 0,016. Pārvēršot procentos, izrādās tikai 1,6%.
Izmitināšana
Tagad mēs apsvērsim vēl vienu ļoti svarīgu un nepieciešamu kombinatorikas formulu. Izmitināšana ir mūsu nākamais izdevums, kuru mēs iesakām apsvērt šajā raksta sadaļā. Mēs kļūsim sarežģītāki. Pieņemsim, ka mēs vēlamies apsvērt iespējamās permutācijas, tikai nevis no visas kopas (n), bet gan no mazākas (m). Tas ir, mēs uzskatām n vienumu permutācijas ar m.
Kombinatorikas pamatformulas nav vienkārši jāiegaumē, bet arī jāsaprot. Pat neskatoties uz to, ka tie kļūst sarežģītāki, jo mums nav viens parametrs, bet divi. Pieņemsim, ka m \u003d 1, tad A=1, m \u003d 2, tad A=n(n - 1). Ja vēl vairāk vienkāršosim formulu un pārejam uz apzīmējumu, izmantojot faktoriālus, mēs iegūstam diezgan kodolīgu formulu: A \u003d n! / (n - m)!
Kombinācija
Mēs esam izskatījuši gandrīz visas kombinatorikas pamatformulas ar piemēriem. Tagad pāriesim uz kombinatorikas pamatkursa izskatīšanas pēdējo posmu - kombinācijas iepazīšanu. Tagad mēs izvēlēsimies m preces no n, kas mums ir, savukārt mēs tos visus izvēlēsimies visos iespējamos veidos. Kā tad tas atšķiras no izmitināšanas? Mēs to nedarīsimapsvērt kārtību. Šis nesakārtotais komplekts būs kombinācija.
Nekavējoties ievadiet apzīmējumu: C. Mēs ņemam m lodīšu izvietojumus no n. Mēs pārstājam pievērst uzmanību kārtībai un iegūstam atkārtotas kombinācijas. Lai iegūtu kombināciju skaitu, izvietojumu skaits jāsadala ar m! (m faktoriāls). Tas ir, C \u003d A / m! Tādējādi ir daži veidi, kā izvēlēties no n bumbiņām, kas ir aptuveni vienādas ar to, cik daudz izvēlēties gandrīz visu. Tam ir loģisks izteiciens: izvēlēties nedaudz ir tas pats, kas izmest gandrīz visu. Šajā brīdī ir arī svarīgi pieminēt, ka maksimālo kombināciju skaitu var sasniegt, mēģinot atlasīt pusi no vienumiem.
Kā izvēlēties formulu problēmas risināšanai?
Mēs esam sīki izpētījuši kombinatorikas pamatformulas: izvietojumu, permutāciju un kombināciju. Tagad mūsu uzdevums ir atvieglot vajadzīgās formulas izvēli problēmas risināšanai kombinatorikā. Varat izmantot šādu diezgan vienkāršu shēmu:
- Pajautājiet sev: vai uzdevuma tekstā ir ņemta vērā elementu secība?
- Ja atbilde ir nē, izmantojiet kombinācijas formulu (C=n! / (m!(n - m)!)).
- Ja atbilde ir nē, tad jāatbild vēl uz vienu jautājumu: vai kombinācijā ir iekļauti visi elementi?
- Ja atbilde ir jā, izmantojiet permutācijas formulu (P=n!).
- Ja atbilde ir nē, izmantojiet sadales formulu (A=n! / (n - m)!).
Piemērs
Esam apsvēruši kombinatorikas elementus, formulas un dažus citus jautājumus. Tagad pāriesim pieapsverot reālu problēmu. Iedomājieties, ka jūsu priekšā ir kivi, apelsīns un banāns.
Pirmais jautājums: cik daudzos veidos tos var pārkārtot? Lai to izdarītu, mēs izmantojam permutācijas formulu: P=3!=6 veidi.
Otrais jautājums: cik dažādos veidos var izvēlēties vienu augli? Tas ir acīmredzams, mums ir tikai trīs iespējas - izvēlēties kivi, apelsīnu vai banānu, bet mēs izmantojam kombinācijas formulu: C \u003d 3! / (2!1!)=3.
Trešais jautājums: cik dažādos veidos var izvēlēties divus augļus? Kādas iespējas mums ir? Kivi un apelsīns; kivi un banāns; apelsīns un banāns. Tas ir, trīs iespējas, taču to ir viegli pārbaudīt, izmantojot kombinācijas formulu: C \u003d 3! / (1!2!)=3
Ceturtais jautājums: cik dažādos veidos var izvēlēties trīs augļus? Kā redzat, ir tikai viens veids, kā izvēlēties trīs augļus: ņem kivi, apelsīnu un banānu. C=3! / (0!3!)=1.
Piektais jautājums: cik daudzos veidos jūs varat izvēlēties vismaz vienu augli? Šis nosacījums nozīmē, ka mēs varam ņemt vienu, divus vai visus trīs augļus. Tāpēc mēs pievienojam C1 + C2 + C3=3 + 3 + 1=7. Tas ir, mums ir septiņi veidi, kā no galda izņemt vismaz vienu augļa gabalu.
