Ang artikulong ito ay tumutuon sa isang espesyal na seksyon ng matematika na tinatawag na combinatorics. Mga formula, panuntunan, halimbawa ng paglutas ng problema - lahat ng ito ay makikita mo dito sa pamamagitan ng pagbabasa ng artikulo hanggang sa dulo.
So, ano ang seksyong ito? Ang Combinatorics ay tumatalakay sa isyu ng pagbibilang ng anumang bagay. Ngunit sa kasong ito, ang mga bagay ay hindi mga plum, peras o mansanas, ngunit iba pa. Tinutulungan tayo ng mga combinatorics na mahanap ang posibilidad ng isang kaganapan. Halimbawa, kapag naglalaro ng baraha, ano ang posibilidad na may trump card ang kalaban? O tulad ng isang halimbawa - ano ang posibilidad na makakuha ka ng eksaktong puti mula sa isang bag ng dalawampung bola? Para sa ganitong uri ng mga gawain na kailangan nating malaman kahit man lang ang mga pangunahing kaalaman ng seksyong ito ng matematika.
Combinatorial configurations
Isinasaalang-alang ang isyu ng mga pangunahing konsepto at pormula ng combinatorics, hindi natin mabibigyang pansin ang mga combinatorial configuration. Ginagamit ang mga ito hindi lamang para sa pagbabalangkas, kundi pati na rin para sa paglutas ng iba't ibang mga problema sa kombinatorial. Ang mga halimbawa ng naturang mga modelo ay:
- placement;
- permutation;
- kumbinasyon;
- komposisyon ng numero;
- split number.
Pag-uusapan natin ang unang tatlo nang mas detalyado sa ibang pagkakataon, ngunit bibigyan natin ng pansin ang komposisyon at paghahati sa seksyong ito. Kapag pinag-uusapan nila ang komposisyon ng isang tiyak na numero (sabihin, a), ang ibig nilang sabihin ay ang representasyon ng numero a bilang isang ordered sum ng ilang positibong numero. At ang hati ay isang hindi nakaayos na kabuuan.
Seksyon
Bago tayo direktang pumunta sa mga formula ng combinatorics at ang pagsasaalang-alang ng mga problema, ito ay nagkakahalaga ng pagbibigay pansin sa katotohanan na ang combinatorics, tulad ng ibang mga seksyon ng matematika, ay may sariling mga subsection. Kabilang dito ang:
- enumerative;
- structural;
- extreme;
- Teorya ni Ramsey;
- probabilistic;
- topological;
- walang katapusan.
Sa unang kaso, pinag-uusapan natin ang tungkol sa enumerative combinatorics, isinasaalang-alang ng mga problema ang enumeration o pagbibilang ng iba't ibang configuration na nabuo ng mga elemento ng set. Bilang isang patakaran, ang ilang mga paghihigpit ay ipinapataw sa mga set na ito (distinguishability, indistinguishability, ang posibilidad ng pag-uulit, at iba pa). At ang bilang ng mga pagsasaayos na ito ay kinakalkula gamit ang panuntunan ng pagdaragdag o pagpaparami, na pag-uusapan natin sa ibang pagkakataon. Kasama sa mga structural combinatorics ang mga teorya ng mga graph at matroid. Ang isang halimbawa ng isang extremal combinatorics na problema ay kung ano ang pinakamalaking dimensyon ng isang graph na nakakatugon sa mga sumusunod na katangian… Sa ikaapat na talata, binanggit namin ang teorya ng Ramsey, na nag-aaral ng pagkakaroon ng mga regular na istruktura sa mga random na pagsasaayos. probabilistikoAng mga combinatorics ay kayang sagutin ang tanong - ano ang posibilidad na ang isang naibigay na hanay ay may isang tiyak na pag-aari. Tulad ng maaari mong hulaan, ang topological combinatorics ay naglalapat ng mga pamamaraan sa topology. At panghuli, ang ikapitong punto - pinag-aaralan ng infinitary combinatorics ang paggamit ng mga combinatorics na pamamaraan sa mga infinite set.
Panuntunan sa karagdagan
Sa mga formula ng combinatorics, mahahanap ng isa ang medyo simple, na matagal na nating pamilyar. Ang isang halimbawa ay ang sum rule. Ipagpalagay na binigyan tayo ng dalawang aksyon (C at E), kung sila ay kapwa eksklusibo, ang aksyon C ay maaaring gawin sa maraming paraan (halimbawa, a), at ang aksyon E ay maaaring gawin sa b-ways, pagkatapos ay alinman sa mga ito (C o E) ay maaaring gawin sa isang + b na paraan.
Sa teorya, ito ay medyo mahirap unawain, susubukan naming ihatid ang buong punto sa isang simpleng halimbawa. Kunin natin ang karaniwang bilang ng mga mag-aaral sa isang klase - sabihin nating dalawampu't lima. Kabilang sa kanila ang labinlimang babae at sampung lalaki. Isang attendant ang nakatalaga sa klase araw-araw. Ilang paraan ang mayroon para magtalaga ng isang attendant sa klase ngayon? Ang solusyon sa problema ay medyo simple, gagamitin namin ang panuntunan sa karagdagan. Ang teksto ng gawain ay hindi nagsasabi na ang mga lalaki o mga batang babae lamang ang maaaring mag-duty. Samakatuwid, maaaring alinman sa labinlimang babae o alinman sa sampung lalaki. Sa paglalapat ng sum rule, nakakakuha tayo ng medyo simpleng halimbawa na madaling makayanan ng isang mag-aaral sa elementarya: 15 + 10. Kapag nakalkula, nakuha natin ang sagot: dalawampu't lima. Ibig sabihin, dalawampu't limang paraan lamangmagtalaga ng klase sa tungkulin para sa araw na ito.
Panuntunan sa pagpaparami
Ang panuntunan ng multiplikasyon ay kabilang din sa mga pangunahing formula ng combinatorics. Magsimula tayo sa teorya. Ipagpalagay na kailangan nating magsagawa ng ilang mga aksyon (a): ang unang aksyon ay ginanap sa 1 paraan, ang pangalawa - sa 2 paraan, ang pangatlo - sa 3 paraan, at iba pa hanggang sa ang huling a-aksyon ay ginanap sa mga paraan. Pagkatapos ang lahat ng mga pagkilos na ito (kung saan mayroon tayong kabuuan) ay maaaring isagawa sa N paraan. Paano makalkula ang hindi kilalang N? Tutulungan tayo ng formula dito: N \u003d c1c2c3…ca.
Muli, walang malinaw sa teorya, lumipat tayo sa isang simpleng halimbawa ng paglalapat ng panuntunan sa pagpaparami. Kunin natin ang parehong klase ng dalawampu't limang tao, kung saan nag-aaral ang labinlimang babae at sampung lalaki. Sa pagkakataong ito lamang kailangan nating pumili ng dalawang tagapag-alaga. Maaari silang maging mga lalaki o babae lamang, o isang lalaki na may babae. Bumaling tayo sa elementarya na solusyon ng problema. Pinipili namin ang unang attendant, tulad ng napagpasyahan namin sa huling talata, nakakakuha kami ng dalawampu't limang posibleng opsyon. Ang pangalawang taong naka-duty ay maaaring alinman sa mga natitirang tao. Mayroon kaming dalawampu't limang estudyante, pumili kami ng isa, ibig sabihin, alinman sa natitirang dalawampu't apat na tao ay maaaring maging pangalawa sa tungkulin. Sa wakas, inilalapat namin ang panuntunan sa pagpaparami at nalaman na ang dalawang attendant ay maaaring mapili sa anim na raang paraan. Nakuha namin ang numerong ito sa pamamagitan ng pag-multiply ng dalawampu't lima at dalawampu't apat.
Swap
Ngayon ay isasaalang-alang natin ang isa pang combinatorics formula. Sa seksyong ito ng artikulo, kamiPag-usapan natin ang tungkol sa mga permutasyon. Isaalang-alang kaagad ang problema sa isang halimbawa. Kumuha tayo ng mga bola ng bilyar, mayroon tayong n-th number nito. Kailangan naming kalkulahin: kung gaano karaming mga pagpipilian ang mayroon upang ayusin ang mga ito sa isang hilera, iyon ay, upang gumawa ng isang ordered set.
Magsimula tayo, kung wala tayong mga bola, wala rin tayong mga pagpipilian sa paglalagay. At kung mayroon kaming isang bola, kung gayon ang pag-aayos ay pareho din (sa matematika, maaari itong isulat bilang mga sumusunod: Р1=1). Maaaring isaayos ang dalawang bola sa dalawang magkaibang paraan: 1, 2 at 2, 1. Samakatuwid, Р2=2. Maaaring isaayos ang tatlong bola sa anim na paraan (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. At kung walang tatlong ganoong bola, ngunit sampu o labinlima? Upang ilista ang lahat ng posibleng mga opsyon ay napakahaba, pagkatapos ay ang mga combinatorics ay tutulong sa amin. Tutulungan tayo ng formula ng permutation na mahanap ang sagot sa ating tanong. Pn=nP(n-1). Kung susubukan nating gawing simple ang formula, makakakuha tayo ng: Pn=n (n - 1) … 21. At ito ang produkto ng unang natural na mga numero. Ang nasabing numero ay tinatawag na factorial, at tinutukoy bilang n!
Pag-isipan natin ang problema. Ang pinuno tuwing umaga ay nagtatayo ng kanyang detatsment sa isang linya (dalawampung tao). Mayroong tatlong matalik na kaibigan sa detatsment - Kostya, Sasha at Lesha. Ano ang posibilidad na magkatabi sila? Upang mahanap ang sagot sa tanong, kailangan mong hatiin ang posibilidad ng isang "magandang" resulta sa kabuuang bilang ng mga resulta. Ang kabuuang bilang ng mga permutasyon ay 20!=2.5 quintillion. Paano mabibilang ang bilang ng "magandang" resulta? Ipagpalagay na sina Kostya, Sasha at Lesha ay isang superman. Tapos tayoLabingwalong subjects lang kami. Ang bilang ng mga permutasyon sa kasong ito ay 18=6.5 quadrillion. Sa lahat ng ito, sina Kostya, Sasha at Lesha ay maaaring arbitraryong lumipat sa kanilang sarili sa kanilang hindi mahahati na triple, at ito ay 3 pa!=6 na pagpipilian. Kaya mayroon kaming 18 "magandang" konstelasyon sa kabuuan!3! Kailangan lang nating hanapin ang gustong probabilidad: (18!3!) / 20! Na humigit-kumulang 0.016. Kung iko-convert sa isang porsyento, ito ay magiging 1.6% lang.
Accommodation
Ngayon ay isasaalang-alang natin ang isa pang napakahalaga at kinakailangang combinatorics formula. Ang tirahan ay ang aming susunod na isyu, na iminumungkahi naming isaalang-alang mo sa seksyong ito ng artikulo. Magiging mas kumplikado tayo. Ipagpalagay natin na gusto nating isaalang-alang ang mga posibleng permutasyon, hindi lamang mula sa buong set (n), ngunit mula sa isang mas maliit (m). Ibig sabihin, isinasaalang-alang namin ang mga permutasyon ng n item ng m.
Ang mga pangunahing formula ng combinatorics ay hindi lamang dapat isaulo, ngunit unawain. Kahit na sa kabila ng katotohanan na sila ay nagiging mas kumplikado, dahil wala kaming isang parameter, ngunit dalawa. Ipagpalagay na m \u003d 1, pagkatapos ay A \u003d 1, m \u003d 2, pagkatapos ay A \u003d n(n - 1). Kung mas pasimplehin natin ang formula at lumipat sa notasyon gamit ang mga factorial, nakakakuha tayo ng medyo maigsi na formula: A \u003d n! / (n - m)!
Kumbinasyon
Isinaalang-alang namin ang halos lahat ng mga pangunahing formula ng combinatorics na may mga halimbawa. Ngayon ay lumipat tayo sa huling yugto ng pagsasaalang-alang sa pangunahing kurso ng combinatorics - pagkilala sa kumbinasyon. Ngayon ay pipili tayo ng m aytem mula sa n mayroon tayo, habang pipiliin natin ang lahat ng ito sa lahat ng posibleng paraan. Paano ito naiiba sa tirahan? hindi namin gagawinisaalang-alang ang kaayusan. Magiging kumbinasyon ang hindi nakaayos na set na ito.
Agad na ipakilala ang notasyon: C. Kumuha kami ng mga placement ng m ball mula sa n. Huminto kami sa pagbibigay pansin sa order at makakuha ng paulit-ulit na kumbinasyon. Upang makuha ang bilang ng mga kumbinasyon, kailangan nating hatiin ang bilang ng mga pagkakalagay sa m! (m factorial). Iyon ay, C \u003d A / m! Kaya, may ilang mga paraan upang pumili mula sa n bola, humigit-kumulang katumbas ng ilan ang pipiliin halos lahat. Mayroong lohikal na pagpapahayag para dito: ang pagpili ng kaunti ay kapareho ng pagtatapon ng halos lahat. Mahalaga ring banggitin sa puntong ito na ang maximum na bilang ng mga kumbinasyon ay maaaring makamit kapag sinusubukang pumili ng kalahati ng mga item.
Paano pumili ng formula para malutas ang isang problema?
Nasuri namin nang detalyado ang mga pangunahing formula ng combinatorics: placement, permutation at combination. Ngayon ang aming gawain ay upang mapadali ang pagpili ng kinakailangang formula para sa paglutas ng problema sa combinatorics. Magagamit mo ang sumusunod na medyo simpleng scheme:
- Tanungin ang iyong sarili: isinasaalang-alang ba ang pagkakasunud-sunod ng mga elemento sa teksto ng problema?
- Kung ang sagot ay hindi, gamitin ang kumbinasyong formula (C=n! / (m!(n - m)!)).
- Kung hindi ang sagot, kailangan mong sagutin ang isa pang tanong: kasama ba ang lahat ng elemento sa kumbinasyon?
- Kung oo ang sagot, gamitin ang permutation formula (P=n!).
- Kung ang sagot ay hindi, gamitin ang formula ng alokasyon (A=n! / (n - m)!).
Halimbawa
Isinaalang-alang namin ang mga elemento ng combinatorics, formula at ilang iba pang isyu. Ngayon ay lumipat tayo saisinasaalang-alang ang isang tunay na problema. Isipin mo na may kiwi, orange, at saging sa harap mo.
Unang tanong: sa ilang paraan maisasaayos muli ang mga ito? Upang gawin ito, ginagamit namin ang permutation formula: P=3!=6 na paraan.
Ikalawang tanong: sa ilang paraan mapipili ang isang prutas? Ito ay malinaw, mayroon lamang kaming tatlong mga pagpipilian - pumili ng kiwi, orange o saging, ngunit inilalapat namin ang kumbinasyon na formula: C \u003d 3! / (2!1!)=3.
Ikatlong tanong: sa ilang paraan mapipili ang dalawang prutas? Anong mga pagpipilian ang mayroon tayo? Kiwi at orange; kiwi at saging; orange at saging. Iyon ay, tatlong mga pagpipilian, ngunit ito ay madaling suriin gamit ang kumbinasyon ng formula: C \u003d 3! / (1!2!)=3
Ikaapat na tanong: sa ilang paraan mapipili ang tatlong prutas? Tulad ng nakikita mo, mayroon lamang isang paraan upang pumili ng tatlong prutas: kumuha ng kiwi, isang orange at isang saging. C=3! / (0!3!)=1.
Ikalimang tanong: ilang paraan ang maaari mong piliin kahit isang prutas? Ang kundisyong ito ay nagpapahiwatig na maaari tayong kumuha ng isa, dalawa o lahat ng tatlong prutas. Samakatuwid, idinagdag namin ang C1 + C2 + C3=3 + 3 + 1=7. Ibig sabihin, mayroon kaming pitong paraan upang kumuha ng kahit isang piraso ng prutas mula sa mesa.
