Комбинаторик ба магадлалын онолын элементүүдийг бий болгох гол урьдчилсан нөхцөл нь хүмүүс сугалаа, шоо, хөзөр болон бусад азын тоглоомд донтох явдал байсан гэж тэд хэлдэг. Эрт дээр үед мөрийтэй тоглоом маш чухал байсан. Зарим нь эд хөрөнгө, газар нутаг, эхнэр авсан. Бусад нь сүүлийн цамц хүртэл өөрт байгаа бүхнээ алдсан. Үнэхээр эрсдэлтэй тоглоомууд эсвэл санамсаргүй тоглоомуудын нөлөөлөл гарсан. Гэсэн хэдий ч шинжлэх ухааны хурдацтай хөгжил зэрэг илүү үндсэн шалтгаанууд байсан: туршилт, цуврал туршилтын явцыг урьдчилан таамаглах, үр дүнгийн алдааг үнэлэх хэрэгцээ. Энэ бүхэн болон бусад олон зүйл нь комбинаторик ба магадлалын онолын элементүүдийг бий болгоход хүргэсэн.
Бернуллийн теорем
Комбинаторик нь 17-р зуунд Кардано, Паскаль, Галилео, Ферма, Лейбниц, Бернулли зэрэг эрдэмтдийн бүтээлийн ачаар үүссэн гэж үздэг. Тэд л тодорхой нэр томъёог нэвтрүүлсэнЭнэ шинжлэх ухааны хувьд хэд хэдэн үндсэн хуулиуд болон комбинаторикийн анхны томьёог нотолсон. Жишээлбэл, Бернуллигийн теорем нь зөвхөн бие биенээсээ хамааралгүй, ижил нөхцөлд хэдэн ч удаа давтагдах боломжтой санамсаргүй туршилт, туршилтуудыг авч үзэх нь зүйтэй юм. Энэхүү теорем нь комбинаторик ба магадлалын онолын цаашдын хөгжлийг шинжлэх ухаан болгон тодорхойлсон гэж нийтээр хүлээн зөвшөөрдөг.
Давтамжийн тогтвортой байдал
Комбинаторикийн элементүүдийн судалгаанд шилжихээсээ өмнө шоо шидэх гэх мэт тодорхой бодлыг санал болгодог тодорхой жишээг хэлье. Энгийн байхын тулд нэг ясыг авч үзье. Энэ бол тал бүр нь дугаарлагдсан зургаан талт шоо юм. Хэрэв бид n шидэлтийн цуврал туршилтыг хийж Г1 нь 1-р тоотой ирмэгийн дуслын тоо гэж үзвэл Г2 - 2 дугаартай гэх мэт шидэлтийн тоо нэмэгдэхэд n давтамж Г1/n, Г2 Туршилтын эхэнд санамсаргүй мэт санагдах /n, …, Г 6/n нь нэлээд тодорхой утгыг олж авдаг. Мөн тэнцвэртэй шоо хийхэд тал бүрийн давтамж маш нарийвчлалтай тэнцүү байх болно.
Өөр нэг жишээ бол зоосны туршилт юм. Тиймээс эрдэмтэн Пирсон 24,000 зоос шидсэний дараа зоосны аль нэг талаас унах давтамж 0.5-д ойртох тусам илүү нарийвчлалтай, илүү их шидэлт хийдэг гэсэн дүгнэлтэд хүрчээ. Ийнхүү тэрээр төрийн сүлд алдагдах магадлалыг 0.5005 болгожээ. Энэ зарчимдавтамжийн тогтвортой байдал нь мөн онолын нэг үндэс юм.
Түүхэн тэмдэглэл
Магадлалын онол, комбинаторикийг 20-р зуунд хамгийн идэвхтэй хөгжүүлсэн. Энэ асуудалд Орос, Зөвлөлтийн математикчид асар их хувь нэмэр оруулсан. Тэдний дунд, жишээлбэл, Колмогоров, Чебышев, Ляпунов, Марков. Тэд хэрэглэх талбарыг ихээхэн өргөжүүлж, их тооны хууль, төв хязгаарын теорем, магадлалын онолын аксиоматикийг судалж, тайлбарласан. Энэ бүхэн нь бүхэл бүтэн шинжлэх ухааны үндэс суурь болсон. Өнөөдөр физик, хими, биологи болон бусад олон салбарт, ялангуяа тэдгээрийн практик талбарт комбинаторик ба магадлалын онолын элементүүдийн ач холбогдлыг хэт үнэлэхэд хэцүү байна.
Комбинаторик бодлогуудын жишээ
Комбинаторик гэдэг нь тодорхой нөхцлийн дагуу аливаа багц элементээс бүрдэх боломжит хослолуудын тоог тооцоолох явдал юм. Үүний тулд шаардлагатай асуудлыг хялбар, хурдан шийдвэрлэх боломжийг олгодог комбинаторик томъёог гаргаж авсан. Гэхдээ эдгээр томьёог харуулахын өмнө тэдгээрт хүргэсэн асуултуудын жишээг харцгаая.
Даалгавар 1. Дэлхийн аварга шалгаруулах тэмцээний плей-оффын шатанд 16 баг оролцоно. Тэд өөр хоорондоо хэдэн аргаар байр хуваарилах боломжтой вэ? Жишээ нь:
- (3, 1, 2, 4..16) - 3-р баг 1-р байр, 1-р баг 2-р байр гэх мэт.
- (16, 1, 2, 3, 4..15) - 16-р баг эхний байранд, …
- (1..7, 9, 8, 10..16) - багийн эхний байруудад 1, 2, 3, …
Эдгээр нь бүгд сонголтын жишээ юм. Энэ асуудлыг шийдэх тодорхой шийдэл бол бүгдийг бичих явдал юмболомжит хослолууд. Гэсэн хэдий ч, энэ нь маш их цаг хугацаа шаардах болно, учир нь тэдгээрийн тоо нь 16 цифрийг дахин байрлуулах арга замуудтай адил байх болно. Комбинаторикийн элементүүд иймэрхүү жишээг хурдан шийддэг.
Асуудал 2. Эдгээр 16 багаас гурав нь л шагнал авах боломжтой. Ялагчдыг хэдэн аргаар тодруулах вэ? Энэ тохиолдолд чансаа ямар байх, эцсийн шатанд шалгарсан хүмүүсийн дараалал ямар байх нь огт хамаагүй байдгаараа өмнөх даалгавараас ялгаатай. Үнэхээр бүх багуудын дунд шагналын төлөө өрсөлдөх гурвыг л олох нь чухал юм. Өөрөөр хэлбэл, багцууд нь {3, 2, 1}, {5, 12, 7}, {8, 1, 2} гэх мэт харагдаж болно.
Асуудал 3. Асуултыг арай өөрөөр тавьбал яах вэ: плей-оффт оролцож буй 16 багийн медалийг хэрхэн хуваарилах вэ? Хоёр дахь даалгаврын ялгаа нь бүрэн тодорхой биш байж магадгүй юм. Гэхдээ одоо бид шагналын төлөө өрсөлдөх гурван багийг сонгоод зогсохгүй аль нь ямар байр эзлэхийг тодорхойлох ёстой. Өөрөөр хэлбэл, хоёр дахь даалгаврын хувьд, жишээлбэл, багц (5, 12, 1) ба (1, 12, 5) тэнцүү байсан бол одоо командын дараалал жинтэй болсон. Үнэхээр эхний тохиолдолд 5-р баг алт, хоёр дахь тохиолдолд 1-р баг авах болно.
Доор бид даалгавар тус бүрийг комбинаторикийн аль хэсэгт хамаарахыг авч үзэж, тэдгээрийг хэрхэн шийдвэрлэх талаар дэлгэрэнгүй тайлбарлах болно. Энэ хооронд та тавьсан асуултынхаа талаар бие даан бодохыг оролдож болно.
Захиалга харгалзахгүйгээр хослол эсвэл хослол
Ердөө n ширхэг элементийн хослолk нь 1-ээс n хүртэлх утгыг авч болох k-хэсэг элементийн багц нь n ширхэг элементээс сонгосон k элементийн дурын хослол юм. Энэ тохиолдолд хоёр олонлогийн аль нэг нь n-ээс ямар нэгэн элемент агуулж байгаа боловч хоёрдугаарт хамаарахгүй бол хоёр олонлогийг өөр гэж үзнэ. Өөрөөр хэлбэл, тэдгээр нь зөвхөн найрлагаараа ялгаатай. Комбинаторикийн элементүүдэд хослолууд нь анхан шатны суурь болдог.
N-ээс k хүртэлх хослолын тоог C k гэж англи хэлний Combination гэдэг үгээр тэмдэглэнэ. C 1=n ба C =1 гэсэн хэллэгүүд нь нэлээд юм. Мэдээжийн хэрэг, n элементээс нэг нэгээр нь сонгоход ердөө n сонголт байдаг (элементүүдтэй ижил тоо) ба үүний дагуу n ширхэг элементийн багцыг зөвхөн нэг л болгож болно.
Тиймээс жишээ нь {e, 2, a} гурван элементийн багцыг авч үзье. Түүний хувьд C31=3: {a}, {2}, {е}; C32=3: {e, 2}, {2, a}, {a, e}; эцэст нь C33=1: {e, 2, a}. Энэ тохиолдолд багц дахь элементүүдийн дараалал хамаагүй гэдгийг санаарай.
Та C 0 гэж юу болохыг олох гэж оролдвол юу болох вэ?
Захиалгад тулгуурлан байршуулах эсвэл хослуулах
Байршуулах комбинаторикийг ойлгоход хангалттай. Эдгээр нь ижил хослолууд бөгөөд одоо зөвхөн найрлагыг төдийгүй хослол бүрийн дарааллыг харгалзан үздэг. Тиймээс, n ширхэг элементийг k ширхэгийн хослолд (иж бүрдэл) байрлуулснаар k нь 1-ээс n хүртэлх утгыг авч болно.тодорхой дарааллаар байрлуулсан n-ээс k-хэсэг элементээс бүрдэх дурын хослол гэж нэрлэдэг. Өөрөөр хэлбэл, хоёр байршлын хослол гурван тохиолдолд өөр байна:
- тэдгээр нь найрлагын хувьд ялгаатай;
- тэдгээр нь олонлог дахь элементүүдийн дарааллаар ялгаатай;
- тэдгээр нь найрлага, дарааллаар нь ялгаатай.
n-ээс k хүртэлх байршлын тоог Зохицуулалтаас A k гэж тэмдэглэв. {x, e, z} гурван элементийн олонлогийн байршлын бүх сонголтыг авч үзье:
- A31=3: (x), (e), (z);
- A32=6: (x, e), (e, x), (x, z), (z), x), (e, z), (z, e);
- A33=6: (x, e, z), (e, x, z), (z, x, e), (x, z, e), (e, z, x), (z, e, x).
Сүүлийн мөр A33 онцгой анхаарал хандуулах ёстой. Эдгээр нь орлуулахаас өөр зүйл биш.
Хувилбарууд
Дээр дурьдсанчлан солих нь утгын хувьд маш энгийн. Эдгээр нь ердөө л n элемент, тус бүр нь n байх болно. Өөрөөр хэлбэл, бид элементүүдийн дарааллаар ялгаатай бүх хослолыг сонирхож байгаа бөгөөд зөвхөн тэдгээрийн дотор л байдаг. Эсвэл A . Сэлгээний тоог Permutation гэдэг үгийн P үсгээр тэмдэглэнэ. Комбинаторикийн элементүүдэд сэлгэлтийг зөвхөн нэг индексээр хангадаг. Жишээлбэл, P3=6 гэдгийг бид өмнөх бүлгээс олж мэдсэн.
Олонлогийн онолын хослолууд
Таны мэдэж байгаачлан математикт тодорхой бус биетүүдтэй харилцах нь хэцүү байдаг: олонлог, хослол гэх мэт. Энэ нь сайхан байх болно. Бид юутай харьцаж байгааг математикийн хувьд нарийн тодорхойл. Энд олонлогийн онолын хэл хэрэг болно. Комбинаторикийн элементүүд юу болохыг олонлогын онолын хэлээр тодорхойлъё.
Зарим n олонлогийг өгье A={a1, a2, …, a }, энэ нь n ширхэг элемент агуулдаг. n олонлогоос түүний k-дэд олонлогийг тодорхойлоход хялбар бөгөөд k нь n-ээс бага эсвэл тэнцүү байна. Дараа нь n-ээс k хүртэлх хослолыг n олонлогийн бүх дэд олонлог k гэж нэрлэнэ. Энэхүү тодорхойлолтын ачаар C 0 оруулга ямар байх вэ гэсэн асуултад хариулахад хялбар байдаг. Олонлогийн онолд хоосон олонлог нь аль ч дэд олонлогт агуулагддаг тул C 0=1. Өөрөөр хэлбэл, энэ нь нэгийг агуулсан хослол байх болно. элемент - хоосон багц.
Тиймээс, {c, b, a} гурван элементийн олонлогийг судалснаар бид C 0 =1: { }; C31=3: {a}, {b}, {c}; C32=3: {a, b}, {b, c}, {c, a}; эцэст нь C33=1: {a, b, c}.
Үүний дагуу тэдгээрийг байрлуулах комбинаторик дээр ижил аргаар тодорхойлно. Цорын ганц ялгаа нь n олонлогоос дараалсан k-дэд олонлогуудыг сонгох хэрэгтэй. Мөн бүх дэд олонлогууд нь хоосон багцыг агуулна. Энэ нь нөхцөлт байдлаар 0 ширхэг n элементийн дараалсан хослол гэж тооцогддог, өөрөөр хэлбэл. A 0=1.
Тодорхой бус хийцээс олонлогийн онолоор тодорхой тодорхойлсон объект руу шилжсэний улмаас нэг асуултад хариулах нь тун улиг болсон юм.үүссэн асуултууд. Энэ бол бүх математик.
Нэмэх зарчим
Энэ бол комбинаторикийн хоёр үндсэн дүрмийн нэг юм. Москва хотод А цэгээс В цэг хүртэл 5 автобус, 3 трамвай, 1 метроны галт тэргээр хүрч болно. Зөв газартаа хүрэх 5 + 3 + 1=9 арга байгаа нь харагдаж байна. Энэ бол нэмэхийн хослолын зарчим юм.
Хэрэв аливаа асуудлыг авч үзэхдээ n аргаар шийдвэрлэх боломжтой бол эдгээр аргуудын эхнийх нь m1 удаа, хоёр дахь нь - m 2удаа гэх мэт, тэгвэл энэ асуудал шийдэгдэх болно m1 + m2 + … + mарга.
Үржүүлэх зарчим
Одоо та Москвагаас Казань хүртэл Нижний Новгородоор дамжин явах хэрэгтэй гэж төсөөлье. Үүний зэрэгцээ Москва, Нижний Новгород хотыг 2 галт тэрэг, 3 нислэг, 10 машин, Нижний Новгород, Казань хотыг 1 галт тэрэг, 1 нислэг, 2 автобусаар холбодог. Нэмэлт зарчмаар бид Москвагаас Нижний Новгород, тэндээс Казань хүртэл 13 арга зам байдаг гэсэн дүгнэлтэд хүрч байна - 4. Москва, Казань хотыг холбосон нийт замын тоо: 134=52 байна..
Тиймээс үржүүлгийн хослолын зарчим дараах байдалтай байна. Хэрэв асуудлыг n үе шаттайгаар шийдсэн бол эхний шатанд m1, хоёр дахь шатанд m2 гэх мэт., хамт Энэ тохиолдолд эдгээр дараалсан үе шатууд нь бие даасан байдаг, өөрөөр хэлбэл өмнөх үе шатуудад хэрхэн шийдвэр гаргаснаас хамааран аргын тоо өөрчлөгддөггүй, дараа нь асуудлыг шийддэг m1 m2 …m арга замууд. Хэрэв алхмуудад дор хаяж нэг ялгаа байгаа бол хоёр шийдлийг өөр гэж үзнэ.
Үндсэн томьёо
Томъёонуудыг нэн даруй үзүүлье, дараа нь тэд хаанаас ирснийг товч тайлбарлаж, комбинаторикийн эдгээр элементүүдийг ашиглан өмнө тайлбарласан жишээнүүдийг шийдье.
Байр. Бусад нь үүнтэй холбоотой учраас бид энэ томъёогоор эхэлдэг
| A k= | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1)= | n! |
| (n-k)! |
Өөрчлөлт
| P= | A = | n(n-1)(n-2)(n-3)(n-4)(n-5)…4321= | n! |
Хослол
| C k= | A k | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1) | n! |
| k! | k! | k!(n-k)! |
Эдгээр томъёоны нотолгоо нь комбинаторикийн элементүүдийн зарчмууд - нэмэх ба үржүүлэх дүрэм дээр суурилдаг. Байршлын тоог олох эхний томъёог авч үзье. Эхний шатанд бид n ширхэг элементийн аль нэгийг авах ба үүнийг хийх n арга байна. Хоёрдахь шатанд бид n-1 элемент, үүний дагуу n-1 сонголттой үлдэнэ. Гурав дахь нь - n-3 арга замууд. Бидний олонлогт k ширхэг элемент үлдэх хүртэл бид үүнийг үргэлжлүүлнэ. Үржүүлэх дүрмийн дагуу бид нийтдээ n (n-1) (n-2) (n-3) (n-4) (n-5) … (n-k + 1) байх болно.) k элементийг сонгох арга. Сэлгээг олох хоёр дахь томъёо нь эхнийх нь энгийн үр дагавар юм.орлуулах тоо m=k. n элементийн хослолыг хайхдаа k харах болгонд k ширхэг байна гэсэн бодлыг харгалзан нэгдлүүдийн тоог гаргаж өгсөн сүүлчийн томъёог гаргажээ. n-ээс k хүртэлх зохицуулалтууд (тэдгээрийг k элементийн сэлгэн шилжүүлэлт хэлбэрээр авдаг). Тиймээс бидэнд A k=C kk байна!.
Одоо бид өмнө нь зарласан ажлууд руу буцаж очоод сонголтуудын тоог үнэлэх боломжтой. Эхний асуудлын хувьд бид солих томьёог ашиглах хэрэгтэй, өөрөөр хэлбэл P16=16!=20 922 789 888 000 ≈ 211012 16 багийг чансаанд хэрхэн оруулах боломжтой хувилбарууд. Хоёр дахь асуудал нь хослолуудтай холбоотой бөгөөд энэ нь C163=16 гэсэн үг! / [3!(16-3)!]=560 ялагч. Эцэст нь хэлэхэд, сүүлийн асуудал нь байршуулалттай холбоотой, жишээлбэл A163=16! / (16-3)!=16 багийн 3 баг шагналаа хуваалцах 3360 арга.
Дээрх зүйлийг харгалзан үзвэл их тооны комбинаторик хэрхэн ажилладаг талаар ярих нь илүүц байх болно.
