Энэ нийтлэл нь комбинаторик гэж нэрлэгддэг математикийн тусгай хэсэгт анхаарлаа хандуулах болно. Томьёо, дүрэм, асуудал шийдвэрлэх жишээ - энэ бүгдийг та нийтлэлийг эцэс хүртэл уншсанаар эндээс олж мэдэх боломжтой.
Тэгвэл энэ хэсэг юу вэ? Комбинаторик нь аливаа объектыг тоолох асуудлыг авч үздэг. Гэхдээ энэ тохиолдолд объектууд нь чавга, лийр, алим биш, харин өөр зүйл юм. Комбинаторик нь үйл явдлын магадлалыг олоход тусалдаг. Жишээлбэл, хөзөр тоглох үед өрсөлдөгч нь бүрээтэй байх магадлал хэд вэ? Эсвэл ийм жишээ - хорин бөмбөгтэй уутнаас яг цагаан өнгөтэй болох магадлал хэд вэ? Энэ төрлийн даалгаврын хувьд бид математикийн энэ хэсгийн наад зах нь үндсийг мэдэх хэрэгтэй.
Комбинаторын тохиргоо
Комбинаторикийн үндсэн ойлголт, томьёоны асуудлыг авч үзвэл комбинаторийн тохиргоонд анхаарлаа хандуулахгүй байх аргагүй. Тэдгээрийг зөвхөн томъёололд төдийгүй янз бүрийн комбинаторын асуудлыг шийдвэрлэхэд ашигладаг. Ийм загваруудын жишээ нь:
- байруулга;
- орчлуулах;
- хослол;
- тооны найрлага;
- хуваасан тоо.
Бид эхний гурвын талаар дараа дэлгэрэнгүй ярих болно, гэхдээ бид энэ хэсэгт найрлага, хуваагдалд анхаарлаа хандуулах болно. Тэд тодорхой тооны найрлагын талаар ярихдаа (а гэх мэт) а тоог зарим эерэг тоонуудын дараалсан нийлбэр хэлбэрээр дүрслэхийг хэлнэ. Мөн хуваах нь эрэмбэлэгдээгүй нийлбэр юм.
Хэсэг
Комбинаторикийн томьёо болон асуудлыг авч үзэхэд шууд орохын өмнө математикийн бусад хэсгүүдийн нэгэн адил комбинаторик нь өөрийн гэсэн дэд хэсгүүдтэй байдгийг анхаарч үзэх нь зүйтэй. Үүнд:
- тоолох;
- бүтцийн;
- хэт;
- Рэмсигийн онол;
- магадлал;
- топологи;
- хязгааргүй.
Эхний тохиолдолд бид тоологч комбинаторикийн тухай ярьж байгаа бол олонлогийн элементүүдээр үүсгэгдсэн янз бүрийн тохиргоонуудыг тоолох эсвэл тоолох асуудлыг авч үздэг. Дүрмээр бол эдгээр багцад зарим хязгаарлалт тавьдаг (ялгагдах, ялгагдахгүй байх, давтагдах боломж гэх мэт). Мөн эдгээр тохиргооны тоог нэмэх эсвэл үржүүлэх дүрмийг ашиглан тооцдог бөгөөд энэ талаар бид дараа нь ярих болно. Бүтцийн комбинаторик нь график ба матроидуудын онолыг агуулдаг. Экстремал комбинаторикийн бодлогын жишээ бол дараах шинж чанаруудыг хангасан графикийн хамгийн том хэмжээс нь юу вэ… Дөрөвдүгээр догол мөрөнд бид санамсаргүй тохиргоонд ердийн бүтэц байдгийг судалдаг Рамсигийн онолыг дурдсан. Магадлалтайкомбинаторик нь өгөгдсөн олонлог тодорхой шинж чанартай байх магадлал хэд вэ гэсэн асуултанд хариулж чаддаг. Таны таамаглаж байгаагаар топологийн комбинаторик нь топологи дахь аргуудыг ашигладаг. Эцэст нь долоо дахь цэг нь хязгааргүй олонлогт комбинаторик аргуудыг хэрэглэхийг судалдаг.
Нэмэх дүрэм
Комбинаторикийн томъёонуудын дотроос бидний эртнээс сайн мэддэг маш энгийн томъёог олж болно. Жишээ нь нийлбэрийн дүрэм юм. Бидэнд хоёр үйлдэл (С ба Е) өгөгдсөн гэж бодъё, хэрэв тэдгээр нь бие биенээ үгүйсгэдэг бол С үйлдлийг хэд хэдэн аргаар хийж болно (жишээ нь, a), Е үйлдлийг b хэлбэрээр хийж болно, дараа нь тэдгээрийн аль нэг нь (C) эсвэл E) a + b аргаар хийж болно.
Онолын хувьд үүнийг ойлгоход нэлээд хэцүү тул бид энгийн жишээгээр бүх санааг илэрхийлэхийг хичээх болно. Нэг ангийн сурагчдын дундаж тоог авч үзье - энэ нь хорин таван гэж бодъё. Тэдний дунд арван таван охин, арван хүү байна. Өдөр бүр нэг үйлчлэгч ангид хуваарилагддаг. Өнөөдөр ангийн жижүүрийг томилох хэдэн арга байдаг вэ? Асуудлын шийдэл нь маш энгийн тул бид нэмэлт дүрэмд хандах болно. Даалгаврын бичвэрт зөвхөн хөвгүүд эсвэл зөвхөн охидууд үүрэг гүйцэтгэж болно гэж заагаагүй байна. Тиймээс арван таван охины аль нь ч, арван хөвгүүдийн аль нь ч байж болно. Нийлбэрийн дүрмийг ашигласнаар бид бага сургуулийн сурагч амархан даван туулж чадах маш энгийн жишээг олж авна: 15 + 10. Тооцоолсны дараа бид хариуг авна: хорин тав. Өөрөөр хэлбэл хорин таван арга зам бийөнөөдрийн жижүүрийн анги оноо.
Үржүүлэх дүрэм
Үржүүлэх дүрэм нь комбинаторикийн үндсэн томъёонд мөн хамаарна. Онолоос эхэлье. Бид хэд хэдэн үйлдлийг хийх шаардлагатай гэж бодъё (a): эхний үйлдэл нь 1 аргаар, хоёр дахь нь 2 аргаар, гурав дахь нь 3 аргаар, гэх мэт сүүлчийн а-үйлдэл нь sa арга замаар гүйцэтгэгдэнэ. Дараа нь эдгээр бүх үйлдлүүдийг (бидний нийлбэр нь) N аргаар хийж болно. Үл мэдэгдэх N-ийг хэрхэн тооцоолох вэ? Томъёо нь үүнд тусална: N \u003d c1c2c3…ca.
Дахин хэлэхэд онолын хувьд тодорхой зүйл байхгүй тул үржүүлэх дүрмийг хэрэглэх энгийн жишээ рүү шилжье. Арван таван охин, арван хөвгүүн сурдаг хорин таван хүнтэй нэг ангиа авъя. Зөвхөн энэ удаад бид хоёр үйлчлэгч сонгох хэрэгтэй. Тэд зөвхөн охид, хөвгүүд эсвэл охинтой хүү байж болно. Бид асуудлын үндсэн шийдэл рүү ханддаг. Бид эхний үйлчлэгчийг сонгохдоо сүүлчийн догол мөрөнд шийдсэний дагуу бид хорин таван боломжит хувилбаруудыг авах болно. Хоёр дахь жижүүр нь үлдсэн хүмүүсийн аль нь ч байж болно. Бид хорин таван оюутантай байсан, нэгийг нь сонгосон, энэ нь үлдсэн хорин дөрвөн хүний аль нь ч хоёрдугаар жижүүр байж болно гэсэн үг юм. Эцэст нь бид үржүүлэх дүрмийг хэрэглэж, хоёр үйлчлэгчийг зургаан зуун аргаар сонгох боломжтой болохыг олж мэдэв. Бид хорин тав, хорин дөрөвийг үржүүлснээр энэ тоог авсан.
Солих
Одоо бид өөр нэг комбинаторик томъёог авч үзэх болно. Өгүүллийн энэ хэсэгт бидСэлгээний талаар ярилцъя. Асуудлыг нэн даруй жишээгээр авч үзье. Бильярдын бөмбөг авъя, бидэнд n-р тоо байна. Бид тооцоолох хэрэгтэй: тэдгээрийг дараалан байрлуулах, өөрөөр хэлбэл захиалгат багц хийх хичнээн олон сонголт байна.
Эхлүүлье, хэрэв бидэнд бөмбөг байхгүй бол байрлуулах сонголт ч байхгүй. Хэрэв бид нэг бөмбөгтэй бол зохион байгуулалт нь ижил байна (математикийн хувьд үүнийг дараах байдлаар бичиж болно: Р1=1). Хоёр бөмбөгийг хоёр янзаар байрлуулж болно: 1, 2 ба 2, 1. Тиймээс Р2=2. Гурван бөмбөгийг зургаан янзаар байрлуулж болно (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Хэрэв ийм бөмбөг гурав биш, харин арав, арван таван байх уу? Бүх боломжит хувилбаруудыг жагсаах нь маш урт бөгөөд дараа нь комбинаторикууд бидэнд туслах болно. Сэлгээний томъёо нь бидний асуултын хариултыг олоход тусална. Pn=nP(n-1). Хэрэв бид томъёог хялбарчлахыг оролдвол: Pn=n (n - 1) … 21. Энэ нь анхны натурал тоонуудын үржвэр юм. Ийм тоог факториал гэж нэрлэх ба n гэж тэмдэглэнэ!
Асуудлыг авч үзье. Удирдагч өглөө бүр отрядаа нэг эгнээнд (хорин хүн) барьдаг. Отрядд гурван сайн найз байдаг - Костя, Саша, Леша. Тэд бие биенийхээ хажууд байх магадлал хэд вэ? Асуултын хариултыг олохын тулд та "сайн" үр дүн гарах магадлалыг нийт үр дүнгийн тоонд хуваах хэрэгтэй. Сэлгээний нийт тоо 20 байна!=2.5 квинтиллон. "Сайн" үр дүнгийн тоог хэрхэн тоолох вэ? Костя, Саша, Леша нар нэг супермэн гэж бодъё. Дараа нь бидМанайд ердөө арван найман хичээл бий. Энэ тохиолдолд солих тоо 18=6.5 квадриллион байна. Энэ бүхний тусламжтайгаар Костя, Саша, Леша нар хоорондоо хуваагдашгүй гурвалсан байдлаар дур зоргоороо хөдөлж чаддаг бөгөөд энэ нь дахиад 3 юм!=6 сонголт. Тиймээс бидэнд нийт 18 "сайн" одны орд бий!3! Бид зүгээр л хүссэн магадлалаа олох хэрэгтэй: (18!3!) / 20! Энэ нь ойролцоогоор 0.016. Хэрэв хувь болгон хөрвүүлбэл ердөө 1.6% болж хувирна.
Байр
Одоо бид өөр нэг маш чухал бөгөөд шаардлагатай комбинаторик томъёог авч үзэх болно. Орон байр бол бидний дараагийн асуудал бөгөөд нийтлэлийн энэ хэсэгт авч үзэхийг танд санал болгож байна. Бид илүү төвөгтэй байх болно. Бид зөвхөн бүхэл бүтэн багцаас (n) биш, харин жижиг (m) -ээс боломжит сэлгэлтийг авч үзэхийг хүсч байна гэж бодъё. Өөрөөр хэлбэл, бид n зүйлийн сэлгэлтийг m-ээр авч үзнэ.
Комбинаторикийн үндсэн томьёог зүгээр нэг цээжлэх биш, ойлгох хэрэгтэй. Хэдийгээр бид нэг параметр биш, харин хоёр параметртэй тул тэд илүү төвөгтэй болж байна. m \u003d 1, дараа нь A \u003d 1, m \u003d 2, дараа нь A \u003d n(n - 1) гэж бодъё. Хэрэв бид томъёог илүү хялбарчилж, факториал ашиглан тэмдэглэгээ рүү шилжих юм бол бид маш товч томъёог авна: A \u003d n! / (n - м)!
Хослол
Бид комбинаторикийн бараг бүх үндсэн томъёог жишээн дээр авч үзсэн. Одоо комбинаторикийн үндсэн хичээлийг авч үзэх эцсийн шат руу шилжье - хослолтой танилцах. Одоо бид байгаа n зүйлээс m зүйлийг сонгох ба бүгдийг нь боломжит бүх аргаар сонгох болно. Энэ нь орон байрнаас юугаараа ялгаатай вэ? Бид тэгэхгүйдарааллыг анхаарч үзээрэй. Энэхүү эрэмбэлэгдээгүй багц хослол байх болно.
Тэмдэглэгээг нэн даруй танилцуулна уу: C. Бид n-ээс m бөмбөгийг байрлуулна. Бид захиалгад анхаарлаа хандуулахаа больж, давтагдах хослолуудыг авдаг. Хослолын тоог авахын тулд бид байршуулах тоог m-ээр хуваах хэрэгтэй! (м хүчин зүйл). Энэ нь C \u003d A / m! Тиймээс, бараг бүх зүйлийг хэдэн бөмбөг сонгохтой тэнцүү n бөмбөгийг сонгох хэд хэдэн арга байдаг. Үүний логик илэрхийлэл байдаг: бага зэрэг сонгох нь бараг бүх зүйлийг хаяхтай адил юм. Зүйлүүдийн тэн хагасыг сонгохыг оролдох үед хамгийн их тооны хослолд хүрэх боломжтой гэдгийг энд дурдах нь зүйтэй.
Асуудлыг шийдэх томъёог хэрхэн сонгох вэ?
Бид комбинаторикийн үндсэн томъёог нарийвчлан судалсан: байршил, сэлгэлт, хослол. Одоо бидний даалгавар бол комбинаторикт асуудлыг шийдвэрлэхэд шаардлагатай томьёог сонгоход хялбар болгох явдал юм. Та дараах энгийн схемийг ашиглаж болно:
- Өөрөөсөө асуугаарай: асуудлын текстэд элементүүдийн дарааллыг харгалзан үзсэн үү?
- Хэрэв хариулт нь үгүй бол хослолын томъёог ашиглана уу (C=n! / (m!(n - m)!)).
- Хэрэв хариулт нь үгүй бол та өөр нэг асуултанд хариулах хэрэгтэй: бүх элементүүд хослолд орсон уу?
- Хэрэв хариулт нь тийм бол солих томъёог ашиглана уу (P=n!).
- Хэрэв хариулт нь үгүй бол хуваарилалтын томъёог ашиглана уу (A=n! / (n - m)!).
Жишээ
Бид комбинаторикийн элементүүд, томьёо болон бусад зарим асуудлыг авч үзсэн. Одоо цаашаа явцгааябодит асуудлыг авч үзэх. Таны өмнө киви, жүрж, банана байна гэж төсөөлөөд үз дээ.
Асуулт нэг: Тэдгээрийг хэдэн аргаар дахин зохион байгуулж болох вэ? Үүнийг хийхийн тулд бид солих томъёог ашиглана: P=3!=6 арга.
Асуулт хоёр: нэг жимсийг хэдэн аргаар сонгох вэ? Энэ нь ойлгомжтой, бидэнд зөвхөн гурван сонголт байгаа - киви, жүрж эсвэл гадил жимсийг сонгох, гэхдээ бид хослолын томъёог ашигладаг: C \u003d 3! / (2!1!)=3.
Асуулт гурав: Хоёр жимсийг хэдэн аргаар сонгох вэ? Бидэнд ямар сонголт байна вэ? киви ба жүрж; киви ба банана; жүрж, банана. Энэ нь гурван сонголт, гэхдээ үүнийг хослолын томъёогоор шалгахад хялбар байдаг: C \u003d 3! / (1!2!)=3
Асуулт дөрөв: Гурван жимсийг хэдэн аргаар сонгох вэ? Таны харж байгаагаар гурван жимс сонгох цорын ганц арга зам байдаг: киви, жүрж, банана. C=3! / (0!3!)=1.
Асуулт тав: Та ядаж нэг жимсийг хэдэн янзаар сонгож болох вэ? Энэ нөхцөл нь бид нэг, хоёр эсвэл гурван жимсийг авч болно гэсэн үг юм. Тиймээс бид C1 + C2 + C3=3 + 3 + 1=7-г нэмнэ. Өөрөөр хэлбэл, ширээн дээрээс ядаж нэг жимс авах долоон арга бий.
