Өгөгдсөн багцаас дээжийн тоог ерөнхий хэлбэрээр тоолох асуудлыг авч үзье. Цөөн хэдэн багц байгаасай Н, бүрдэнэ n элементүүд. -аас бүрдэх аливаа дэд олонлог м элементүүдийг тэдгээрийн дарааллыг харгалзахгүйгээр, эсвэл үүнийг харгалзан үзэхгүйгээр авч үзэж болно, i.e. дарааллыг өөрчлөх үед өөр рүү шилжих м- дээж авах.
Дараахь тодорхойлолтуудыг томъёолъё.
Дахин давтагдахгүйгээр байршуулах
Дахин давталгүйгээр байрлуулахn элементүүдм Нагуулсанмянз бүрийн элементүүд.
Тодорхойлолтоос харахад энэ хоёр зохицуулалт нь элементүүд нь ижил байсан ч элемент болон дарааллаар нь бие биенээсээ ялгаатай байдаг.
Теорем 3. Дахин давтагдахгүйгээр байрлуулах тоо нь бүтээгдэхүүнтэй тэнцүү байна м хүчин зүйлүүдийн хамгийн том нь тоо юм n . Бичнэ үү:
Дахин давтагдахгүйгээр солих
-аас солихn элементүүдийг олонлогийн янз бүрийн дараалал гэж нэрлэдэгН.
Энэхүү тодорхойлолтоос үзэхэд хоёр сэлгэн залгалт нь зөвхөн элементүүдийн дарааллаар ялгаатай бөгөөд тэдгээрийг байрлуулах тусгай тохиолдол гэж үзэж болно.
Теорем 4. Дахин давтагдахгүйгээр өөр өөр орлуулах тоог томъёогоор тооцоолно
Давталтгүй хослолууд
Дахин давтагдахгүй хослолn элементүүдм олонлогийн ямар ч эрэмбэлэгдээгүй дэд олонлогууд гэж нэрлэдэгНагуулсанм янз бүрийн элементүүд.
Тодорхойлолтоос харахад хоёр хослол нь зөвхөн элементүүдээр ялгаатай, дараалал нь чухал биш юм.
Теорем 5. Дахин давтагдахгүй хослолын тоог дараах томъёоны аль нэгийг ашиглан тооцоолно.
Жишээ 1. Өрөөнд 5 сандал байна. Та тэдгээрийг хэдэн аргаар байрлуулж болох вэ?
a) 7 хүн; б) 5 хүн; в) 3 хүн?
Шийдэл: a) Юуны өмнө та сандал дээр суух 7 хүнээс 5 хүнийг сонгох хэрэгтэй. Үүнийг хийж болно 
арга зам. Тодорхой тавыг сонгох бүрт та үйлдвэрлэж болно 
дахин зохицуулалтууд. Үржүүлэх теоремын дагуу буух аргын шаардлагатай тоо тэнцүү байна.
Сэтгэгдэл:Асуудлыг зөвхөн бүтээгдэхүүний теоремыг ашиглан шийдэж болно: 1-р сандал дээр суухад 7, 2-р сандал дээр 6, 3-т -5, 4-т -4, 5-д суух боломжтой. -3. Тэгвэл 5 сандал дээр 7 хүн суулгах аргын тоо . Хоёр аргын шийдэл нь нийцэж байгаа тул
б) Шийдэл нь ойлгомжтой - 
V) 
- эзэлсэн дарга нарын сонгуулийн тоо.
- сонгосон гурван сандал дээрх гурван хүний суудлын тоо.
Нийт сонгуулийн тоо .
Томьёог шалгах нь тийм ч хэцүү биш юм 
;
;
-аас бүрдэх олонлогийн бүх дэд олонлогуудын тоо nэлементүүд.
Байршлыг давтах
-аас давталттайгаар байрлуулах замаарn элементүүдм олонлогийн эрэмбэлэгдсэн дэд олонлог бүрийг дууднаН, бүрдэнэм Энэ дэд олонлогт 1-ээс аль ч элементийг оруулах боломжтоймудаа, эсвэл бүрмөсөн байхгүй байх.
Дахин давтагдах байршлын тоог дараах байдлаар тэмдэглэв 
үржүүлэх теоремын үр дагавар болох томъёог ашиглан тооцоолно.
Жишээ 2. N = (a, b, c) гурван үсгийн олонлог байг. Энэ багцад багтсан бүх үсгийг үг гэж нэрлэе. Эдгээр үсгүүдээс хийж болох 2 урттай үгсийн тоог ол: 
.
Сэтгэгдэл:Мэдээжийн хэрэг, давталттай байршуулалтыг хэзээ гэж үзэж болно 
.
Жишээ 3. Та (a, b) үсгүүдийг ашиглан урттай бүх боломжит үгсийг үүсгэх хэрэгтэй 3. Үүнийг хэдэн аргаар хийж болох вэ?
Хариулт:
Комбинаторик бол дээд математикийн бие даасан салбар (тэрверийн нэг хэсэг биш) бөгөөд энэ чиглэлээр нэлээд жинтэй сурах бичгүүдийг бичсэн бөгөөд агуулга нь заримдаа хийсвэр алгебраас хялбар байдаггүй гэдгийг тэмдэглэх нь зүйтэй. Гэсэн хэдий ч онолын мэдлэгийн багахан хэсэг нь бидэнд хангалттай байх бөгөөд энэ нийтлэлд би сэдвийн үндсийг ердийн комбинаторын асуудлуудтай хялбар хэлбэрээр шинжлэхийг хичээх болно. Та нарын ихэнх нь надад туслах болно ;-)
Бид юу хийх гэж байна? Нарийн утгаараа комбинаторик гэдэг нь тодорхой багцаас хийж болох янз бүрийн хослолуудын тооцоо юм. салангидобъектууд. Объектууд нь хүн, амьтан, мөөг, ургамал, шавьж гэх мэт тусгаарлагдсан объект эсвэл амьд биетийг ойлгодог. Үүний зэрэгцээ, иж бүрдэл нь манна будаа, гагнуурын төмөр, намаг мэлхий зэргээс бүрдэхийг комбинаторик огт тоодоггүй. Эдгээр объектуудыг тоолж болох нь үндсэндээ чухал юм - тэдгээрийн гурав нь байдаг (салангид байдал)Хамгийн гол нь тэдний аль нь ч адилхан биш юм.
Бид одоо хослолуудын талаар маш их зүйлийг авч үзсэн. Хослолын хамгийн түгээмэл хэлбэрүүд нь объектуудын сэлгэлт, тэдгээрийг багцаас сонгох (хослол) ба хуваарилалт (байршил) юм. Энэ нь яг одоо хэрхэн болж байгааг харцгаая:
Дахин давтагдахгүйгээр сэлгэлт, хослол, байршуулалт
Тодорхой бус нэр томъёоноос бүү ай, ялангуяа тэдний зарим нь тийм ч сайн биш байдаг. Гарчгийн сүүлээс эхэлье - юу хийдэг вэ? давталт байхгүй"? Энэ нь энэ хэсэгт бид бүрдсэн багцуудыг авч үзэх болно гэсэн үг юм янз бүрийнобъектууд. Жишээ нь, ... үгүй ээ, би гагнуур, мэлхийтэй будаа өгөхгүй, илүү амттай зүйл байсан нь дээр байх болно =) Алим, лийр, гадил жимсний урд талын ширээн дээр болсон гэж төсөөлөөд үз дээ ( Хэрэв танд байгаа бол нөхцөл байдлыг бодит байдалд дуурайж болно). Бид жимсээ зүүнээс баруун тийш дараах дарааллаар байрлуулна.
алим / лийр / банана
Асуулт нэг: Тэдгээрийг хэдэн аргаар дахин зохион байгуулж болох вэ?
Нэг хослолыг дээр аль хэдийн бичсэн байгаа бөгөөд бусадтай холбоотой ямар ч асуудал байхгүй:
алим / банана / лийр
лийр / алим / банана
лийр / банана / алим
гадил / алим / лийр
гадил / лийр / алим
Нийт: 6 хослол эсвэл 6 орлуулалт.
За, боломжтой бүх тохиолдлыг жагсаахад хэцүү байсангүй, гэхдээ илүү олон объект байвал яах вэ? Дөрвөн өөр жимстэй бол хослолын тоо мэдэгдэхүйц нэмэгдэх болно!
Лавлах материалыг нээнэ үү (гарын авлагыг хэвлэхэд тохиромжтой) 2-р цэгт сэлгэлтийн тооны томьёог ол.
Ямар ч төвөг учруулахгүй - 3 объектыг янз бүрийн аргаар дахин зохион байгуулж болно.
Хоёр дахь асуулт: Та a) нэг жимс, б) хоёр жимс, в) гурван жимс, г) ядаж нэг жимс сонгох боломжтой вэ?
Яагаад сонгох вэ? Тиймээс бид өмнөх цэг дээр хоолны дуршилыг нэмэгдүүлсэн - идэхийн тулд! =)
a) Нэг жимсийг гурван аргаар сонгож болно - алим, лийр, гадил жимсний аль нэгийг авна. Албан ёсны тооцоог заасны дагуу хийж байна хослолын тооны томъёо:
Энэ тохиолдолд оруулгыг дараах байдлаар ойлгох ёстой: "Та гурваас 1 жимсийг хэдэн аргаар сонгож болох вэ?"
б) Хоёр жимсний боломжит бүх хослолыг жагсаая.
алим, лийр;
алим ба гадил жимсний;
лийр ба банана.
Хослолын тоог ижил томъёог ашиглан хялбархан шалгаж болно.
Бичлэгийг үүнтэй төстэй байдлаар ойлгож байна: "Та гурваас 2 жимсийг хэдэн аргаар сонгож болох вэ?"
в) Эцэст нь гурван жимс сонгох ганцхан арга бий:
Дашрамд хэлэхэд, хослолын тооны томъёо нь хоосон дээжийн хувьд утга учиртай хэвээр байна.
Ийм байдлаар та ганц ч жимс сонгох боломжгүй - үнэндээ юу ч авахгүй, тэгээд л болоо.
г) Та хэдэн аргаар авч болох вэ? ядаж нэгжимс? "Ядаж нэг" гэсэн нөхцөл нь бид 1 жимс (ямар ч) эсвэл 2 жимс эсвэл бүх 3 жимсэнд сэтгэл хангалуун байна гэсэн үг юм.
Эдгээр аргуудыг ашиглан та дор хаяж нэг жимс сонгож болно.
Танилцуулгын хичээлийг сайтар судалсан уншигчид магадлалын онол, бид аль хэдийн ямар нэг зүйлийг таамагласан. Гэхдээ нэмэх тэмдгийн утгын талаар дараа нь илүү ихийг хэлье.
Дараагийн асуултанд хариулахын тулд надад хоёр сайн дурын ажилтан хэрэгтэй байна... ...За, хэн ч хүсэхгүй байгаа бол би чамайг удирдах зөвлөлд дуудъя =)
Гуравдугаар асуулт: Даша, Наташа хоёрт нэг жимсийг хэдэн аргаар тарааж чадах вэ?
Хоёр жимс тараахын тулд эхлээд тэдгээрийг сонгох хэрэгтэй. Өмнөх асуултын "be" гэсэн догол мөрийн дагуу үүнийг янз бүрийн аргаар хийж болно, би тэдгээрийг дахин бичих болно:
алим, лийр;
алим ба гадил жимсний;
лийр ба банана.
Харин одоо хоёр дахин олон хослол байх болно. Жишээлбэл, эхний хос жимсийг авч үзье.
Та Дашаг алимаар, Наташаг лийрээр эмчилж болно;
эсвэл эсрэгээр - Даша лийр, Наташа алим авах болно.
Мөн ийм сэлгэлт нь хос жимс бүрийн хувьд боломжтой байдаг.
Бүжигт явсан оюутны бүлгийг авч үзье. Хүү, охин хоёрыг хэдэн янзаар хослуулж болох вэ?
Та 1 залууг сонгох арга замаар;
1 охиныг сонгох арга замууд.
Ингээд нэг залуу ТэгээдТа нэг охиныг сонгож болно: 
арга замууд.
Багц бүрээс 1 объект сонгогдсон тохиолдолд хослолыг тоолох дараах зарчим хүчинтэй байна: " бүрнэг багцаас объект хос үүсгэж болно бүртэйөөр олонлогийн объект."
Өөрөөр хэлбэл, Олег 13 охины аль нэгийг бүжигт урьж болно, Евгений арван гурван охины аль нэгийг нь урьж болно, бусад залуучууд ижил төстэй сонголттой. Нийт: боломжит хосууд.
Энэ жишээнд хос үүссэн "түүх" нь хамаагүй гэдгийг тэмдэглэх нь зүйтэй; Гэсэн хэдий ч хэрэв бид санаачлагыг харгалзан үзвэл 13 охин бүр ямар ч хөвгүүнийг бүжигт урих боломжтой тул хослолын тоог хоёр дахин нэмэгдүүлэх шаардлагатай. Энэ бүхэн тодорхой ажлын нөхцлөөс хамаарна!
Үүнтэй төстэй зарчим нь илүү төвөгтэй хослолуудад хүчинтэй байдаг, жишээлбэл: хоёр залуу эрэгтэйг хэдэн аргаар сонгож болох вэ? Тэгээдхоёр охин КВН-д оролцох уу?
Холбоо БАхослолыг үржүүлэх шаардлагатайг тодорхой харуулж байна:
Уран бүтээлчдийн боломжит бүлгүүд.
Өөрөөр хэлбэл, тус бүрхос хөвгүүд (45 өвөрмөц хос) хамтран тоглох боломжтой ямар чхос охид (78 өвөрмөц хос). Хэрэв бид оролцогчдын хоорондох үүргийн хуваарилалтыг авч үзвэл бүр илүү олон хослол байх болно. ...Үнэхээр хүсч байна, гэхдээ би чамайг оюутны амьдралд дургүй болгохгүйн тулд үргэлжлүүлэхээс татгалзах болно =).
Хослолыг үржүүлэх дүрэм нь илүү олон тооны үржүүлэгчид хамаарна.
Асуудал 8
5-д хуваагддаг гурван оронтой тоо хэд вэ?
Шийдэл: тодорхой болгохын тулд энэ тоог гурван одоор тэмдэглэе: ***
IN хэдэн зуун газарТа аль ч тоог (1, 2, 3, 4, 5, 6, 7, 8 эсвэл 9) бичиж болно. Тэг нь тохиромжгүй, учир нь энэ тохиолдолд тоо гурван оронтой байхаа больсон.
Гэхдээ дотор аравтын байр(дунд хэсэгт) та 10 цифрээс аль нэгийг нь сонгож болно: .
Нөхцөлийн дагуу тоо нь 5-д хуваагдах ёстой. 5 эсвэл 0-ээр төгссөн тоо 5-д хуваагдана. Тиймээс бид хамгийн бага ач холбогдол бүхий оронтой 2 цифрийг хангасан байна.
Нийтдээ байгаа: 5-д хуваагддаг гурван оронтой тоо.
Энэ тохиолдолд уг ажлыг дараах байдлаар тайлсан болно: "Та тоог сонгох 9 арга хэдэн зуун газар ТэгээдТоо сонгох 10 арга аравтын байр Тэгээд 2 арга зам нэгжийн цифр»
Эсвэл бүр энгийн: " тус бүр 9 цифрээс хэдэн зуун газарнэгтгэдэг тус бүртэй 10 оронтой аравтын байр мөн тус бүртэйхоёр оронтой тооноос нэгжийн цифр».
Хариулт: 180
Одоо…
Тиймээ, Бор, Дима, Володя нарт тус бүр нэг картыг өөр өөр аргаар тарааж болох 5-р асуудлын амласан тайлбарыг би бараг мартсан. Энд үржүүлэх нь ижил утгатай: тавцангаас 3 картыг арилгах арга замууд БА бүртдээжийг арга замаар дахин зохион байгуул.
Одоо өөрийнхөөрөө шийдэх асуудал байна... одоо би илүү сонирхолтой зүйл гаргах болно... энэ нь блэк-ийн орос хувилбартай адил байх болтугай:
Асуудал 9
"Цэг" тоглоход 2 картын хэдэн ялалтын хослол байдаг вэ?
Мэдэхгүй хүмүүсийн хувьд: ялалтын хослол нь 10 + ACE (11 оноо) = 21 оноо бөгөөд хоёр хөзрийн ялалтын хослолыг авч үзье.
(ямар ч хос дахь картуудын дараалал хамаагүй)
Хичээлийн төгсгөлд товч шийдэл, хариулт.
Дашрамд хэлэхэд, жишээг анхдагч гэж үзэх хэрэггүй. Блэкжак бол казиног ялах боломжийг олгодог математикт суурилсан алгоритмтай бараг цорын ганц тоглоом юм. Сонирхсон хүмүүс оновчтой стратеги, тактикийн талаар маш их мэдээлэл олж авах боломжтой. Үнэн, ийм мастерууд бүх байгууллагын хар жагсаалтад маш хурдан ордог =)
Хэд хэдэн хатуу даалгавраар бүрхэгдсэн материалыг нэгтгэх цаг болжээ.
Асуудал 10
Вася гэртээ 4 мууртай.
a) муурыг өрөөний буланд хэдэн янзаар суулгаж болох вэ?
б) муурыг хэдэн аргаар зугаалж болох вэ?
в) Вася хэдэн аргаар хоёр муур (нэг нь зүүн талд, нөгөө нь баруун талд) авч чадах вэ?
Шийдье: Нэгдүгээрт, та асуудалтай холбоотой гэдгийг дахин анхаарах хэрэгтэй өөробъектууд (муур нь ижил ихрүүд байсан ч гэсэн). Энэ бол маш чухал нөхцөл юм!
a) Муурны чимээгүй байдал. Энэхүү гүйцэтгэлийн дагуу бүх муурыг нэг дор
+ тэдгээрийн байршил чухал тул энд сэлгэлтүүд байна:
Эдгээр аргуудыг ашиглан муурыг өрөөний буланд байрлуулж болно.
Сэлгээ хийхдээ зөвхөн өөр өөр объектуудын тоо, тэдгээрийн харьцангуй байрлал чухал гэдгийг би давтан хэлье. Васягийн сэтгэлийн байдлаас хамааран тэрээр амьтдыг буйдан дээр хагас тойрог хэлбэрээр, цонхны тавцан дээр дараалан суулгаж болно. - бүх тохиолдолд 24 солих байх болно, сонирхолтой хүмүүс муурыг олон өнгийн (жишээлбэл, цагаан, хар, улаан, tabby) гэж төсөөлж, бүх боломжит хослолуудыг жагсааж болно.
б) Та муурыг хэдэн аргаар зугаалж болох вэ?
Муурууд зөвхөн хаалгаар зугаалдаг гэж үздэг бөгөөд асуулт нь амьтдын тоонд хайхрамжгүй ханддаг - 1, 2, 3 эсвэл бүх 4 муур зугаалж болно.
Бид бүх боломжит хослолуудыг тооцдог.
Эдгээр арга замаар та нэг муурыг (дөрвийн аль нэгийг) зугаалахыг зөвшөөрч болно; 
хоёр муурыг зугаалах арга замууд (сонголтуудыг өөрөө жагсаах);
гурван муурыг зугаалахаар явуулах боломжтой (дөрвийн нэг нь гэртээ суудаг);
Ингэснээр та бүх муурыг суллаж чадна.
Үр дүнгийн утгыг нэгтгэн дүгнэх ёстой гэж та таамагласан байх.
муурыг зугаалгаар явуулах арга замууд.
Сонирхогчдын хувьд би асуудлын төвөгтэй хувилбарыг санал болгож байна - ямар ч дээжийн муур 10-р давхрын хаалга, цонхоор санамсаргүй байдлаар гадаа гарах боломжтой. Хослолууд мэдэгдэхүйц нэмэгдэх болно!
в) Вася хоёр муурыг хэдэн аргаар авах вэ?
Нөхцөл байдал нь зөвхөн 2 амьтныг сонгохоос гадна тэдгээрийг гар тус бүрт байрлуулах явдал юм.
Эдгээр аргаар та 2 муур авах боломжтой.
Хоёрдахь шийдэл: та аргуудыг ашиглан хоёр муур сонгож болно Тэгээдтарих арга замууд бүргарт байгаа хос: 
Хариулт: a) 24, б) 15, в) 12
За, мөс чанараа цэвэрлэхийн тулд хослолыг үржүүлэх талаар илүү тодорхой зүйл ... Васяг нэмж 5 мууртай болгоё =) 2 муурыг хэдэн янзаар зугаалуулж болох вэ? Тэгээд 1 муур?
Энэ нь хамт тус бүрхэд хэдэн муурыг суллаж болно бүрмуур.
Бие даасан шийдэлд зориулсан өөр нэг товчлуурын баян хуур:
Асуудал 11
Гурван зорчигч 12 давхар барилгын цахилгаан шатанд суусан байна. Хүн бүр бусдаас үл хамааран аль ч (2-р давхраас эхлэн) ижил магадлалтайгаар гарч болно. Хэдэн аргаар:
1) зорчигчид нэг давхарт бууж болно (гарах дараалал хамаагүй);
2) хоёр хүн нэг давхарт, гурав дахь нь нөгөө давхарт бууж болно;
3) хүмүүс өөр өөр давхарт гарах боломжтой;
4) зорчигчид цахилгаан шатнаас гарах боломжтой юу?
Энд тэд дахин асуудаг, би тодруулж байна: хэрэв нэг давхарт 2 эсвэл 3 хүн гарах юм бол гарах дараалал хамаагүй. БОДОХ, хослолыг нэмэх/үржүүлэхэд томьёо, дүрмийг ашигла. Зорчигчид хүндрэлтэй тохиолдолд лифтнээс ямар хослолоор гарах боломжтойг хэлж, таамаглах нь ашигтай байдаг. Хэрэв ямар нэг зүйл болохгүй бол бухимдах шаардлагагүй, жишээлбэл, 2-р цэг нь маш нууцлаг юм.
Хичээлийн төгсгөлд дэлгэрэнгүй тайлбар бүхий бүрэн шийдэл.
Эцсийн догол мөр нь нэлээд олон удаа тохиолддог хослолуудад зориулагдсан болно - миний субъектив үнэлгээний дагуу комбинаторын асуудлын 20-30% -д:
Сэлгээ, хослол, давталттай байршуулалт
Жагсаалтад орсон төрлийн хослолуудыг лавлах материалын 5-р зүйлд тусгасан болно Комбинаторикийн үндсэн томъёо, гэхдээ тэдгээрийн зарим нь эхний уншлагад тийм ч тодорхой биш байж магадгүй юм. Энэ тохиолдолд эхлээд практик жишээнүүдтэй танилцаж, дараа нь ерөнхий томъёоллыг ойлгохыг зөвлөж байна. Явах:
Дахин давтагдах өөрчлөлтүүд
"Энгийн" солихтой адил давталттай сэлгэн залгалтуудад, бүх олон объектыг нэг дор, гэхдээ нэг зүйл бий: энэ багцад нэг буюу хэд хэдэн элемент (объект) давтагдана. Дараагийн стандартыг хангана уу:
Асуудал 12
K, O, L, O, K, O, L, b, Ch, I, K гэсэн үсгүүдтэй картуудыг өөрчилснөөр хэдэн өөр үсгийн хослол авах боломжтой вэ?
Шийдэл: Хэрэв бүх үсгүүд өөр байсан бол өчүүхэн томьёог хэрэглэх шаардлагатай байсан ч санал болгож буй картуудын хувьд зарим заль мэх "сул зогсолтгүй" ажиллах нь тодорхой байна, жишээлбэл, хэрэв та хоёр картыг сольсон бол. "K" үсгээр ямар ч үгэнд та ижил үгийг авна. Түүнээс гадна, бие махбодийн хувьд картууд нь маш өөр байж болно: нэг нь "K" үсэгтэй дугуй хэлбэртэй, нөгөө нь "K" үсэг зурсан дөрвөлжин хэлбэртэй байж болно. Гэхдээ даалгаварын утгын дагуу ийм картууд ч гэсэн адилхан гэж үздэг, нөхцөл нь үсгийн хослолын талаар асуудаг тул.
Бүх зүйл маш энгийн - ердөө 11 карт, түүний дотор захидал:
K - 3 удаа давтана;
O - 3 удаа давтана;
L - 2 удаа давтана;
b - 1 удаа давтана;
H - 1 удаа давтагдсан;
Мөн - 1 удаа давтана.
Шалгах: 3 + 3 + 2 + 1 + 1 + 1 = 11, энэ нь шалгах шаардлагатай зүйл юм.
Томъёоны дагуу давталттай солих тоо:
янз бүрийн үсгийн хослолыг авч болно. Хагас сая гаруй!
Том хүчин зүйлийн утгыг хурдан тооцоолохын тулд Excel-ийн стандарт функцийг ашиглахад тохиромжтой: дурын нүд рүү оруулна уу =БОДИТ(11)болон дарна уу Оруулна уу.
Практикт ерөнхий томьёо бичихгүй байх, үүнээс гадна нэгж хүчин зүйлийг орхих нь бүрэн зөвшөөрөгдөхүйц юм. 
Гэхдээ давтагдсан захидлын талаархи урьдчилсан тайлбар шаардлагатай!
Хариулт: 554400
Давталттай солих өөр нэг ердийн жишээ нь агуулахаас олж болох шатрын чулуу байрлуулах асуудалд тохиолддог. бэлэн шийдлүүдхаргалзах pdf-д. Бие даасан шийдлийн хувьд би арай бага томъёолсон даалгавар гаргаж ирэв.
Асуудал 13
Алексей спортоор хичээллэдэг бөгөөд долоо хоногт 4 өдөр - хөнгөн атлетик, 2 өдөр - хүч чадлын дасгал, 1 өдөр амардаг. Тэр өөртөө зориулж долоо хоногийн хуваарийг хэдэн аргаар гаргаж чадах вэ?
Энэ томьёо энд ажиллахгүй, учир нь энэ нь санамсаргүй солилцоог (жишээлбэл, Лхагва гарагийн хүч чадлын дасгалыг Пүрэв гарагийн хүчний дасгалуудтай солих) харгалзан үздэг. Дахин хэлэхэд - үнэндээ ижил 2 хүч чадлын бэлтгэл нь бие биенээсээ эрс ялгаатай байж болох ч даалгаврын хүрээнд (хуваарийн үүднээс) тэдгээрийг ижил элементүүд гэж үздэг.
Хичээлийн төгсгөлд хоёр мөрийн шийдэл, хариулт.
Давталттай хослолууд
Энэ төрлийн хослолын онцлог шинж чанар нь дээжийг хэд хэдэн бүлгээс авсан бөгөөд тус бүр нь ижил объектуудаас бүрддэг.
Өнөөдөр бүгд шаргуу ажилласан тул өөрийгөө сэргээх цаг болжээ.
Асуудал 14
Оюутны гуанз нь зуурмаг, бяслагны бялуу, пончикоор хийсэн хиам зардаг. Та таван бялууг хэдэн аргаар худалдаж авах вэ?
Шийдэл: давталттай хослуулах ердийн шалгуурыг нэн даруй анхаарч үзээрэй - нөхцөл байдлын дагуу энэ нь сонгоход санал болгож буй объектуудын багц биш, харин янз бүрийн төрөлобъект; худалдаанд дор хаяж таван хот-дог, 5 cheesecakes, 5 пончик байдаг гэж таамаглаж байна. Бүлэг тус бүрийн бялуу нь мэдээжийн хэрэг өөр өөр байдаг - учир нь яг ижилхэн гурилан бүтээгдэхүүнийг зөвхөн компьютер дээр дуурайлган хийх боломжтой =) Гэсэн хэдий ч бялууны физик шинж чанар нь асуудлын зорилгод тийм ч чухал биш бөгөөд халуун нохой / cheesecakes / Тэдний бүлгүүд дэх гурилан бүтээгдэхүүн нь адилхан гэж тооцогддог.
Түүвэрт юу байж болох вэ? Юуны өмнө түүвэрт яг ижил бялуу байх болно гэдгийг тэмдэглэх нь зүйтэй (Бид 5 ширхэгийг сонгож байгаа бөгөөд 3 төрлийн сонголттой байдаг). Энд амт болгоны сонголтууд байдаг: 5 хот-дог, 5 cheesecakes, 5 пончик, 3 хот-дог + 2 cheesecakes, 1 хот-дог + 2 cheesecakes + 2 пончик гэх мэт.
"Ердийн" хослолуудын нэгэн адил бялууг сонгох, байрлуулах дараалал нь хамаагүй - та ердөө 5 ширхэгийг сонгоод л болоо.
Бид томъёог ашигладаг 
давталттай хослолын тоо: 
Та энэ аргыг ашиглан 5 бялуу худалдаж авах боломжтой.
Сайхан хооллоорой!
Хариулт: 21
Комбинаторийн олон бодлогоос ямар дүгнэлт хийж болох вэ?
Заримдаа хамгийн хэцүү зүйл бол нөхцөл байдлыг ойлгох явдал юм.
Бие даасан шийдлийн ижил төстэй жишээ:
Асуудал 15
Түрийвч нь нэлээд олон тооны 1, 2, 5, 10 рублийн зоос агуулдаг. Түрийвчнээс гурван зоосыг хэдэн аргаар гаргаж болох вэ?
Өөрийгөө хянахын тулд хэд хэдэн энгийн асуултанд хариулна уу:
1) Дээж дэх бүх зоос өөр байж болох уу?
2) Зоосны "хамгийн хямд", хамгийн "үнэтэй" хослолыг нэрлэ.
Хичээлийн төгсгөлд шийдэл ба хариултууд.
Миний хувийн туршлагаас харахад давталттай хослолууд нь практикт хамгийн ховор зочин гэдгийг би хэлж чадна, үүнийг дараах төрлийн хослолуудын талаар хэлэх боломжгүй юм.
Давталт бүхий байрлалууд
Элементүүдээс бүрдсэн олонлогоос элементүүдийг сонгох ба сонголт бүрийн элементүүдийн дараалал чухал байдаг. Бүх зүйл сайхан байх болно, гэхдээ гэнэтийн хошигнол бол бид анхны багцын дурын объектыг хүссэн хэмжээгээрээ сонгож болно. Дүрслэлээр хэлбэл, "олон цөөрөхгүй".
Энэ хэзээ тохиолддог вэ? Ердийн жишээ бол хэд хэдэн диск бүхий хосолсон түгжээ боловч технологийн хөгжлийн улмаас түүний дижитал удамшлыг авч үзэх нь илүү чухал юм.
Асуудал 16
Хэдэн дөрвөн оронтой ПИН код байдаг вэ?
Шийдэл: үнэндээ асуудлыг шийдэхийн тулд комбинаторикийн дүрмийн талаархи мэдлэг хангалттай: та ПИН кодын эхний цифрийг сонгох боломжтой. Тэгээдарга замууд - ПИН кодын хоёр дахь цифр Тэгээдолон талаараа - гуравдугаарт Тэгээдижил тоо - дөрөв дэх. Тиймээс хослолыг үржүүлэх дүрмийн дагуу дөрвөн оронтой пин кодыг дараах байдлаар бүрдүүлж болно.
Тэгээд одоо томъёог ашиглаж байна. Нөхцөлийн дагуу бидэнд дугааруудыг санал болгож, тэдгээрээс дугаарыг сонгож, цэгцэлдэг тодорхой дарааллаар, харин түүвэр дэх тоонууд давтагдаж болно (өөрөөр хэлбэл эх олонлогийн аль ч цифрийг дурын хэдэн удаа ашиглаж болно). Дахин давтагдах байршлын тооны томъёоны дагуу: 
Хариулт: 10000
Энд юу бодогддог вэ... ... АТМ гурав дахь удаагаа ПИН код оруулах оролдлого бүтэлгүйтсэний дараа картыг "идсэн" бол санамсаргүй байдлаар авах магадлал маш бага байдаг.
Комбинаторик нь практик утгагүй гэж хэн хэлсэн бэ? Сайтын бүх уншигчдад зориулсан танин мэдэхүйн даалгавар:
Асуудал 17
Улсын стандартын дагуу автомашины улсын дугаар нь 3 тоо, 3 үсгээс бүрдэнэ. Энэ тохиолдолд гурван тэгтэй тоог хүлээн зөвшөөрөх боломжгүй бөгөөд үсгийг A, B, E, K, M, N, O, P, S, T, U, X багцаас сонгоно. (зөвхөн кирилл үсэг нь латин үсэгтэй давхцаж байгаа үсгийг ашигладаг).
Тухайн бүс нутагт хэдэн өөр улсын дугаар үүсгэж болох вэ?
Дашрамд хэлэхэд тэд тийм ч олон биш. Томоохон бүс нутагт ийм тоо хэмжээ хангалтгүй байдаг тул тэдний хувьд RUS бичээсийн хэд хэдэн код байдаг.
Шийдэл, хариулт нь хичээлийн төгсгөлд байна. Комбинаторикийн дүрмийг ашиглахаа бүү мартаарай ;-) ...Би онцгой зүйл гэдгийг харуулахыг хүссэн боловч онцгой биш байсан =) Би Википедиа руу харлаа - тайлбаргүй ч гэсэн тооцоолол байдаг. Хэдийгээр боловсролын зорилгоор үүнийг цөөхөн хүн шийдсэн байх.
Бидний сэтгэл хөдөлгөм хичээл дуусч, эцэст нь би та цагаа дэмий үрээгүй гэдгийг хэлмээр байна - учир нь комбинаторикийн томъёо нь өөр нэг чухал практик хэрэглээг олж авдаг: тэдгээр нь янз бүрийн асуудлуудад байдаг. магадлалын онол,
болон дотор магадлалын сонгодог тодорхойлолттой холбоотой асуудлууд- ялангуяа ихэвчлэн =)
Идэвхтэй оролцсон та бүхэндээ баярлалаа, удахгүй уулзацгаая!
Шийдэл ба хариултууд:
Даалгавар 2: Шийдэл: 4 картын бүх боломжит шилжүүлгийн тоог ол:
Тэгтэй картыг 1-р байранд байрлуулахад тоо нь гурван оронтой болох тул эдгээр хослолыг хасах хэрэгтэй. Тэгийг 1-р байранд оруулаарай, дараа нь доод цифрүүдийн үлдсэн 3 цифрийг янз бүрийн аргаар дахин байрлуулж болно.
Анхаарна уу
: учир нь Цөөн хэдэн карт байгаа тул энд бүх сонголтыг жагсаахад хялбар байдаг:
0579
0597
0759
0795
0957
0975
Тиймээс, санал болгож буй багцаас бид дараахь зүйлийг хийж болно.
24 – 6 = 18 дөрвөн оронтой тоо
Хариулт
: 18
Даалгавар 4: Шийдэл: арга замаар та 36 картаас 3 карт сонгох боломжтой.
Хариулт
: 7140
Даалгавар 6: Шийдэл: 
арга замууд.
Өөр нэг шийдэл
: бүлгээс хоёр хүнийг сонгох арга замууд болон
2) "Хамгийн хямд" багц нь 3 рублийн зоос, хамгийн "үнэтэй" нь 3 арван рублийн зоос агуулдаг.
Асуудал 17: Шийдэл: 
Эдгээр аргуудыг ашиглан та машины дугаарын дижитал хослолыг үүсгэж болох бөгөөд тэдгээрийн аль нэгийг (000) хасах хэрэгтэй: .
Эдгээр аргуудыг ашиглан та автомашины дугаарын үсгийн хослолыг үүсгэж болно.
Үржүүлэх хослолын дүрмийн дагуу нийт дүнг гаргаж болно.
машины дугаар
(тус бүрдижитал хослолыг хослуулсан тус бүртэйүсгийн хослол).
Хариулт
: 1726272
Комбинаторикийн хувьд тэд өгөгдсөн объектуудаас (элементүүд) тодорхой төрлийн хэдэн хослол хийж болох тухай асуултуудыг судалдаг.
Комбинаторик нэг салбар болж үүссэн нь мөрийтэй тоглоомын онолын тухай Б.Паскаль, П.Фермат нарын бүтээлүүдтэй холбоотой. Комбинаторын аргыг хөгжүүлэхэд асар их хувь нэмэр оруулсан Г.В. Лейбниц, Ж.Бернулли, Л.Эйлер нар.
Францын философич, зохиолч, математикч, физикч Блез Паскаль (1623-1662) математикийн гайхалтай чадвараа эрт харуулжээ. Паскалийн математикийн сонирхлын хүрээ маш олон янз байсан. Паскаль нэг зүйлийг нотолсон
проекцийн геометрийн үндсэн теоремуудаас (Паскалын теорем) нийлбэрийн машин (Паскалын нэмэх машин) зохион бүтээж, бином коэффициентийг тооцоолох аргыг (Паскалын гурвалжин) гаргаж, математикийн индукцийн аргыг анх удаа үнэн зөв тодорхойлж, нотлох аргыг ашигласан, хязгааргүй бага анализыг хөгжүүлэхэд чухал алхам хийж, магадлалын онол үүсэхэд чухал үүрэг гүйцэтгэсэн. Гидростатикт Паскаль үндсэн хуулиа (Паскалын хууль) бий болгосон. Паскалийн "Аймагт бичсэн захидал" нь Францын сонгодог зохиолын шилдэг бүтээл байв.
Готфрид Вильгельм Лейбниц (1646-1716) нь Германы философич, математикч, физикч, зохион бүтээгч, хуульч, түүхч, хэл шинжлэлийн эрдэмтэн юм. Математикийн хувьд тэрээр И.Ньютонтой хамт дифференциал ба интеграл тооцоог боловсруулсан. Тэрээр комбинаторикт чухал хувь нэмэр оруулсан. Ялангуяа түүний нэр нь тооны онолын асуудлуудтай холбоотой байдаг.
Готфрид Вильгельм Лейбниц нь тийм ч гайхалтай дүр төрхтэй байсангүй, тиймээс нэлээд энгийн хүн мэт сэтгэгдэл төрүүлжээ. Парист нэг өдөр тэрээр өөрийн таньдаг гүн ухаантны номыг худалдаж авах найдлагатайгаар номын дэлгүүрт оров. Нэгэн зочин энэ номын талаар асуухад номын худалдагч түүнийг толгойноосоо хөл хүртэл шалгаж үзээд: "Чамд яагаад хэрэгтэй байна вэ? Чи үнэхээр ийм ном унших чадвартай юу?" Эрдэмтэн хариулж амжаагүй байтал номын зохиогч өөрөө "Агуу Лейбницт мэндчилж, хүндэтгэе!" Гэж дэлгүүрт оров. Энэ бол үнэхээр алдартай Лейбниц байсан бөгөөд ном нь эрдэмтдийн дунд маш их эрэлт хэрэгцээтэй байсан гэдгийг худалдагч ойлгохгүй байв.
Ирээдүйд дараахь чухал үүрэг гүйцэтгэнэ
Лемма.Элементүүдийн багцыг, олонлогт элементүүдийг оруулаарай. Дараа нь бүх ялгаатай хосуудын тоо нь тэнцүү байх болно.
Баталгаа.Үнэн хэрэгтээ, олонлогийн нэг элементээр бид ийм өөр хос, нийтдээ олон тооны элементүүдийг хийж чадна.
Байршил, сэлгэлт, хослолууд
Гурван элементийн багцтай болцгооё. Эдгээр хоёр элементийг бид ямар аргаар сонгож болох вэ? .
Тодорхойлолт.Өөр өөр элементүүдийн олонлогийн элементүүдийн зохион байгуулалт нь өгөгдсөн элементүүдээс > элементээр бүрдэх ба элементүүдийн өөрт нь эсвэл элементүүдийн дарааллаар ялгаатай хослолууд юм.
Элементүүдийн багцын бүх зохицуулалтын тоог элементүүдээр (франц хэлний "зохицуулалт" гэсэн үгийн эхний үсгээс авсан) энд ба .
Теорем.Элементүүдийн багцын байршлын тоо нь тэнцүү байна
Баталгаа.Бидэнд элементүүд байгаа гэж бодъё. Байршуулах боломжтой байг. Бид эдгээр байршлыг дарааллаар нь барих болно. Эхлээд эхний байршуулах элементийг тодорхойлъё. Өгөгдсөн элементүүдийн багцаас үүнийг янз бүрийн аргаар сонгож болно. Эхний элементийг сонгосны дараа хоёр дахь элементийг сонгох гэх мэт арга замууд хэвээр байна. Ийм сонголт бүр нь шинэ байрлалыг өгдөг тул эдгээр бүх сонголтыг бие биетэйгээ чөлөөтэй хослуулж болно. Тиймээс бидэнд:
Жишээ.Таван өнгийн материал байвал туг өөр өөр өнгийн гурван хэвтээ судлуудаас хэдэн янзаар бүтэх вэ?
Шийдэл.Шаардлагатай тооны гурван хамтлаг туг:
Тодорхойлолт.Элементүүдийн багцыг солих нь элементүүдийг тодорхой дарааллаар байрлуулах явдал юм.
Тиймээс гурван элементийн олонлогийн бүх өөр өөр сэлгэлтүүд байна
Элементүүдийн бүх сэлгэлтийн тоог зааж өгсөн (Франц хэлний "сэлгэн залгалт", "хөдөлгөөн" гэсэн үгийн эхний үсгээс). Тиймээс бүх өөр өөр орлуулалтын тоог томъёогоор тооцоолно
Жишээ.Шатрын тавцан дээр дэгээнүүд бие биенээ дайрахгүйн тулд хэдэн янзаар байрлуулж болох вэ?
Шийдэл.Шаардлагатай тооны дэгээ
А- приорит!
Тодорхойлолт.Элементүүдээр өөр өөр элементүүдийн хослолууд нь өгөгдсөн элементүүдээс бүрдсэн элементүүдээс бүрдэх ба хамгийн багадаа нэг элементээр ялгаатай (өөрөөр хэлбэл өгөгдсөн олонлогийн элементийн дэд олонлогууд) нэгдэл юм.
Таны харж байгаагаар хослолууд нь байршлаас ялгаатай нь элементүүдийн дарааллыг харгалзан үздэггүй. Элементүүдийн бүх хослолын тоог, тус бүр дэх элементүүдийг зааж өгсөн болно (франц хэлний "хослол" гэсэн үгийн эхний үсгээс авсан нь "хослол" гэсэн утгатай).
Тоонууд
Хоёр багцын бүх хослолууд нь .
Тоонуудын шинж чанарууд (\sf C)_n^k
Үнэн хэрэгтээ өгөгдсөн -элементийн олонлогийн -элементийн дэд олонлог бүр нь ижил олонлогийн нэг бөгөөд зөвхөн нэг -элементийн дэд олонлогтой тохирч байна.
Үнэн хэрэгтээ бид элементүүдийн дэд олонлогуудыг дараах байдлаар сонгож болно: нэг элементийг засах; энэ элементийг агуулсан -элементийн дэд олонлогуудын тоо тэнцүү байна; Энэ элементийг агуулаагүй элементийн дэд олонлогуудын тоо нь -тэй тэнцүү байна.
Паскалийн гурвалжин
Энэ гурвалжинд эгнээ тус бүрийн туйлын тоо 1-тэй тэнцүү байх ба туйлын бус тоо бүр нь өмнөх эгнээний дээрх хоёр тооны нийлбэртэй тэнцүү байна. Тиймээс энэ гурвалжин нь тоог тооцоолох боломжийг танд олгоно.
Теорем.
Баталгаа.Элементүүдийн багцыг авч үзээд дараах асуудлыг хоёр аргаар шийдье: өгөгдсөн элементээс хэдэн дараалал үүсгэж болох вэ?
нэг ч элемент хоёр удаа харагдахгүй олонлогууд?
1 арга зам. Бид дарааллын эхний гишүүнийг, дараа нь хоёр дахь, гурав дахь гэх мэтийг сонгоно. гишүүн
Арга 2. Эхлээд өгөгдсөн олонлогоос элементүүдийг сонгоод дараа нь тэдгээрийг дарааллаар нь байрлуулцгаая
Энэ бутархайн хүртэгч ба хуваагчийг дараах байдлаар үржүүлнэ.
Жишээ.Та "Спортлото" тоглоомын 36 тооноос 5 тоог хэдэн аргаар сонгож болох вэ?
Шаардлагатай тооны арга
Даалгаврууд.
1.
Автомашины улсын дугаар нь орос цагаан толгойн 3 үсэг (33 үсэг), 4 тооноос бүрдэнэ. Хэдэн өөр улсын дугаар байдаг вэ?
2.
Төгөлдөр хуур дээр 88 товчлуур байдаг. Та 6 дууг дараалан хэдэн аргаар гаргаж болох вэ?
3.
5-д хуваагддаг зургаан оронтой тоо хэд вэ?
4.
Гурван халаасанд 7 өөр зоосыг хэдэн аргаар хийж болох вэ?
5.
Та ядаж нэг удаа аравтын бутархайн тэмдэглэгээнд 5 оронтой хэдэн таван оронтой тоог гаргаж чадах вэ?
6.
Тойргоор хөдөлж нэг нэгнээсээ авах боломжтой бол 20 хүнийг дугуй ширээний ард хэдэн янзаар суулгаж болох вэ?
7.
5-д хуваагддаг, ижил цифрүүд агуулаагүй таван оронтой тоо хэд вэ?
8.
1 см-ийн эсийн талтай алаг цаасан дээр 100 см-ийн радиустай тойрог зурсан бөгөөд энэ нь эсийн оройгоор дамжин өнгөрөхгүй, нүдний хажуу тал руу хүрдэггүй. Энэ тойрог хэдэн нүдийг огтолж чадах вэ?
9.
Тоонуудыг зэргэлдээх, өсөх дарааллаар байрлуулахаар хэдэн янзаар тоонуудыг дараалан байрлуулж болох вэ?
10.
Цифр бүрийг зөвхөн нэг удаа ашиглах боломжтой бол цифрүүдээс хэдэн таван оронтой тоо гаргах вэ?
11.
ROT гэдэг үгнээс үсгүүдийг өөрчилснөөр TOP, ORT, OTR, TRO, RTO гэсэн үгсийг гаргаж болно. Тэдгээрийг анаграмм гэж нэрлэдэг. ЛОГАРИТМ гэдэг үгнээс хэдэн анаграм хийж болох вэ?
12.
За дуудъя хуваахнатурал тоо, түүнийг натурал тоонуудын нийлбэрээр дүрслэх. Жишээлбэл, тооны бүх хуваалтууд энд байна:
Хуваалтууд нь тоогоор эсвэл нэр томъёоны дарааллаар ялгаатай байвал ялгаатай гэж үзнэ.
Тооныг нэр томъёонд хуваах хэд байдаг вэ?
13.
Өсөхгүй оронтой дараалалтай гурван оронтой тоо хэд вэ?
14.
Өсөхгүй оронтой дараалалтай дөрвөн оронтой хэдэн тоо байдаг вэ?
15.
17 хүнийг хэдэн янзаар зэрэгцүүлэн суулгаж болох вэ?
16.
охид, хөвгүүдийг санамсаргүй байдлаар эгнээнд суулгадаг. Хоёр охин зэрэгцэн суухгүйн тулд тэднийг хэдэн янзаар суулгаж болох вэ?
17.
охид, хөвгүүдийг санамсаргүй байдлаар эгнээнд суулгадаг. Бүх охидыг зэрэгцүүлэн суулгахын тулд тэднийг хэдэн янзаар суулгаж болох вэ?
Тогтмол тоотой, элементүүдийн давталтгүйгээр хязгаарлагдмал олонлогийн элементүүдийн дараалалгүй сонголтыг хослол гэнэ. Янз бүрийн хослолууд нь дор хаяж нэг элементээр ялгаатай байх ёстой бөгөөд элементүүдийн дараалал нь хамаагүй. Жишээлбэл, латин үсгийн бүх эгшгийн багцаас (AEIOU) та 3 үсгийн 10 өөр хослол хийж, дараах дараалалгүй гурвалсан үсгийг үүсгэж болно.
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Сонирхолтой нь та ижил таван үсгээс 10 өөр хослолыг нэг дор 2 үсгийг нэгтгэж, дараах дараалалгүй хосуудыг үүсгэж болно.
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
Гэсэн хэдий ч, хэрэв та ижил эгшигт латин үсгийг 4-өөр нийлүүлбэл дараах 5 өөр хослолыг л авна.
AEIO, AEIU, AIOU, EIOU, AEOU.
Ерөнхийдөө m элементийн n өөр элементийн хослолын тоог тэмдэглэхийн тулд дараах функциональ, индекс эсвэл вектор (Appel) бэлгэдлийг ашигладаг.
Тэмдэглэгээний хэлбэрээс үл хамааран n элементийн m элементийн хослолын тоог дараах үржүүлэх болон хүчин зүйлийн томъёог ашиглан тодорхойлж болно.
Эдгээр томьёог ашиглан тооцоолсон үр дүн нь дээр дурдсан жишээний үр дүнтэй давхцаж байгаа эсэхийг шалгахад хялбар байдаг. Тодруулбал, n=5 ба m=3-тай бол эдгээр томъёог ашиглан тооцоо хийх нь дараах үр дүнг өгнө.
Ерөнхий тохиолдолд хослолын тооны томъёо нь хослолын утгатай бөгөөд n > m > 0 байх n ба m бүхэл тоонд хүчинтэй байна. Хэрэв m > n ба m бол< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Нэмж дурдахад, үржүүлэх болон хүчин зүйлийн томъёонд шууд орлуулах замаар хялбархан шалгах боломжтой хослолуудын дараах хязгаарлагдмал тоог санах нь зүйтэй.
Мөн m нь бүхэл тоо хэвээр байгаа тохиолдолд n нь бодит тоо байсан ч үржүүлэх томъёо хүчинтэй хэвээр байдгийг тэмдэглэх нь зүйтэй. Гэсэн хэдий ч үүнийг ашигласан тооцооллын үр дүн нь албан ёсны хүчинтэй байхын зэрэгцээ комбинаторын утгыг алддаг.
ХОЛБОГДОЛЫН ТОДОРХОЙЛОЛТ
N ба m-ийн дурын утгуудын хослолын тоог тодорхойлохын тулд үржүүлэх болон хүчин зүйлийн томъёог практикт ашиглах нь тэдгээрийн тоо ба хуваагчийн хүчин зүйлийн бүтээгдэхүүний экспоненциал өсөлтөөс болж бүтээмж багатай болж хувирдаг. Харьцангуй бага n ба m утгын хувьд ч эдгээр бүтээгдэхүүн нь орчин үеийн тооцоолол, програм хангамжийн системд бүхэл тоог илэрхийлэх чадвараас давж гардаг. Түүнээс гадна тэдгээрийн үнэ цэнэ нь харьцангуй бага байж болох хослолын тооноос мэдэгдэхүйц их байх болно. Жишээлбэл, n=10-аас m=8 элементийн хослолын тоо ердөө 45 байна. Гэсэн хэдий ч хүчин зүйлийн томъёог ашиглан энэ утгыг олохын тулд эхлээд 10-аас хамаагүй том утгыг тооцоолох хэрэгтэй! тоологч болон 8! хуваарьт:
Их хэмжээний боловсруулалт хийхэд цаг хугацаа шаардсан үйлдлүүдийг арилгах, хослолын тоог тодорхойлохын тулд үржүүлгийн болон хүчин зүйлийн томъёоноос шууд гардаг янз бүрийн дахилтын харилцааг ашиглаж болно. Тодруулбал, үржүүлэх томъёоноос дараах давталтын хамаарал гарч ирдэг бөгөөд энэ нь түүний индексүүдийн харьцааг хослолын тооны тэмдгээс илүү авах боломжийг олгодог.
Эцэст нь, доод тэмдгийг тогтмол байлгах нь дараах давталтын хамаарлыг бий болгодог бөгөөд үүнийг хослолын тооны факториал томъёоноос хялбархан олж авдаг.
Анхан шатны өөрчлөлтүүдийн дараа үүссэн гурван давталтын харилцааг дараах хэлбэрээр илэрхийлж болно.
Хэрэв бид одоо эхний 2 томьёоны зүүн ба баруун талыг нэмж, үр дүнг n-ээр бууруулбал бид нэг чухал давталтын хамаарлыг олж авах бөгөөд үүнийг хослолын тоог нэмэх таних тэмдэг гэж нэрлэдэг.
Нэмэлт танилт нь хүчин зүйлийн үржвэрийн үржүүлгийн үйлдлүүдийг илүү энгийн нэмэх үйлдлээр, цөөн тооны хослолоор солих боломжийг олгодог тул n ба m-ийн том утгуудын хослолын тоог үр дүнтэй тодорхойлох үндсэн дахилтын дүрмийг өгдөг. Ялангуяа нэмэх таних тэмдэгийг ашиглан дээр дурдсан n=10 m=8 элементийн хослолын тоог дараах давталтын хувиргалтыг гүйцэтгэх замаар тодорхойлоход хялбар болсон.
Нэмж дурдахад, нэмэх таних тэмдэгээс төгсгөлтэй нийлбэрийг тооцоолох хэд хэдэн ашигтай харилцааг гаргаж авах боломжтой, тухайлбал, дараах хэлбэртэй байна.
Хэрэв нэмэлт тэмдэгтэнд бид хамгийн том дээд тэмдэгтийн доод тэмдэг 0-ээс их байх үед тухайн нэр томьёоны дагуу давталтыг өргөтгөх юм бол энэ хамаарлыг олж авна. Дараах тоон жишээ нь энэ давтагдах хувиргалтын үйл явцыг харуулж байна:
Натурал тоонуудын чадлын нийлбэрийг тооцоолохдоо дэд бичвэрийн нийлбэрийн томъёог ихэвчлэн ашигладаг. Ялангуяа m=1 гэж үзвэл энэ томьёог ашиглан натурал цувралын эхний n тооны нийлбэрийг олоход хялбар болно.
Нэгдэлийн томьёоны өөр нэг ашигтай хувилбарыг нэр томьёоны дагуу нэмэх таних тэмдэгийн давталтыг хамгийн жижиг үсгээр тэлэх замаар олж авч болно. Дараах тоон жишээ нь давтагдах хувиргалтын энэ хувилбарыг харуулж байна:
Ерөнхийдөө ийм хувиргалтын үр дүнд индексүүд нь хөрш зэргэлдээх нөхцлөөс нэгээр ялгаатай хослолуудын тоонуудын нийлбэрийг олж авдаг бөгөөд индексүүдийн зөрүү тогтмол хэвээр байна (харгалзан үзэх жишээнд энэ нь бас нэгтэй тэнцүү). Тиймээс бид хослолын тоонуудын хоёр индексийн дараах нийлбэрийн томъёог олж авна.
Дээр дурдсан давталтын хамаарал ба нийлбэрийн томъёоноос гадна хослолын тоонуудын бусад олон ашигтай таних тэмдгүүдийг хослуулан шинжилгээгээр олж авсан. Тэдний дундаас хамгийн чухал нь тэгш хэмийн өвөрмөц байдал, энэ нь иймэрхүү харагдаж байна:
Дараах жишээн дээр 5 элементийн хослолын тоог 2 ба (5 2) = 3-аар харьцуулах замаар тэгш хэмийн ижил төстэй байдлын үнэн зөвийг шалгаж болно.
Тэгш хэмийн шинж чанар нь n элементээс m элемент сонгох сонголтуудын тоог тодорхойлсноор үлдсэн (nm) сонгогдоогүй элементүүдийн хослолын тоог нэгэн зэрэг тогтоодог тул тэгш хэмийн ижил төстэй байдал нь тодорхой хослолын утгатай байдаг. Заасан тэгш хэмийг хослолын тооны факториал томъёонд m-ийг (нм) орлуулах замаар нэн даруй олж авна.
Тоонууд болон хосолсон таних тэмдгүүд нь орчин үеийн тооцооллын математикийн янз бүрийн салбарт өргөн хэрэглэгддэг. Гэсэн хэдий ч тэдний хамгийн алдартай хэрэглээ нь Ньютоны бином болон Паскалийн гурвалжинтай холбоотой байдаг.
ХОЁРСОН ТЕОРЕМ
Төрөл бүрийн математик хувиргалт, тооцоолол хийхийн тулд алгебрийн хоёр гишүүний (биномиаль) байгалийн хүчийг олон гишүүнт хэлбэрээр илэрхийлэх чадвартай байх нь чухал юм. Жижиг зэрэглэлийн хувьд хоёр гишүүнийг шууд үржүүлэх замаар хүссэн олон гишүүнтийг хялбархан олж авч болно. Ялангуяа хоёр гишүүний нийлбэрийн квадрат ба кубын дараах томъёог анхан шатны математикийн хичээлээс сайн мэддэг.
Ерөнхий тохиолдолд дурын n зэрэгтэй хоёр гишүүний хувьд олон гишүүнт хэлбэрээр шаардлагатай дүрслэлийг Ньютоны бином теоремоор хангадаг бөгөөд энэ нь дараах тэгшитгэлийг үнэн гэж зарладаг.
Энэ тэгш байдлыг ихэвчлэн Ньютоны бином гэж нэрлэдэг. Түүний баруун талд байгаа олон гишүүнт нь зүүн талын хоёр гишүүний X ба Y n гишүүний үржвэрийн нийлбэрээр үүсгэгдэх ба тэдгээрийн өмнөх коэффициентүүдийг хоёр гишүүн гэж нэрлэдэг бөгөөд индекстэй хослолын тоотой тэнцүү байна. эрх мэдлээсээ олж авдаг. Комбинаторийн шинжилгээнд Ньютоны бином томьёо их алдаршсан тул бином коэффициент ба хослолын тоог ерөнхийд нь ижил утгатай гэж үздэг.
Мэдээжийн хэрэг квадрат ба шоо нийлбэрийн томьёо нь n=2 ба n=3-ын хувьд бином теоремын тусгай тохиолдлууд юм. Илүү өндөр зэрэгтэй (n>3) ажиллахын тулд Ньютоны бином томъёог ашиглах хэрэгтэй. Дөрөвдүгээр зэрэглэлийн бином (n=4)-д хэрэглэхийг дараах жишээгээр харуулав.
Хоёр гишүүний томьёо нь Ньютоноос өмнө Арабын Дорнод ба Баруун Европын дундад зууны үеийн математикчдад мэдэгдэж байсныг тэмдэглэх нь зүйтэй. Тиймээс түүний нийтээр хүлээн зөвшөөрөгдсөн нэр нь түүхэн шударга бус юм. Ньютоны гавъяа нь тэрээр энэ томьёог дурын бодит илтгэгч r-ийн хувьд ерөнхийлсөн бөгөөд энэ нь ямар ч эерэг эсвэл сөрөг рационал ба иррациональ утгыг авч болно. Ерөнхий тохиолдолд Ньютоны ийм бином томъёо нь баруун талдаа хязгааргүй нийлбэртэй бөгөөд ихэвчлэн дараах байдлаар бичигддэг.
Жишээлбэл, r=1/2 экспонентийн эерэг бутархай утгатай бол бином коэффициентүүдийн утгыг харгалзан дараахь өргөтгөлийг олж авна.
Ерөнхий тохиолдолд Ньютоны дурын экспонентийн хоёр гишүүний томьёо нь Маклаурины томъёоны тусгай хувилбар бөгөөд дурын функцийг зэрэглэлийн цуваа болгон тэлэх боломжийг олгодог. Ньютон үүнийг |z|-д харуулсан< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0. Хэрэв бид одоо Z=X/Y гэж тохируулаад зүүн ба баруун талыг Yn-ээр үржүүлбэл дээр дурдсан Ньютоны хоёр гишүүний томьёоны хувилбар гарч ирнэ.
Бүх нийтийн шинж чанартай хэдий ч хоёр гишүүний теорем нь зөвхөн хоёр гишүүний сөрөг бус бүхэл тоонуудын хувьд комбинатор утгаа хадгалдаг. Энэ тохиолдолд үүнийг бином коэффициентийн хэд хэдэн ашигтай таних тэмдгийг батлахад ашиглаж болно. Ялангуяа хослолын тоог дэд тэмдэгтээр болон хоёр индексээр нэгтгэх томъёог дээр дурдсан болно. Алга болсон дээд үсгийн нийлбэрийн таних тэмдгийг Ньютоны бином томъёоноос X = Y = 1 эсвэл Z = 1 гэж оруулснаар хялбархан олж авч болно.
Өөр нэг ашигтай таних тэмдэг нь тэгш ба сондгой тоо бүхий бином коэффициентүүдийн нийлбэрийн тэгш байдлыг тогтоодог. Хэрэв X = 1 ба Y = 1 эсвэл Z = 1 байвал Ньютоны бином томъёоноос шууд гарна.
Эцэст нь, авч үзсэн ижил төстэй байдлын аль алинаас нь бид зөвхөн тэгш эсвэл сондгой тоо бүхий бином коэффициентүүдийн нийлбэрийн ижил төстэй байдлыг олж авдаг.
Үзэж буй ижил төстэй байдал, хослолын тооны тэмдгийн доор индексийг хасах давтагдах дүрэмд үндэслэн хэд хэдэн сонирхолтой харилцааг олж авах боломжтой. Жишээлбэл, дээд үсгийн нийлбэрийн томъёонд бид n-ийг хаа сайгүй (n1)-ээр сольж, гишүүн бүрийн индексийг хасвал дараах хамаарлыг олж авна.
Тэгш ба сондгой тоо бүхий бином коэффициентүүдийн нийлбэрийн томъёонд ижил төстэй аргыг ашиглан жишээлбэл, дараахь хамаарлын үнэн зөвийг нотлох боломжтой.
Өөр нэг ашигтай таних тэмдэг нь дараахь Коши томъёог ашиглан дурын n ба k зэрэгтэй хоёр биномийн тэгш хэмтэй байрлалтай бином коэффициентүүдийн бүтээгдэхүүний нийлбэрийг хялбархан тооцоолох боломжийг танд олгоно.
Энэ томьёоны хүчинтэй байдал нь дараах ижил хамаарлын зүүн ба баруун талд байгаа Z хувьсагчийн дурын m зэрэгт хамаарах коэффициентүүдийн шаардлагатай тэнцүү байдлаас хамаарна.
Онцгой тохиолдолд n = k = m үед тэгш хэмийн ижил төстэй байдлыг харгалзан хоёрын коэффициентүүдийн квадратуудын нийлбэрийн илүү түгээмэл томъёог олж авна.
Комбинаторийн шинжилгээний талаархи өргөн хүрээний ном зохиолоос бином коэффициентийн бусад олон ашигтай таних тэмдгийг олж болно. Гэсэн хэдий ч тэдний хамгийн алдартай практик хэрэглээ нь Паскалийн гурвалжинтай холбоотой юм.
ПАСКАЛИЙН ГУРВАЛЖИН
Паскалийн арифметик гурвалжин нь бином коэффициентуудаас бүрдэх хязгааргүй тооны хүснэгтийг бүрдүүлдэг. Түүний мөрүүд нь дээрээс доош хоёр гишүүний хүчээр эрэмбэлэгддэг. Мөр бүрт хоёр гишүүний коэффициентийг зүүнээс баруун тийш харгалзах хослолын тоонуудын дээд бичээсийн өсөх дарааллаар байрлуулна. Паскалийн гурвалжинг ихэвчлэн тэгш өнцөгт эсвэл тэгш өнцөгт хэлбэрээр бичдэг.
Илүү харагдахуйц бөгөөд нийтлэг зүйл бол хоёр талын коэффициентүүд нь шаталсан, төгсгөлгүй тэгш өнцөгт гурвалжин үүсгэдэг. 4-р зэрэг (n=4) хүртэлх биномуудын анхны фрагмент нь дараах хэлбэртэй байна.
Ерөнхийдөө Паскалийн ижил өнцөгт гурвалжин нь нэмэхийн таних тэмдэг, тооны хослолын тэгш хэм дээр үндэслэсэн бином коэффициентийг тодорхойлох тохиромжтой геометрийн дүрмийг өгдөг. Тодруулбал, нэмэх таних тэмдгийн дагуу аливаа бином коэффициент нь өмнөх эгнээний хоёр коэффициентийн нийлбэр бөгөөд түүнд хамгийн ойр байдаг. Тэгш хэмийн ижил төстэй байдлын дагуу Паскалийн ижил өнцөгт гурвалжин нь биссектрисын хувьд тэгш хэмтэй байна. Тиймээс түүний мөр бүр нь бином коэффициентийн тоон палиндром юм. Заасан алгебрийн болон геометрийн шинж чанарууд нь Паскалийн ижил өнцөгт гурвалжинг хялбархан өргөжүүлж, дурын хүчний хоёртын коэффициентүүдийн утгыг тогтмол олох боломжийг олгодог.
Гэсэн хэдий ч Паскалийн гурвалжны янз бүрийн шинж чанарыг судлахын тулд албан ёсоор илүү хатуу тэгш өнцөгт хэлбэрийг ашиглах нь илүү тохиромжтой. Энэ форматын хувьд үүнийг бином коэффициентийн доод гурвалжин матрицаар тодорхойлдог бөгөөд тэдгээр нь хязгааргүй тэгш өнцөгт гурвалжинг үүсгэдэг. 9-р зэрэг (n=9) хүртэлх биномийн хувьд Паскалийн тэгш өнцөгт гурвалжны анхны фрагмент дараах хэлбэртэй байна.
Геометрийн хувьд ийм тэгш өнцөгт хүснэгтийг Паскалийн тэгш өнцөгт гурвалжны хэвтээ хэвтээ хэвтээ байдлаар гаргаж авдаг. Үүний үр дүнд Паскалийн тэгш өнцөгт гурвалжны хажуу талуудтай параллель тооны цуваа нь Паскалийн тэгш өнцөгт гурвалжны босоо болон диагональ болж хувирч, хоёр гурвалжны хэвтээ тал нь давхцдаг. Үүний зэрэгцээ, Pascal-ийн тэгш өнцөгт гурвалжин нь тэгш өнцөгтийн тэгш хэмийн шинж чанараа алддаг ч бином коэффициентүүдийн нэмэх ба тэгш хэмийн дүрэм хүчинтэй хэвээр байна. Үүнийг нөхөхийн тулд Паскалийн тэгш өнцөгт гурвалжны хэвтээ, босоо, диагональуудын хоёр талын коэффициентүүдийн янз бүрийн тоон шинж чанарыг албан ёсоор шинжлэх нь илүү тохиромжтой.
Паскалийн тэгш өнцөгт гурвалжны хэвтээ тал дээр дүн шинжилгээ хийж эхлэхэд хоёр гишүүнийг дээд тэмдэгтээр нийлбэрлэх томъёоны дагуу n тоотой аль ч эгнээний элементүүдийн нийлбэр 2n-тэй тэнцүү байгааг анзаарахад хялбар байдаг. Үүнээс үзэхэд n тоотой хэвтээ шугамын дээрх элементүүдийн нийлбэр нь (2 n 1) тэнцүү байна. Хэрэв хэвтээ шугам бүрийн элементүүдийн нийлбэрийн утгыг хоёртын тооллын системд бичвэл энэ үр дүн тодорхой болно. Жишээлбэл, n=4-ийн хувьд энэ нэмэлтийг дараах байдлаар бичиж болно.
Энд хоёрын хүчтэй холбоотой хэвтээ чиглэлийн хэд хэдэн сонирхолтой шинж чанарууд байдаг. Хэрэв хэвтээ тоо нь хоёр (n = 2 k) бол түүний бүх дотоод элементүүд (гаднаас бусад) тэгш тоонууд болно. Эсрэгээр, хэвтээ шугамын тоо нь хоёрын зэрэглэлээс нэгээр бага байвал түүний бүх тоо сондгой байх болно (n=2 k 1). Эдгээр шинж чанаруудын үнэн зөвийг n=4 ба n=3 буюу n=8 ба n=7 гэсэн хэвтээ утгууд дахь дотоод хоёрын коэффициентүүдийн паритетыг шалгах замаар шалгаж болно.
Одоо Паскалийн тэгш өнцөгт гурвалжны эгнээний дугаарыг p анхны тоо болгоё. Дараа нь түүний бүх дотоод бином коэффициентүүд p-д хуваагдана. Энэ шинж чанар нь анхны контурын тоонуудын жижиг утгыг шалгахад хялбар байдаг. Жишээлбэл, тав дахь хэвтээ (5, 10, 5) бүх дотоод хоёртын коэффициентүүд нь 5-д хуваагдах нь ойлгомжтой. Ямар ч анхны хэвтээ p тоонд энэ үр дүнг батлахын тулд түүний хоёртын коэффициентийг үржүүлэх томъёог дараах байдлаар бичих хэрэгтэй.
p нь анхны тоо тул m!-д хуваагддаггүй тул бином коэффициентийн бүхэл утгыг баталгаажуулахын тулд энэ томьёоны тоологчийн үлдсэн хүчин зүйлийн үржвэр нь m-д хуваагдах ёстой! Эндээс харахад дөрвөлжин хаалтанд байгаа харьцаа нь натурал N тоо бөгөөд хүссэн үр дүн нь тодорхой болно.
Энэ үр дүнг ашиглан дотоод элементүүд нь өгөгдсөн p анхны тоонд хуваагддаг Паскалийн гурвалжны бүх хэвтээ хэсгүүдийн тоо нь p-ийн зэрэгтэй, өөрөөр хэлбэл n=p k хэлбэртэй болохыг тогтоож болно. Ялангуяа, хэрэв p=3 бол p анхны тоо нь дээр дурдсанчлан 3-р эгнээний бүх дотоод элементүүдийг төдийгүй жишээлбэл, 9-р хэвтээ (9, 36, 84, 126) -ийг хуваана. Нөгөөтэйгүүр, Паскалийн гурвалжинд дотоод элементүүд нь бүгд нийлмэл тоонд хуваагддаг хэвтээ шугамыг олох боломжгүй юм. Үгүй бол ийм хэвтээ шугамын тоо нь түүний бүх дотоод элементүүдийг хуваах нийлмэл тооны анхны хуваагчдын хүч байх ёстой, гэхдээ энэ нь тодорхой шалтгааны улмаас боломжгүй юм.
Үзсэн бодол нь Паскалийн гурвалжны хэвтээ элементүүдийн хуваагдах дараах ерөнхий шалгуурыг томъёолох боломжийг бидэнд олгодог. n тоотой Паскалийн гурвалжны аль ч хэвтээ шугамын бүх дотоод элементүүдийн хамгийн том нийтлэг хуваагч (GCD) нь бусад бүх тохиолдолд n=pk эсвэл 1 бол анхны p тоотой тэнцүү байна.
Дурын 0-ийн хувьд GCD(Cmn) = ( ).< m < n .
Хэвтээ байдлын дүн шинжилгээг дүгнэж хэлэхэд тэдгээрийг бүрдүүлдэг хоёрын коэффициентүүдийн цувралд байдаг өөр нэг сонирхолтой шинж чанарыг авч үзэх нь зүйтэй юм. Хэрэв n тоотой аливаа хэвтээ шугамын бином коэффициентийг 10 тооны дараалсан зэрэглэлээр үржүүлж, эдгээр бүх үржвэрийг нэмбэл үр дүн нь 11 n болно. Энэхүү үр дүнгийн албан ёсны үндэслэл нь X = 10 ба Y = 1 (эсвэл Z = 1) утгыг Ньютоны бином томъёонд орлуулах явдал юм. Дараах тоон жишээ нь n=5 хувьд энэ шинж чанарын биелэлтийг харуулж байна.
Паскалийн тэгш өнцөгт гурвалжны босоо тэнхлэгийн шинж чанарын шинжилгээг тэдгээрийн бүрдүүлэгч элементүүдийн бие даасан шинж чанарыг судлахаас эхэлж болно. Албан ёсоор, босоо m бүр нь тогтмол дээд тэмдэгт (m) ба доод тэмдгийн өсөлт бүхий бином коэффициентуудын дараах төгсгөлгүй дарааллаар үүсгэгддэг.
Мэдээжийн хэрэг, m=0 үед нэгийн дараалал, m=1 үед натурал тооны цуваа үүснэ. m=2 үед босоо нь гурвалжин тооноос бүрдэнэ. Гурвалжин тоо бүрийг тэгш талт гурвалжин хэлбэрээр хавтгай дээр дүрсэлж болох бөгөөд энэ нь даамын самбарт байрлуулсан дурын объектуудаар (цөм) дүүрсэн байдаг. Энэ тохиолдолд гурвалжин тоо бүрийн утга T k нь төлөөлөх цөмийн тоог тодорхойлох ба индекс нь түүнийг илэрхийлэхэд хэдэн эгнээ цөм шаардлагатайг харуулдаг. Жишээлбэл, 4 анхны гурвалжин тоо нь цөмийн "@" тэмдгийн харгалзах тооны дараах тохиргоог илэрхийлнэ.
Үүнтэй адилаар натурал тоо, ерөнхийдөө ердийн олон өнцөгтийг тогтмол дүүргэх замаар үүссэн олон өнцөгт дүрст тоог квадрат болгох замаар олж авсан S k квадрат тоонуудыг авч үзэх боломжтой гэдгийг тэмдэглэх нь зүйтэй. Ялангуяа эхний 4 квадрат тоог дараах байдлаар илэрхийлж болно.
Паскалийн гурвалжны босоо тэнхлэгийн шинжилгээнд буцаж ирэхэд m=3 дахь дараагийн босоо нь тетраэдр (пирамид) тоогоор дүүрсэн болохыг тэмдэглэж болно. Ийм P k тоо бүр нь тетраэдр хэлбэрээр байрлуулж болох цөмийн тоог зааж өгдөг ба индекс нь гурван хэмжээст орон зайд дүрслэхийн тулд хэдэн хөндлөн гурвалжин эгнээний эгнээ шаардлагатай байгааг тодорхойлдог. Энэ тохиолдолд бүх хэвтээ давхаргууд нь дараалсан гурвалжин тоогоор илэрхийлэгдэх ёстой. Паскалийн гурвалжны m>3-ийн дараах босоо хэсгүүдийн элементүүд нь хавтгайд эсвэл гурван хэмжээст орон зайд харааны геометрийн тайлбаргүй, харин гурвалжин ба тетраэдийн тооны олон хэмжээст аналогуудтай албан ёсоор тохирч байгаа гипертетраедал тоонуудын цувралыг бүрдүүлдэг.
Паскалийн гурвалжны босоо тооны цувралууд нь бие даасан хэлбэрийн шинж чанартай байдаг ч тэдгээрийн хувьд хослолын тоог дэд тэмдэгтээр нэгтгэх томъёог ашиглан анхны элементүүдийн утгуудын хэсэгчилсэн нийлбэрийг ижил аргаар тооцоолох боломжтой. . Паскалийн гурвалжинд энэ томьёо нь дараах геометрийн тайлбартай байна. Аливаа босоо тэнхлэгийн n дээд бином коэффициентийн утгуудын нийлбэр нь нэг мөр доор байрлах дараагийн босоо хэсгийн элементийн утгатай тэнцүү байна. Энэ үр дүн нь гурвалжин, тетраэдр болон гипертетраэдийн тоонуудын геометрийн бүтэцтэй тохирч байна, учир нь ийм тоо бүрийн дүрслэл нь доод эрэмбийн тоог илэрхийлэх үндсэн давхаргуудаас бүрддэг. Ялангуяа n-р гурвалжин тоо T n-ийг түүний шугаман давхаргыг төлөөлсөн бүх натурал тоонуудыг нийлбэрээр гаргаж болно.
Үүний нэгэн адил, хэвтээ үндсэн давхаргыг бүрдүүлдэг эхний n гурвалжин тооны дараах нийлбэрийг тооцоолох замаар тетраэдр Pn тоог олоход хэцүү биш юм.
Паскалийн тэгш өнцөгт гурвалжны хэвтээ ба босоо байдлаас гадна элементүүдийн диагональ эгнээг ажиглах боломжтой бөгөөд тэдгээрийн шинж чанарыг судлах нь бас сонирхолтой юм. Энэ тохиолдолд ихэвчлэн буурах ба өсөх диагональуудыг ялгадаг. Доош диагональууд нь Паскалийн тэгш өнцөгт гурвалжны гипотенузтай параллель байна. Эдгээр нь хоёр индексийн өсөлттэй хоёрын коэффициентүүдийн цуваагаар үүсгэгддэг. Тэгш хэмийн онцлогоос шалтгаалан буурах диагональууд нь Паскалийн гурвалжны харгалзах босоо эгнээтэй элементүүдийн утгуудад давхцаж байгаа тул дээр дурдсан бүх шинж чанаруудыг давтана. Заасан захидал харилцааг босоо тэгийг тооцохгүй бол буурах диагональ ба босоо элементүүдийн утгуудын n тоотой давхцах замаар ажиглаж болно.
Өсөх диагональууд нь Паскалийн тэгш өнцөгт гурвалжны гипотенузтай геометрийн перпендикуляр тооны цуваа үүсгэдэг. Тэдгээр нь доод талын бууралт ба дээд үсгийн өсөлт бүхий бином коэффициентүүдээр дүүргэгдсэн байдаг. Ялангуяа 7 дээд өгсөх диагональ нь дараачийн тэгийг харгалзахгүйгээр дараах тоон дарааллыг бүрдүүлнэ.
Ерөнхийдөө, өсөх диагональ тоо n нь дараах бином коэффициентүүдийг агуулдаг бөгөөд тус бүрийн индексийн нийлбэр нь (n1) тэнцүү байна:
Хосолсон тоонуудын нэмэлт таних тэмдгийн ачаар диагональ элемент бүр нь өмнөх хоёр өсөх диагональаас индекст харгалзах хоёр элементийн нийлбэртэй тэнцүү байна. Энэ нь өмнөх хоёр диагональаас зэргэлдээх хэвтээ элементүүдийн хоёр нийлбэрээр дараагийн өгсөх диагональ бүрийг байгуулах боломжийг олгож, диагональ дагуу Паскалийн гурвалжныг хязгааргүй тэлэх боломжийг олгоно. Паскалийн гурвалжны дараах фрагмент нь 6 ба 7 дугаартай диагональуудын дагуу өсөх диагональ 8 тоог бүтээж байгааг харуулж байна.
Барилгын энэ аргын хувьд 3-аас эхлэн аливаа өсөх диагональын элементүүдийн нийлбэр нь өмнөх хоёр өсөх диагональуудын элементүүдийн нийлбэртэй тэнцүү байх бөгөөд эхний 2 диагональ нь зөвхөн нэг элементээс бүрдэх болно. Үүний 1. Харгалзах тооцооны үр дүн нь дараах тоон цувааг үүсгэх бөгөөд үүний дагуу Паскалийн тэгш өнцөгт гурвалжны өсөх диагональуудын авч үзсэн шинж чанарын үнэн зөвийг шалгаж болно.
Эдгээр тоонуудад дүн шинжилгээ хийснээр та ижил төстэй хуулийн дагуу Фибоначчийн тоонуудын сайн мэддэг дараалал үүссэн бөгөөд дараагийн тоо бүр өмнөх хоёр тоонуудын нийлбэртэй, эхний хоёр тоо нь 1-тэй тэнцүү байгааг харж болно.
Тиймээс бид дараах чухал дүгнэлтийг гаргаж болно: Паскалийн гурвалжны элементүүдийн диагональ нийлбэрүүд нь Фибоначчийн дарааллыг бүрдүүлдэг. Энэхүү өмч нь Паскалийн гурвалжны өөр нэг сонирхолтой шинж чанарыг бий болгох боломжийг бидэнд олгодог. Фибоначчийн томьёог рекурсив байдлаар өргөжүүлбэл, эхний n Фибоначчийн тооны нийлбэр (F n+2 1) тэнцүү болохыг батлахад хялбар болно.
Иймд дээд n диагональыг дүүргэх хоёртын коэффициентүүдийн нийлбэр нь мөн (F n+2 1) тэнцүү байна. Паскалийн гурвалжны эхний n диагональуудын нийлбэр нь (n+2) тоогоор диагональ дээр байрлах бином коэффициентүүдийн нийлбэрээс 1-ээр бага байна.
Эцэст нь хэлэхэд Паскалийн гурвалжны хэвтээ, босоо, диагональуудын авч үзсэн шинж чанарууд нь эхлээд харахад нийтлэг зүйлгүй математикийн янз бүрийн талуудыг хооронд нь холбох асар олон янзын боломжийг шавхдаггүй гэдгийг тэмдэглэх нь зүйтэй. Ийм ер бусын шинж чанарууд нь Паскалийн гурвалжныг хамгийн төгс тоон системүүдийн нэг гэж үзэх боломжийг бидэнд олгодог бөгөөд тэдгээрийн бүх чадварыг жагсаах боломжгүй бөгөөд хэт үнэлэхэд хэцүү байдаг.
Паскалийн гурвалжинг ашиглан хослолын тоог тооцоолох алгоритмыг доор үзүүлэв.
Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) For i = 0 to n TT (0, i) = 1 TT (i, i) = 1 Дараа нь i = 2 To n хувьд j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Дараагийн Дараагийн SochTT = TT (n, k) Төгсгөлийн функц
Хэрэв та хослолын тоог олон удаа тооцоолох шаардлагатай бол Паскалийн гурвалжинг нэг удаа байгуулж, дараа нь массиваас өгөгдлийг хүлээн авах нь илүү тохиромжтой байж магадгүй юм.
Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Дараа нь BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) Төгсгөлийн функц Хувийн дэд төгсгөлTT () ReDim TT (0, 0) Төгсгөлийн дэд Хувийн дэд BuildTT (ByVal эхлэл бүхэл тоогоор, ByVal төгсгөл нь бүхэл тоогоор) Dim i бүхэл тоогоор Dim j As Integer ReDim Preserve TT (төгсгөл, төгсгөл) For i = start to end TT (0, i) = 1 TT (i, i) = 1 Next If end< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Эхлээд та CreateTT процедурыг дуудах хэрэгтэй. Дараа нь та SochTT функцийг ашиглан хослолын тоог олж авах боломжтой. Хэрэв танд гурвалжин хэрэггүй болсон бол TerminateTT процедурыг дуудна уу. Дээрх кодонд SochTT функцийг дуудахдаа гурвалжин шаардлагатай түвшинд хараахан дуусаагүй бол BuildTT процедурыг ашиглан дуусгана. Дараа нь функц нь TT массивын хүссэн элементийг аваад буцаана.
Dim X () Бүхэл тоо Бүдэг тоологч () Бүхэл тоогоор Dim K Бүхэл тоогоор Dim N Бүхэл тоогоор Нийтийн дэд Soch() Dim i Бүхэл тоогоор N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K" ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c Бүхэл тоогоор) Dim i Бүхэл тоогоор Dim j Бүхэл тоогоор Dim n1-ээр Бүхэл тоо Dim Out() Бүхэл тоогоор Dim X1() Бүхэл тоо Хэрэв c = K Дараа нь ReDim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 j = 1-д N бол X1(j)<>0 Дараа нь n1 = n1 + 1 Хэрэв n1 = Counter(i) бол Out(i) = X1(j) X1(j) = 0 Exit For End If Next txtOut.Text = txtOut.Text & CStr(Out(i)) Next txtOut.Text = txtOut.Text & vbCrLf Бусад Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
БАЙГАЛИЙН ТООНЫ ХОЛБООНЫ ЖАГСААЛТ
Практик олон асуудлыг шийдэхийн тулд зөвхөн тэдгээрийн тоог тодорхойлох биш, өгөгдсөн хязгаарлагдмал олонлогийн элементүүдээс олж авч болох тогтмол кардинал байдлын бүх хослолыг жагсаах шаардлагатай. Аливаа хязгаарлагдмал олонлогийн элементүүдийг бүхэл тоогоор дугаарлах үргэлж байдаг боломжийг харгалзан ихэнх тохиолдолд натурал тооны хослолыг тоолох алгоритмыг ашиглахыг хязгаарлахыг зөвшөөрдөг. Тэдгээрийн хамгийн энгийн бөгөөд энгийн нь натурал тоонуудын хослолыг жагсаах алгоритм юм толь бичгийн дараалал.
Энэхүү алгоритмыг албан ёсоор тайлбарлахын тулд m элементийн бүх хослолыг жагсаасан байх ёстой үндсэн багц нь 1-ээс n хүртэлх дараалсан натурал тоонуудыг үүсгэдэг гэж үзэх нь тохиромжтой. Дараа нь m-ийн дурын хослол Захиалга хийсний үр дүнд ийм хослолын векторын байрлал тус бүрийн утга нь дээрээс болон доороос хязгаарлагдмал утгатай болж хувирдаг. Үг зүйн алгоритм нь лексиграфийн хувьд хамгийн жижиг вектороос эхлэн ийм хослол векторуудыг дараалан үүсгэдэг бөгөөд бүх байрлал нь индекстэй тэнцүү элементүүдийн дараах боломжит хамгийн бага утгыг агуулна. Хязгаарлалтдаа хүрээгүй байгаа хамгийн баруун талын элементийг олохын тулд дараагийн хослолын вектор бүр элементүүдийг зүүнээс баруун тийш сканнердсаны дараа одоогийнхоос үүсдэг. Ийм элементийн утгыг 1-ээр нэмэгдүүлэх шаардлагатай. Түүний баруун талд байгаа элемент бүрд хамгийн бага боломжит утгыг оноож өгөх ёстой бөгөөд энэ нь зүүн талын хөршөөсөө 1 дахин их байна. Эдгээр өөрчлөлтүүдийн дараа хослолын дараагийн вектор нь дараах элементийн найрлагатай болно. Тиймээс дараагийн хослолын вектор нь өмнөх (j1) элементүүдийн утгууд нь ижил утгатай, j байрлал дахь элементийн утга өмнөхөөсөө 1-ээр их байх тул дараагийн хослолын вектор нь өмнөхөөсөө том байх болно. . Толь бичгийн дарааллыг нэмэгдүүлэхийн заасан хамаарал нь алгоритмын бүх давталтуудад хангагдана. Үр дүн нь лексиграфийн хамгийн том хослолын вектороор төгсдөг өсөн нэмэгдэж буй үг зүйн дараалал бөгөөд бүх байрлал дахь элементүүд дараах хамгийн их утгатай байна. Үзэж буй толь бичгийн алгоритмыг дараах жишээн дээр харуулсан бөгөөд энд n=6 анхны натурал тооны бүх 15 хослолыг m=4 тоогоор, өөрөөр хэлбэл үндсэн үүсгэгчийн бүх боломжит 4 элементтэй дэд олонлогуудыг үгзүйн дарааллаар жагсаах шаардлагатай болно. 6 элементээс (1, 2, 3, 4, 5, 6) багц. Тооцооллын үр дүнг дараах хүснэгтэд үзүүлэв. Энэ жишээнд хослол векторуудын байрлал дахь тоонуудын зөвшөөрөгдөх хамгийн том утгууд нь 3, 4, 5, 6 байна. Үр дүнг тайлбарлахад хялбар болгохын тулд хослол вектор бүрт хамгийн баруун талын элемент байна. хамгийн дээд хэмжээндээ хараахан хүрээгүй байгаа гэдгийг онцлон тэмдэглэв. Нийлмэл векторуудын тоон индексүүд нь тэдгээрийн тоог толь бичгийн дарааллаар тодорхойлдог. Ерөнхий тохиолдолд n элементийн аль ч хослолын m-ийн lexigraphic тоог N-ийг дараах томъёогоор тооцоолж болох бөгөөд энд гоо сайхны шалтгааны улмаас хослолын тоог тэмдэглэхэд Appel бэлгэдлийг ашигладаг. Тодруулбал, m=4-ийн n=6 элементийн хослолын дугаарыг (1, 3, 4, 6) толь бичгийн дарааллаар энэ томьёог ашиглан хийсэн дараах тооцоолол нь дээр дурдсан жишээтэй тохирч байгаа N=8 үр дүн гарна. Ерөнхийдөө хоёр индексийн хослолын тоонуудын нийлбэрийн таних тэмдгийг ашиглан бид энэ томьёог ашиглан тооцоолохдоо үг зүйн хувьд хамгийн бага хослолын тоо (1, … i, … m) үргэлж тэнцүү байх болно гэдгийг харуулж чадна. 1: Энэ томьёог ашиглан тооцоолохдоо үг зүйн хувьд хамгийн том хослолын тоо (m, … nm+i, … n) нь n элементийн хослолын тоо m-тэй тэнцүү байх нь ойлгомжтой. Тайлбар бичгийн хослолын тоог тооцоолох томъёог урвуу асуудлыг шийдвэрлэхэд ашиглаж болох бөгөөд энд та хослол векторыг толь бичгийн дарааллаар нь тоогоор нь тодорхойлох хэрэгтэй. Ийм урвуу асуудлыг шийдэхийн тулд үүнийг тэгшитгэл хэлбэрээр бичих ёстой бөгөөд үүнд хүссэн хослолын векторын элементүүдийн үл мэдэгдэх бүх утгууд (C 1, ... C i, ... C m) байх ёстой. ) нь түүний баруун талын хослолуудын тоонд төвлөрч, хослолын тооны мэдэгдэж буй L ялгаа нь m бүрийн n элементийн зүүн талд, шаардлагатай N хослолын тоогоор бичигдсэн болно. Энэхүү тэгшитгэлийн шийдлийг дараах "шуналтай" алгоритмаар хангадаг бөгөөд давталтын явцад хүссэн хослолын векторын элементүүдийн утгыг дараалан сонгоно. Эхний давталт дээр C 1-ийн хамгийн бага боломжтой (хязгаарлалтуудын хүрээнд) утгыг сонгосон бөгөөд энэ үед баруун талын эхний гишүүн нь L-ээс хэтрэхгүй хамгийн их утгатай байна. Одоо L-ийн зүүн талыг сонгосон C 1 утгатай баруун талд байгаа хослолуудын эхний тоогоор багасгаж, хоёр дахь давталт дээр C 2-ийн утгыг ижил төстэй байдлаар тодорхойлно. Үүний нэгэн адил, хүссэн хослолын C i бусад бүх элементүүдийн утгыг сонгохын тулд дараагийн бүх давталтуудыг хийх ёстой бөгөөд C m сүүлчийн элемент хүртэл: Тодорхой шалтгааны улмаас C m-ийн сүүлчийн элементийн утгыг түүний хослолын тоо нь L-ийн зүүн талын үлдэгдэл утгатай тэнцүү байх үндсэн дээр тодорхойлж болно. C m хослолын сүүлчийн элементийн утгыг түүний боломжит утгыг тоолохгүйгээр илүү энгийнээр олох боломжтой гэдгийг тэмдэглэх нь зүйтэй. Харгалзан үзсэн алгоритмын давталтын хэрэгжилтийг дараах жишээгээр дүрсэлсэн бөгөөд n=6 ба m=4 бол N=8 тоо бүхий хослолуудыг үг зүйн дарааллаар тодорхойлох шаардлагатай. Тог зүйн дарааллаар өгөгдсөн тоогоор хослолыг тодорхойлох алгоритмын чадварыг янз бүрийн чиглэлд ашиглаж болно. Ялангуяа хослолыг толь бичгийн дарааллаар жагсаахдаа өмнө нь олж авсан хослолыг буцааж өгөх шаардлагатай бөгөөд зөвхөн түүний тоог л мэдэхэд хангалттай. Нэмж дурдахад дурын дарааллаар хослол үүсгэх боломжтой болсон бөгөөд энэ нь тэдгээрийн лексиграфийн дугааруудын дур зоргоороо өгөгдсөн дарааллаар зохицуулагддаг. Одоо бид лексикографийн дарааллаар хослол үүсгэх алгоритмыг танилцуулж байна. 2 for i:= 1 to k хийх A[i] := i; 5 бичиж эхлэх(A, …, A[k]); 6 хэрэв A[k] = n бол p:= p 1 өөр p:= k; 8 хувьд i:= k доош p хийх A[i] := A[p] + i p + 1 ДАВТАГДАХ ЭЛЕМЕНТТЭЙ ХОСЛОЛТ Бүх элементүүд өөр өөр байдаг сонгодог хослолоос ялгаатай нь давталттай хослол нь төгсгөлтэй олонлогийн элементүүдийн эрэмбэлэгдээгүй сонголтыг бүрдүүлдэг бөгөөд энд дурын элемент хязгааргүй олон удаа гарч ирдэг бөгөөд заавал нэг хуулбарт байх албагүй. Энэ тохиолдолд элементүүдийн давталтын тоог ихэвчлэн зөвхөн хослолын уртаар хязгаарладаг бөгөөд дор хаяж нэг элементээр ялгаатай хослолуудыг өөр гэж үздэг. Жишээлбэл, 1, 2, 3-р багцаас өөр 4 тоог сонгосноор та давталттай дараах 15 хослолыг үүсгэж болно. 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Ерөнхийдөө дурын төрлийн n элементийг сонгох замаар давталттай хослолыг үүсгэж болно. Гэсэн хэдий ч тэдгээрийг 1-ээс n хүртэлх дараалсан натурал тоонуудтай үргэлж холбож болно. Дараа нь энэ муж дахь m сонголтоор өөр өөр тооны дурын хослолыг вектор хэлбэрээр бичиж, тэдгээрийг зүүнээс баруун тийш буурахгүй дарааллаар байрлуулж болно. Мэдээжийн хэрэг, тэмдэглэгээний энэ хэлбэрийн хувьд хязгааргүй давтагдах боломжтой тул хөрш зэргэлдээ элементүүд тэнцүү байж болно. Гэсэн хэдий ч n элементийн m-ээр давталттай хослол вектор бүрийг (n+m−1) элементийн хослолын вектортой m-ээр холбож болох бөгөөд үүнийг дараах байдлаар байгуулна. f векторын элементүүдийн аль ч утгын хувьд C векторын элементүүд өөр байх нь тодорхой бөгөөд утгуудын дарааллыг 1-ээс (n+m1) нэмэгдүүлэх дарааллаар хатуу эрэмбэлдэг. f ба C хослолын векторуудын элементүүдийн хооронд нэг нэгээр нь харгалзах нь n элементийн давталт бүхий хослолуудыг m-ээр системтэйгээр жагсаах дараах энгийн аргыг санал болгох боломжийг бидэнд олгодог. Жишээлбэл, m-ийн (n+m1) элементийн бүх C хослолыг толь бичгийн дарааллаар жагсааж, тэдгээрийн элементүүдийг f давталттай хослолын харгалзах элемент болгон дараалан дараах томьёог ашиглан жагсаах шаардлагатай. Үүний үр дүнд элементүүдийн давталт бүхий хослолын векторуудын дараалал үүсдэг бөгөөд тэдгээр нь элементүүдийн давталтгүйгээр харгалзах хослолуудыг жагсаах замаар үүсгэсэн дарааллаар байрладаг. Тодруулбал, 4 оронтой давталттай 1, 2, 3-ын 3 оронтой хослолын дээрх дарааллыг олж авахын тулд 1,2,3,4,5-ын 6 оронтой давталтгүйгээр бүх хослолыг үг зүйн дарааллаар жагсаах шаардлагатай. ба 6 нь тус бүр 4 оронтой бөгөөд тэдгээрийг заасны дагуу хөрвүүлнэ. Дараах жишээнд (1,3,4,6) хослолыг толь бичгийн 8 дугаартай хөрвүүлснийг харуулав. Элементүүдийн давталттай болон давталтгүй хослолуудын хоорондох нэг нэгээр нь харгалзах нь тэдний багц нь адилхан хүчтэй гэсэн үг юм. Иймд ерөнхий тохиолдолд n элементийн m-ээр давтагдсан хослолын тоо нь (n+m1) элементийн m-ээр давтагдахгүй хослолын тоотой тэнцүү байна. Давталттай f ба давталтгүй C хослолын тоог ижил бэлгэдлийг ашиглан энэ тэгшитгэлийг дараах байдлаар бичиж болно. Дээр дурдсан жишээний хувьд n=3 ба m=4 бол давталтын хослолын тоо 15-тай тэнцүү байх бөгөөд энэ нь шууд жагсаалтын үр дүнтэй давхцаж байгааг шалгахад хялбар байдаг. Сонгодог хувилбараас ялгаатай нь n ба m давталттай хосолсон параметрүүдийн утгууд нь хоорондоо шууд хамааралгүй тул тэдгээрийн эерэг утгуудын аль ч хослолын хувьд f(n,m)>0 байна гэдгийг тэмдэглэх нь зүйтэй. Харгалзах хилийн нөхцлийг (n+m1) ба (n1) эсвэл (n+m1) ба m-ийн утгуудын тэгшитгэлээр тодорхойлно. Хэрэв m нь 1-тэй тэнцүү бол элементүүдийг давтах боломжгүй тул n>0-ийн эерэг утгын хувьд дараахь тэгшитгэл үнэн байх болно. Нэмж дурдахад, n ба m-ийн эерэг утгуудын хувьд давтагдах хослолын тооны хувьд дараах давталтын хамаарал хүчинтэй бөгөөд энэ нь элементийн давталтгүй хослолын тоог нэмэхтэй адил юм. Үнэн хэрэгтээ энэ нь зүүн, баруун талдаа давталтгүйгээр тохирох тооны хослолыг албан ёсоор орлуулахад заасан нэмэлт тэмдэг болж хувирдаг. Боломжит давталтын хамаарлыг хүчин зүйлийн бүтээгдэхүүнийг тооцоолоход цаг хугацаа шаардсан үйлдлүүдийг арилгах, илүү энгийн нэмэх үйлдлээр солих нь чухал үед давталттай хослолуудын тоог үр дүнтэй тодорхойлоход ашиглаж болно. Энэ тохиолдолд f(n,m)-ийн утгыг тооцоолохын тулд та f(1,m) ба f(i,1) хэлбэрийн нөхцлийн нийлбэрийг олж авах хүртлээ энэ давталтын хамаарлыг ашиглахад л хангалттай. n-ээс 1 хүртэлх утгыг авна. Хэмжигдэхүүний тодорхойлолтоор ийм нэр томъёо нь 1 ба i-тэй тэнцүү байна. Дараах жишээ нь n=3 ба m=4 тохиолдолд энэхүү хувиргах аргыг ашиглахыг харуулж байна. ХОЁРДУГААР ХОСОЛЦООНЫ ЖАГСААЛТ Комбинацыг техник хангамж эсвэл ассемблер хэлээр програмчлалд хэрэгжүүлэхдээ хосолсон бичлэгийг хоёртын форматаар боловсруулах чадвартай байх нь чухал. Энэ тохиолдолд m-ийн n элементийн дурын хослолыг n-битийн хоёртын тоо (B n,...B j,...B 1) хэлбэрээр зааж өгөх ёстой бөгөөд энд m нэгж цифрүүд нь m-ийн элементүүдийг заана. хослол, үлдсэн (нм) цифрүүд нь тэг утгатай байна. Мэдээжийн хэрэг, тэмдэглэгээний энэ хэлбэрийн хувьд өөр өөр хослолууд нь 1-ийн цифрүүдийн зохион байгуулалтад ялгаатай байх ёстой бөгөөд n-битийн хоёртын олонлогт m нэг эсвэл (nm) тэгийг цэгцлэх зөвхөн C(n,m) арга байдаг. Жишээлбэл, дараах хүснэгтэд дурын олонлогийн 4 элементийн (E 1 , E 2 , E 3 , E 4 ) бүх хослолыг 2-оор 4 битийн хоёртын тоогоор хангадаг ийм бүх 6 хоёртын хослолыг жагсаав. Ерөнхий тохиолдолд ийм хоёртын хослолыг тоолох ажил нь m нэг ба (nm) тэг битийн өөр өөр зохион байгуулалттай бүх n-битийн хоёртын олонлогуудыг системтэй хайхад ирдэг. Энгийн хэлбэрээр ийм хайлтыг зэргэлдээх битүүдийг шилжүүлэн суулгах янз бүрийн аргаар (transpositive-shift алгоритмууд) хэрэгжүүлдэг. Эдгээр нь давтагдах алгоритмууд бөгөөд тэдгээрийн нэр нь алхам бүрт гүйцэтгэсэн үйлдлийн мөн чанарыг илэрхийлдэг. Transpositive-shift алгоритмуудын давталттай процедур нь хоёртын олонлогоос эхэлдэг хоёртын хослолуудын дарааллыг бүрдүүлдэг бөгөөд бүх нь бага эрэмбийн цифрүүдэд (баруун талд) төвлөрч, бүх 1-үүд өндөр эрэмбийн цифрүүдэд (баруун талд) төвлөрдөг. зүүн талд): Эхний болон эцсийн хослолд таарч байгаа боловч эдгээр дараалал нь завсрын хоёртын олонлогуудыг жагсаасан дарааллаар ялгаатай байна. Гэсэн хэдий ч бүх тохиолдолд дараагийн хоёртын хослол бүр нь өмнөхөөс нь шилжүүлэн суулгах, шилжүүлэх үйлдлийг гүйцэтгэсний үр дүнд үүсдэг. Үүний зэрэгцээ янз бүрийн транспозитив шилжих алгоритмууд нь шилжүүлэн суулгах хос бит, шилжүүлэхэд зориулсан бүлэг битийг сонгох арга замаар ялгаатай байдаг. Зүүн ба баруун шилжилттэй шилжүүлэн суулгах алгоритмын хувьд энэ онцлогийг доор авч үзнэ. Зүүн шилжилттэй шилжүүлэн суулгах алгоритмд алхам бүрт дараагийн хоёртын хослолыг одоогийнхоос хамгийн зүүн талын 01 цифрийг 10 (шилжүүлэлт) -ээр сольж, тэргүүлэх нэгжийн цифрүүдийн бүлгийг хэрэв байгаа бол ойролцоо шилжүүлэх замаар олж авна. шилжүүлгийн дараа олж авсан 10 хос. Хэрэв энэ тохиолдолд одоогийн хоёртын хослолын хамгийн өндөр цифрүүдэд нэгж байхгүй бол энэ алхамд шилжүүлсний дараа тэргүүлэх нэгжийг авсан ч шилжилт хийгдэхгүй. Шилжилтийн дараа олж авсан 10-р хосын өмнөх хамгийн чухал битүүдэд тэг байхгүй үед шилжилтийг хийхгүй. Энэ алгоритмын дараалсан хоёр давталтыг гүйцэтгэх дараах жишээн дээр авч үзсэн үйлдлүүдийг харуулсан бөгөөд нэг давталтад (15) зөвхөн шилжүүлэг (T"), нөгөө давталт дээр (16) шилжүүлэг нь шилжилтээр нэмэгддэг. T"+S"): Баруун тийш шилжих шилжилтийн алгоритмд үзэл баримтлалын хувьд ижил төстэй алхмуудыг алхам бүр дээр гүйцэтгэдэг. Зөвхөн шилжүүлэлт нь 01-ийн баруун талын битүүдийг 10-аар (хамгийн зүүн талынхын оронд) сольж, дараа нь баруун талд байгаа бүх битийг хамгийн бага ач холбогдол бүхий битүүд рүү шилжүүлдэг. Өмнөх шигээ баруун тийш шилжүүлэх боломжтой нэгжүүд байгаа тохиолдолд л ээлжийг гүйцэтгэдэг. Энэ алгоритмын дараалсан хоёр давталтыг гүйцэтгэх дараах жишээн дээр авч үзсэн үйлдлүүдийг харуулсан бөгөөд нэг давталтад (3) зөвхөн шилжүүлэг (T"), нөгөө давталт дээр (4) шилжүүлэг нь шилжилтээр нэмэгддэг. T"+S"): Хоёртын хослолыг 2-р суурь тооллын системд бүхэл тоо гэж тайлбарлавал хоёр алгоритмын давталтыг нэмж бичих боломжтой гэдгийг тэмдэглэх нь зүйтэй ,…B" j , …B" 1), бүхэл тоо нэмэх үйлдлийг дараах нэмэлт томъёог ашиглан одоогийн хослолоос (B n,…B j,…B 1) үргэлж авч болно. Энэхүү нэмэлт томъёонд f ба t хоёрын зэрэглэлийн илтгэгч нь одоогийн хоёртын хослолын доод эрэмбийн тэг цифрүүдийн тоо болон тэдгээрийн зүүн талд байгаа нэг эгнээний тоог тус тус илэрхийлнэ. Жишээлбэл, n=6 цифрийн 4 дэх хоёртын хослолын хувьд (001110) f =1 ба t =3. Тиймээс 5-р давталт дээр нэмэлт томъёог ашиглан дараагийн хоёртын хослолыг тооцоолох нь шилжүүлэн суулгах, шилжүүлэх үйлдлийг гүйцэтгэхтэй тэнцэх дараах үр дүнг өгнө. Зүүн ба баруун шилжилт бүхий шилжүүлэн суулгах алгоритмуудын харьцуулсан дүн шинжилгээ хийхдээ тэдгээрийн давталтаар үүсгэсэн хоёртын хослолуудын дарааллыг харьцуулахыг зөвлөж байна. Дараах хүснэгтэд зүүн (TSL) ба баруун (TSR) шилжих алгоритмуудаар олж авсан 2-ын 4 элементийн хоёртын хослолын хоёр дарааллыг харуулав. Эдгээр 2 дарааллыг харьцуулж үзвэл тэдгээр нь урвуу толин тусгал болохыг харж болно. Энэ нь тэдгээрийн дарааллын эсрэг талын төгсгөлүүдээс ижил зайд байрладаг аливаа хоёр хоёртын хослолууд нь бие биенийхээ толин тусгал дүрс, өөрөөр хэлбэл тэдгээрийн аль нэг дэх битүүдийн индексжүүлэлт эсрэгээр давхцдаг гэсэн үг юм. Жишээлбэл, TSL дарааллын эхнээс хоёр дахь хоёртын загвар (0101) нь TSR дарааллын төгсгөлөөс хоёр дахь нь хоёртын хэв маягийн (1010) толин тусгал дүрс юм. Ерөнхийдөө нэг дарааллын i тоотой аливаа хоёртын хослол нь өөр дарааллын тоотой (ni+1) хоёртын хослолын толин тусгал дүрс юм. Эдгээр дарааллын хоорондох энэхүү хамаарал нь хоёртын хослолыг тоолох хоёр алгоритм дахь шилжүүлэн суулгах, шилжүүлэх үйлдлүүдийн тэгш хэмтэй байдлын үр дагавар юм. Хоёртын форматыг элементийн давталттай хослолыг бичихэд ашиглаж болно гэдгийг тэмдэглэх нь зүйтэй. Үүнийг хийхийн тулд дараах байдлаар бүтээгдсэн давталт болон хоёртын хослол бүхий хослолуудын хооронд нэг нэгээр нь захидал харилцааг бий болгох шаардлагатай. Үүсгэх олонлогийн n элементээс m сонголттой өөр элемент сонгох замаар олж авсан давталттай дурын хослол байг. Хүссэн тохирохыг бий болгохын тулд эхлээд бүрдүүлэх багцын бүх элементүүдийг (муур) хослолд нэмж, дараа нь үүссэн холболтыг (эрэмбэлэх) бүх ижил элементүүдийг зэрэгцүүлэн эрэмбэлэх хэрэгтэй. Үр дүн нь (n+m) элементүүдийн дараалал бөгөөд n бүлэг ижил элементтэй байна. Элементүүдийн хооронд нийт (n+m1) цоорхой байх ба тэдгээрийн хооронд ижил элементүүдийн бүлгүүдийн хооронд (n1) зай, бүлэг доторх элементүүдийн хооронд m зай байна. Тодорхой болгохын тулд заасан зайд "|" тэмдгийг байрлуулж болно. мөн үүний дагуу. Хэрэв бид одоо 1-ийг бүлгүүдийн хоорондох зайд (|), 0-ийг бусад бүх орон зайд () тааруулбал бид хоёртын хослолыг авна. Энэ нь (n+m1) битийн хоёртын олонлогоор үүсгэгддэг бөгөөд (n1) нь нэг ба м тэг бит бөгөөд тэдгээрийн байршил нь n-ээс m хүртэлх элементүүдийн давталттай анхны хослолтой өвөрмөц тохирч байна. Харгалзан хувиргах техникийг эхний таван латин үсгийн үүсгэгч багцаас элементүүдийг сонгосон давталттай (BBD) хослуулан хоёртын хослол (1001101) байгуулах дараах жишээгээр дүрсэлсэн болно. Ерөнхийдөө ийм хоёртын олонлогуудын тоо нь (n1) нэгийг (эсвэл m тэг) (n+m1) хоёртын тоонд байрлуулах аргын тоог тодорхойлдог. Энэ утга нь мэдээжийн хэрэг (n+m1)-аас (n1) эсвэл m-ээр, өөрөөр хэлбэл C(n+m1,n1) эсвэл C(n+m1,m)-ийн хослолын тоотой тэнцүү байна. n элементийн f( n,m) давталттай хослолын тоо, тус бүр m. Тиймээс давталттай хослолууд болон хоёртын хослолуудын хооронд нэг нэгээр нь харгалзах тул давталттай хослолуудын тоог хоёртын хослолыг тоолох хүртэл багасгах, жишээлбэл, зүүн эсвэл баруун тийш шилжих алгоритмыг ашиглах нь хууль ёсны юм. Үүний дараа та зөвхөн үүссэн хоёртын хослолыг ашиглан шаардлагатай хослолуудыг давталттайгаар сэргээх хэрэгтэй. Үүнийг дараах сэргээх техникийг ашиглан үргэлж хийж болно. Заавал өөр өөр элемент үүсэх албагүй m-ийн давталттай хослол бүхий үндсэн олонлогийг түүний элемент бүр 1-ээс n хүртэлх тодорхой серийн дугаартай байхаар дур зоргоороо эрэмбэлье. Мөн (n+m1) хоёртын цифрүүдийн (n1) нэг ба m тэг цифрүүдийн хоёртын хослолуудын тооллогыг хэрэгжүүлье. Үүссэн хоёртын хослол бүрийг зүүн талд нь зохиомол нэгж цифрээр нэмж, бүх нэгжийн цифрүүдийг зүүнээс баруун тийш 1-ээс n хүртэлх бүхэл тоогоор дугаарлаж болно. Дараа нь хоёртын хослолын i-р нэгж бүрийн дараа дараалсан тэгийн тоо нь давталттай харгалзах хослол дахь үндсэн багцын i-р элементийн тохиолдлын тоотой тэнцүү байх болно. Дараах жишээгээр авч үзсэн техникийг хоёртын хослол (1001101) ашиглан BBD-ийн давталттай хослолыг сэргээж, элементүүдийг цагаан толгойн үсгийн дарааллаар бичсэн эхний таван латин үсгийн үүсгэгч багцаас сонгосон. , мөн давхар зураас нь энэ хослолд байхгүй элементүүдийг заана: Энэ жишээний нөхцөлд ижил төстэй үйлдлүүдийг хийснээр та 4 нэг ба 3 тэгтэй 7 битийн хоёртын олонлогийг бүрдүүлдэг бүх 35 хоёртын хослолыг жагсааж, 3-ын 5 элементийн давталтаар харгалзах хослолыг сэргээж болно. Комбинаторик бол өгөгдсөн объектуудаас тодорхой нөхцлийн дагуу хэдэн өөр хослол хийж болох тухай асуултуудыг судалдаг математикийн салбар юм. Комбинаторикийн үндэс нь санамсаргүй тохиолдлын магадлалыг тооцоолоход маш чухал, учир нь Эдгээр нь үйл явдлын хөгжлийн янз бүрийн хувилбаруудын үндсэн тоог тооцоолох боломжийг бидэнд олгодог. k бүлэг элемент байх ба i-р бүлэг нь n i элементээс бүрдэнэ. Бүлэг бүрээс нэг элемент сонгоцгооё. Тэгвэл ийм сонголт хийх боломжтой N аргын нийт тоог N=n 1 *n 2 *n 3 *...*n k хамаарлаар тодорхойлно.Жишээ 1. Энэ дүрмийг энгийн жишээгээр тайлбарлая. Хоёр бүлэг элемент байг, эхний бүлэг нь n 1 элементээс, хоёр дахь нь n 2 элементээс бүрдэнэ. Энэ хоёр бүлгээс хэдэн өөр хос элемент хийж болох бөгөөд энэ хос нь бүлэг тус бүрээс нэг элементийг агуулж болох вэ? Бид эхний бүлгээс эхний элементийг авч, түүнийг өөрчлөхгүйгээр бүх боломжит хосуудыг дамжуулж, зөвхөн хоёрдугаар бүлгийн элементүүдийг өөрчилсөн гэж үзье. Энэ элементийн хувьд ийм хос n 2 байж болно. Дараа нь бид эхний бүлгээс хоёр дахь элементийг авч, түүнд тохирох бүх хосыг хийнэ. Мөн n 2 ийм хос байх болно.Эхний бүлэгт зөвхөн n 1 элемент байгаа тул нийт боломжит сонголтууд нь n 1 *n 2 байх болно. n 1 =6 (учир нь та 1, 2, 3, 4, 5, 6-аас ямар ч тоог эхний орон болгон авч болно), n 2 =7 (учир нь та 0-ээс дурын тоог хоёр дахь цифр болгон авч болно , 1, 2 , 3, 4, 5, 6), n 3 =4 (0, 2, 4, 6-аас эхлэн дурын тоог гурав дахь орон болгон авч болно). Тэгэхээр N=n 1 *n 2 *n 3 =6*7*4=168. Бүх бүлгүүд ижил тооны элементүүдээс бүрдэх тохиолдолд, өөрөөр хэлбэл. n 1 =n 2 =...n k =n сонголт бүрийг нэг бүлгээс хийсэн, сонгосны дараах элементийг бүлэгт буцаана гэж бид үзэж болно. Дараа нь бүх сонголтын аргын тоо n k байна. Комбинаторик дахь сонголтын энэ аргыг нэрлэдэгбуцаан олголттой дээж. 1, 5, 6, 7, 8 гэсэн цифрүүдээс дөрвөн оронтой хэдэн тоо гаргаж болох вэ? Дөрвөн оронтой тооны цифр бүрт таван боломж байгаа нь N=5*5*5*5=5 4 =625 гэсэн үг.. нийт хүн ам n элементийн байршлын тоо m nТодорхойлолт 1. м-аас байрлуулсан элементүүдкомбинаторикт аливаа мзахиалсан багц n-аас дахь популяциас сонгосон янз бүрийн элементүүдэлементүүд. Жишээ 4. Сэтгэгдэл: n!=1*2*3*...*n (унш: "en factorial"), үүнээс гадна 0!=1 гэж үздэг. Жишээ 5. Аравтын орон ба нэгжийн орон нь өөр, сондгой байдаг хоёр оронтой хэдэн тоо байдаг вэ? Тодорхойлолт 2. Хослол-аас nТодорхойлолт 1. мкомбинаторикт аливаа захиалгагүй багцкомбинаторикт аливаа мдахь популяциас сонгосон янз бүрийн элементүүд nэлементүүд. Жишээ 6. (1, 2, 3) багцын хувьд (1, 2), (1, 3), (2, 3) хослолууд байна. Хослолын тоог C n m-ээр тэмдэглэж, дараах томъёогоор тооцоолно. Жишээ 7.Уншигч зургаан номноос хоёрыг хэдэн аргаар сонгож болох вэ? Шийдэл:Аргын тоо нь хоёр зургаан номын хослолын тоотой тэнцүү байна, i.e. тэнцүү байна: Тодорхойлолт 3. Орлуулах-аас nэлементүүдийг дурын гэж нэрлэдэг элементүүдэдгээр элементүүд. Жишээ 7a.Гурван элементээс (1, 2, 3) бүрдэх олонлогийн бүх боломжит орлуулалтууд нь: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2). n элементийн өөр өөр сэлгэлтийн тоог P n гэж тэмдэглэж P n =n! томъёогоор тооцоолно. Жишээ 8.Өөр өөр зохиолчдын долоон номыг нэг эгнээнд тавиур дээр хэдэн янзаар байрлуулж болох вэ? Шийдэл:Энэ асуудал нь долоон өөр номын сэлгэлтийн тооны тухай юм. Номуудыг цэгцлэх P 7 =7!=1*2*3*4*5*6*7=5040 арга бий. Хэлэлцүүлэг.Боломжит хослолуудын тоог янз бүрийн дүрмийн дагуу (сэлгэн залгалт, хослол, байршил) тооцоолж болох бөгөөд үр дүн нь өөр байх болно гэдгийг бид харж байна, учир нь Тооцооллын зарчим, томъёо нь өөр өөр байдаг. Тодорхойлолтыг анхааралтай ажиглавал үр дүн нь хэд хэдэн хүчин зүйлээс нэгэн зэрэг хамааралтай болохыг анзаарах болно. Нэгдүгээрт, бид хэдэн элементээс тэдгээрийн багцыг нэгтгэж чадах вэ (элементүүдийн нийт хэмжээ хэр их вэ). Хоёрдугаарт, үр дүн нь бидэнд хэрэгтэй элементийн багцын хэмжээнээс хамаарна. Эцэст нь, багц дахь элементүүдийн дараалал нь бидний хувьд чухал ач холбогдолтой эсэхийг мэдэх нь чухал юм. Дараах жишээг ашиглан сүүлчийн хүчин зүйлийг тайлбарлая. Жишээ 9.Эцэг эхийн хуралд 20 хүн оролцож байна. Эцэг эхийн хорооны бүрэлдэхүүнд 5 хүний бүрэлдэхүүнтэй байх ёстой гэж үзвэл хэдэн өөр хувилбар байдаг вэ? Хорооны гишүүн бүр ажлын тодорхой чиглэлийг хариуцдаг бол бүх зүйл өөр байх болно. Дараа нь хорооны гишүүдийн ижил жагсаалтад 5 хүн багтаж магадгүй юм! сонголтууд орлуулалттэр асуудал. Өөр өөр сонголтуудын тоог (бүрэлдэхүүн болон хариуцлагын хүрээнд хоёуланг нь) энэ тохиолдолд тоогоор тодорхойлно байршуулалт 20 элемент тус бүр 5. Өөрийгөө шалгах даалгавар 2. Зүүнээс баруун тийш, баруунаас зүүн тийш ижил уншигдах таван оронтой тоо хэд вэ? 3. Ангид арван хичээл, өдөрт таван хичээл ордог. Та нэг өдрийн хуваарийг хэдэн аргаар гаргаж болох вэ? 4. Бүлэгт 20 хүн байгаа бол чуулганд 4 төлөөлөгчийг хэдэн хэлбэрээр сонгох вэ? 5. Дугтуй бүрд ганцхан үсэг хийвэл найман өөр үсгийг найман өөр дугтуйнд хэдэн янзаар хийж болох вэ? 6. Хоёр математикч, зургаан эдийн засагчаас бүрдсэн комисс гурван математикч, арван эдийн засагчаас бүрдсэн байх. Үүнийг хэдэн аргаар хийж болох вэ?Комбинаторикийн үндсэн томъёо
Шийдэл:Жишээ 2.
0, 1, 2, 3, 4, 5, 6 гэсэн цифрүүдийг давтаж чадвал гурван оронтой хэдэн тэгш тоо гаргаж болох вэ?
Шийдэл.Жишээ 3.n элементээс бүрдэх олонлогийг авч үзье. Комбинаторикт энэ олонлогийг нэрлэдэг
Шийдэл:учир нь Хэрэв 1, 3, 5, 7, 9 гэсэн таван сондгой цифр байгаа бол энэ даалгавар нь таван өөр цифрээс хоёрыг сонгож, хоёр өөр байрлалд байрлуулах явдал юм. заасан тоонууд нь:
n элементийн хослолын тоо, тус бүр m
n элементийн орлуулалт
Шийдэл:Энэ жишээн дээр бид хорооны жагсаалтын нэрсийн дарааллыг сонирхохгүй байна. Хэрэв үр дүнд нь ижил хүмүүс түүний нэг хэсэг болж хувирвал бидний хувьд энэ нь ижил сонголт юм. Тиймээс бид тоог тооцоолохдоо томъёог ашиглаж болно хослолууд 20 элемент тус бүр 5.
1. 0, 1, 2, 3, 4, 5, 6-ын цифрүүд давтагдаж чадвал гурван оронтой тэгш тоо хэд болох вэ?
