10-аас 2 нь хэдэн хослол. Комбинаторик: үндсэн дүрэм, томъёо. Оршил ба магадлалын онол

Бүх N элемент бөгөөд нэг нь ч давтагдахгүй бол энэ нь сэлгэцийн тооны асуудал юм. Шийдлийг энгийн байдлаар олж болно. N элементийн аль нэг нь эгнээний эхний байрыг эзэлж чадах тул N сонголтыг олж авна. Хоёрдугаарт - эхний байранд аль хэдийн ашиглагдсанаас бусад нь. Тиймээс аль хэдийн олдсон N сонголт бүрийн хувьд (N - 1) хоёрдугаар байрын сонголтууд байгаа бөгөөд нийт хослолын тоо N*(N - 1) болно.
Цувралын үлдсэн элементүүдийн хувьд ижил зүйлийг давтаж болно. Хамгийн сүүлчийн байранд зөвхөн нэг сонголт үлдсэн - сүүлчийн элемент. Эцсийн эцэст - хоёр сонголт гэх мэт.
Иймд N давтагдахгүй элементийн цувааны хувьд боломжит сэлгэлт нь 1-ээс N хүртэлх бүх бүхэл тоонуудын үржвэртэй тэнцүү байна. Энэ үржвэрийг N-ийн факториал гэж нэрлэх ба N-ээр тэмдэглэнэ! ("en factorial" гэж уншина уу).

Өмнөх тохиолдолд, боломжит элементүүдийн тоо болон цувралын газруудын тоо давхцаж, тэдгээрийн тоо нь N-тэй тэнцүү байсан. Гэхдээ цувралд боломжит элементүүдээс цөөн газар байгаа тохиолдолд нөхцөл байдал боломжтой. Өөрөөр хэлбэл, түүврийн элементүүдийн тоо нь M, M тоотой тэнцүү байна< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Эхлээд N-ээс M элементийг дараалан байрлуулах боломжит аргуудын нийт тоог тоолох шаардлагатай байж магадгүй.Ийм аргыг байршуулалт гэж нэрлэдэг.
Хоёрдугаарт, судлаач N элементээс M элементийг сонгох хэд хэдэн арга замыг сонирхож магадгүй. Энэ тохиолдолд элементүүдийн дараалал чухал байхаа больсон, гэхдээ дурын хоёр сонголт бие биенээсээ дор хаяж нэг элементээр ялгаатай байх ёстой. . Ийм аргыг хослол гэж нэрлэдэг.

N элементээс M элементийн байршлын тоог олохын тулд сэлгэн залгахтай адил үндэслэлийг ашиглаж болно. Эхний ээлжинд N элемент байж болно, хоёрдугаарт (N - 1) гэх мэт. Гэхдээ сүүлийн байранд боломжит сонголтуудын тоо нь нэг биш, харин (N - M + 1), учир нь байршуулалт дууссаны дараа (N - M) ашиглагдаагүй элементүүд байх болно.
Тиймээс, N-ээс M элемент дээр байршуулах тоо нь (N - M + 1) -ээс N хүртэлх бүх бүхэл тоонуудын үржвэртэй тэнцүү, эсвэл N!/(N - M)!

Мэдээжийн хэрэг, N-ээс M элементийн хослолын тоо нь байрлуулах тооноос бага байх болно. Боломжит хослол бүрт M байна! энэ хослолын элементүүдийн дарааллаас хамааран боломжит байршуулалт. Иймд энэ тоог олохын тулд та N элементийн M элемент дээрх байршлын тоог N-д хуваах хэрэгтэй! Өөрөөр хэлбэл, N-ээс M элементийн хослолын тоо нь N!/(M!*(N - M)!).

КОМБИНАТОРИК

Комбинаторик нь өгөгдсөн дүрмийн дагуу зарим үндсэн олонлогоос элементүүдийг сонгох, цэгцлэх асуудлыг судалдаг математикийн салбар юм. Комбинаторикийн томъёо, зарчмуудыг магадлалын онолд санамсаргүй үйл явдлын магадлалыг тооцоолох, үүний дагуу санамсаргүй хэмжигдэхүүний тархалтын хуулийг олж авахад ашигладаг. Энэ нь эргээд массын санамсаргүй үзэгдлийн хуулиудыг судлах боломжийг олгодог бөгөөд энэ нь байгаль, технологид илэрдэг статистикийн хуулиудыг зөв ойлгоход маш чухал юм.

Комбинаторик дахь нэмэх ба үржүүлэх дүрэм

Нийлбэрийн дүрэм. Хэрэв А ба В хоёр үйлдэл нь бие биенээ үгүйсгэж, А үйлдлийг m аргаар, Б үйлдлийг n аргаар гүйцэтгэж чадвал эдгээр үйлдлүүдийн аль нэгийг нь (А эсвэл В) n + m аргаар гүйцэтгэж болно.

Жишээ 1

Ангид 16 хүү, 10 охин байна. Нэг үйлчлэгчийг хэдэн янзаар томилж болох вэ?

Шийдэл

Та жижүүрийн хүү эсвэл охиныг томилж болно, i.e. 16 хөвгүүдийн аль нэг нь эсвэл 10 охины аль нь ч үүрэг гүйцэтгэж болно.

Нэгдсэн журмын дагуу нэг жижүүрийг 16+10=26 янзаар томилж болно.

Бүтээгдэхүүний дүрэм. k үйлдлийг дараалан гүйцэтгэхийг шаардана. Эхний үйлдлийг n 1 аргаар, хоёр дахь үйлдлийг n 2 аргаар, гурав дахь үйлдлийг n 3 аргаар гэх мэтээр n k аргаар хийж болох k дахь үйлдэл хүртэл хийж чадвал бүх k үйлдлийг хамтад нь хийж болно. гүйцэтгэсэн:

арга замууд.

Жишээ 2

Ангид 16 хүү, 10 охин байна. Хоёр үйлчлэгчийг хэдэн аргаар томилж болох вэ?

Шийдэл

Эхний ээлжийн хүн нь хүү эсвэл охин байж болно. Учир нь Ангид 16 хүү, 10 охин байгаа бол 16 + 10 = 26 аргаар нэгдүгээр жижүүрийг томилж болно.

Бид нэгдүгээр жижүүрийг сонгосны дараа үлдсэн 25 хүнээс хоёр дахь жижүүрийг сонгож болно, өөрөөр хэлбэл. 25 арга.

Үржүүлэх теоремоор хоёр үйлчлэгчийг 26*25=650 аргаар сонгож болно.

Давталтгүй хослолууд. Давталттай хослолууд

Комбинаторикийн сонгодог асуудал бол давталтгүй хослолын тооны асуудал бөгөөд агуулгыг нь дараахь асуултаар илэрхийлж болно. Хэдэн ширхэг арга замууд Чадах сонгох м-ээс n өөр зүйл?

Жишээ 3

Бэлэглэх боломжтой 10 өөр номноос 4-ийг нь сонгох ёстой. Үүнийг хэдэн аргаар хийж болох вэ?

Шийдэл

Бид 10 номноос 4-ийг нь сонгох хэрэгтэй бөгөөд сонголтын дараалал хамаагүй. Тиймээс та 10 элементийн хослолын тоог 4-ээр олох хэрэгтэй.

.

Давталттай хослолын тооны асуудлыг авч үзье: n өөр төрлийн r ижил объектууд байдаг; Хэдэн ширхэг арга замууд Чадах сонгох m()-ийн эдгээр (n*r) зүйл?

.

Жишээ 4

Тус нарийн боовны дэлгүүрт наполеон, эклер, боов, хийсвэр гэсэн 4 төрлийн бялуу худалдаалагдаж байв. 7 бялууг хэдэн аргаар худалдаж авч болох вэ?

Шийдэл

Учир нь 7 бялууны дунд ижил төрлийн бялуу байж болно, дараа нь 7 бялууг худалдаж авах аргын тоог 7-оос 4 хүртэлх давталттай хослолын тоогоор тодорхойлно.

.

Дахин давтагдахгүйгээр байршуулах. Давталт бүхий байрлалууд

Комбинаторикийн сонгодог асуудал бол давталтгүйгээр байршуулах тооны асуудал бөгөөд түүний агуулгыг дараахь асуултаар илэрхийлж болно. Хэдэн ширхэг арга замууд Чадах сонгох Тэгээд газар By м өөр газрууд м-ээс n өөр эд зүйлс?

Жишээ 5

Зарим сонин 12 хуудастай байдаг. Энэ сонины хуудсан дээр дөрвөн гэрэл зургийг байрлуулах шаардлагатай. Хэрэв сонины аль ч хуудсанд нэгээс илүү гэрэл зураг байх ёсгүй бол үүнийг хэдэн аргаар хийж болох вэ?

Шийдэл.

Энэ асуудалд бид зөвхөн гэрэл зургуудыг сонгоод зогсохгүй сонины тодорхой хуудсан дээр байрлуулж, сонины хуудас бүр нэгээс илүүгүй зураг байх ёстой. Тиймээс асуудлыг 12 элементээс 4 элементээр давталтгүйгээр байршуулах тоог тодорхойлох сонгодог асуудал болгон бууруулж байна.

Тиймээс 12 хуудасны 4 зургийг 11880 янзаар байрлуулж болно.

Мөн комбинаторикийн сонгодог даалгавар бол давталттай байршуулалтын тооны асуудал бөгөөд түүний агуулгыг дараахь асуултаар илэрхийлж болно. Хэдэн ширхэг арга замууд Чадах Табарми Тэгээд газар By м өөр газрууд м-ээс n зүйл-тайredi аль Байна адилхан уу?

Жишээ 6

Хүү нь ширээний тоглоомын багцаас 1, 3, 7 гэсэн тоо бүхий марктай байсан бөгөөд тэр эдгээр маркуудыг ашиглан бүх номон дээр таван оронтой тоо тавихаар шийджээ. Хүү хэдэн өөр таван оронтой тоо гаргаж чадах вэ?

Дахин давтагдахгүйгээр солих. Дахин давтагдах өөрчлөлтүүд

Комбинаторикийн сонгодог асуудал бол давталтгүйгээр орлуулах тооны асуудал бөгөөд агуулгыг нь дараахь асуултаар илэрхийлж болно. Хэдэн ширхэг арга замууд Чадах газар n янз бүрийн зүйлс дээр n өөр газрууд?

Жишээ 7

"Гэрлэлт" гэдэг үгийн үсгүүдээс хэдэн дөрвөн үсэгтэй "үг" хийж болох вэ?

Шийдэл

Ерөнхий багц нь "гэрлэлт" гэсэн үгний 4 үсэг (b, p, a, k). "Үг" -ийн тоог эдгээр 4 үсгийн орлуулах замаар тодорхойлно, i.e.

Сонгосон n элементийн дунд ижил (буцах сонголттой) байгаа тохиолдолд давталттай сэлгэлтийн тооны асуудлыг дараахь асуултаар илэрхийлж болно. Хэрэв n объектын дотор n өөр төрлийн (k) байвал n объектыг n өөр газар хэдэн аргаар дахин байрлуулах боломжтой вэ?< n), т. е. есть одинаковые предметы.

Жишээ 8

"Миссисипи" гэдэг үгийн үсгүүдээс хэдэн өөр үсгийн хослол хийж болох вэ?

Шийдэл

"М" 1 үсэг, "и" 4 үсэг, "в" 3 үсэг, "п" 1 үсэг нийт 9 үсэгтэй. Тиймээс давталттай солих тоо нь байна

"КОМБИНАТОРИК" БҮЛЭГИЙН ҮНДЭСЛЭЛИЙН ХУРААНГУЙ

Найзууд аа! Энэ үхсэн дэвтэр надад байгаа болохоор өчигдөр гурван физикч, хоёр эдийн засагч, нэг Политехникийн нэг, нэг хүмүүнлэгийн ухааны нэг хүний ​​тулгарсан асуудлыг асууж байна. Бид тархиа бүхэлд нь эвдэж, бид байнга өөр үр дүнд хүрдэг. Магадгүй та нарын дунд программистууд, математикийн суутнууд байгаа байх, үүнээс гадна асуудал нь ерөнхийдөө сургуулийнх бөгөөд маш амархан, бидэнд томъёо байхгүй. Яагаад гэвэл нарийн шинжлэх ухааныг орхиод оронд нь яагаад ч юм ном бичиж, зураг зурдаг болсон. Уучлаарай.

Тэгэхээр, арын түүх.

Надад шинэ банкны карт өгсөн бөгөөд би ердийнхөөрөө түүний пин кодыг ямар ч хүчин чармайлтгүйгээр тааварлав. Гэхдээ дараалан биш. Пин код нь 8794 байсан гэж бодъё, би 9748 руу залгасан. Өөрөөр хэлбэл би ялалт байгуулсан. бүх тоог таасанөгөгдсөн дөрвөн оронтой тоонд агуулагдсан. За, тийм ээ, зүгээр нэг тоо биш, гэхдээ зүгээр л түүний бүрэлдэхүүн хэсгүүдгэж гайхсан. Гэхдээ бүх тоо үнэн! ТАЙЛБАР - Би санамсаргүй байдлаар үйлдэл хийсэн, өөрөөр хэлбэл би аль хэдийн мэдэгдэж байсан тоонуудыг зөв дарааллаар оруулах шаардлагагүй, би зүгээр л сүнсээр ажилласан: энд миний мэдэхгүй дөрвөн тоо байгаа бөгөөд тэдний дунд байж магадгүй гэж би итгэж байна. 9, 7, 4, 8 байх ба тэдгээрийн дараалал чухал биш.Бид тэр даруй өөрөөсөө асуув Надад хэдэн сонголт байсан(ямар дажгүй юм бэ гэдгийг ойлгохын тулд аваад тааж байсан байх). Өөрөөр хэлбэл, би дөрвөн тооны хэдэн хослолыг сонгох ёстой байсан бэ? Тэгээд мэдээж там эхэлсэн. Оройн турш бидний толгой дэлбэрч, үүний үр дүнд бүгд өөр өөр хариултыг гаргаж ирэв! Би бүр эдгээр бүх хослолыг дэвтэр дээрээ дараалан бичиж эхэлсэн боловч дөрвөн зуугаар нь дөрвөн зуу гаруй байгааг ойлгосон (ямар ч байсан энэ нь физикч Трашийн хариултыг няцаасан. дөрвөн зуун хослол байсан, гэхдээ энэ нь тийм ч тодорхой биш байна) - тэгээд бууж өгсөн.

Үнэндээ, асуултын мөн чанар.Дөрвөн оронтой тоонд агуулагдах дөрвөн тоог (ямар ч дарааллаар) таамаглах магадлал хэд вэ?

Үгүй ээ, (би хүмүүнлэг, уучлаарай, математикийн хувьд үргэлж асар их сул талтай байсан ч) үүнийг илүү тодорхой, ойлгомжтой болгохын тулд дахин томъёолъё. Хэдэн ширхэг давтагдахгүй 0-ээс 9999 хүртэлх дарааллын тооны цувралд агуулагдах тооны хослолууд? ( Үүнийг "хэчнээн хослолтой вэ" гэсэн асуулттай андуурч болохгүй давтагдахгүйтоо"!!! тоог давтаж болно! Энэ тохиолдолд 2233 ба 3322 нь ижил хослол юм!).

Эсвэл бүр тодруулбал. Би араваас нэг тоог дөрвөн удаа таах хэрэгтэй. Гэхдээ дараалан биш.

За, эсвэл өөр зүйл. Ерөнхийдөө картын пин кодыг бүрдүүлсэн тоон хослолын хэдэн сонголт байгааг олж мэдэх хэрэгтэй. Туслаач, сайн хүмүүс ээ! Зүгээр л туслаарай, эдгээрийн хувьд 9999 сонголт байна гэж шууд бичиж эхлэх хэрэггүй(Өчигдөр энэ нь эхлээд бүгдийн санаанд орсон) Учир нь энэ бол утгагүй зүйл - эцэст нь бидний санаа зовдог хэтийн төлөвийн хувьд 1234 тоо, 3421 тоо, 4312 тоо гэх мэт. нэг бөгөөд адилхан! За, тийм ээ, тоонууд давтаж болно, учир нь пин код 1111 эсвэл тэнд жишээ нь 0007. Та пин кодын оронд машины дугаарыг төсөөлж болно. Машины дугаарыг бүрдүүлдэг бүх нэг оронтой тоог таах магадлал хэд вэ гэж бодъё? Эсвэл магадлалын онолыг бүрмөсөн устгахын тулд би хэдэн тоон хослолоос нэгийг нь сонгох ёстой байсан бэ?

Өчигдөр бид ухаан алдах шахсан тул хариулт, үндэслэлээ тодорхой томъёогоор нөөцөлнө үү. Бүгдэд нь урьдчилж маш их баярлалаа!

P.S. Нэг ухаалаг хүн, программист, зураач, зохион бүтээгч асуудлын зөв шийдлийг маш зөв санал болгож, надад хэдэн минутын сайхан сэтгэлийг өгсөн: " Асуудлын шийдэл нь энэ юм: тэр хий үзэгдэлтэй-компульсив эмгэгтэй, эмчилгээ нь: гэрлэж, улаан лооль цац. Хэрэв би түүний оронд байсан бол "магадлал хэд вэ" гэсэн асуулт биш, харин "би энэ бүх тоонд анхаарлаа хандуулж байна уу" гэсэн асуултад илүү их санаа зовох байсан.Ерөнхийдөө нэмэх зүйл алга :)

Доорх тооцоолуур нь n х m элементийн бүх хослолыг үүсгэх зориулалттай.
Ийм хослолын тоог "Комбинаторикийн элементүүд" тооцоолуур ашиглан тооцоолж болно. Сэлгээ, байршил, хослолууд.

Тооцоологч дор үүсгэх алгоритмын тайлбар.

Алгоритм

Холболтыг үг хэллэгийн дарааллаар үүсгэдэг. Алгоритм нь олонлогийн элементүүдийн дарааллын индексүүдтэй ажилладаг.
Алгоритмыг жишээгээр авч үзье.
Илтгэлд хялбар болгохын тулд индексүүд нь 1-ээр эхэлдэг таван элементийн багцыг авч үзье, тухайлбал 1 2 3 4 5.
m = 3 хэмжээтэй бүх хослолыг үүсгэх шаардлагатай.
Нэгдүгээрт, өгөгдсөн хэмжээтэй m-ийн эхний хослолыг эхлүүлсэн - өсөх дарааллаар индексүүд
1 2 3
Дараа нь сүүлчийн элементийг шалгана, өөрөөр хэлбэл i = 3. Хэрэв түүний утга n - m + i-ээс бага бол 1-ээр нэмэгдэнэ.
1 2 4
Сүүлийн элементийг дахин шалгаж, дахин нэмэгдүүлнэ.
1 2 5
Одоо элементийн утга нь хамгийн их боломжтой тэнцүү байна: n - m + i = 5 - 3 + 3 = 5, i = 2-тай өмнөх элементийг шалгана.
Хэрэв түүний утга нь n - m + i-ээс бага бол 1-ээр нэмэгдэх ба түүнийг дагаж байгаа бүх элементийн хувьд өмнөх элементийн утга 1-тэй тэнцүү байна.
1 (2+1)3 (3+1)4 = 1 3 4
Дараа нь бид i = 3 байгаа эсэхийг дахин шалгана.
1 3 5
Дараа нь - i = 2 байгаа эсэхийг шалгана уу.
1 4 5
Дараа нь i = 1 эргэлт ирнэ.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
Мөн цаашлаад,
2 3 5
2 4 5
3 4 5 - сүүлчийн хослол, учир нь түүний бүх элементүүд нь n - m + i-тэй тэнцүү байна.

Дэлхийн дэд бүтцэд PIN-ийн үүрэг чухал хэдий ч хүмүүс PIN кодыг хэрхэн сонгодог талаар эрдэм шинжилгээний судалгаа хараахан хийгдээгүй байна.

Кембрижийн их сургуулийн судлаач Сорен Прейбуш, Росс Андерсон нар 4 оронтой банкны PIN кодыг таахад хүндрэлтэй байгааг харуулсан дэлхийн анхны тоон шинжилгээг нийтэлснээр нөхцөл байдлыг зассан.

Банкны бус эх сурвалжаас нууц үг задруулсан талаарх мэдээлэл болон онлайн судалгааг ашиглан судлаачид хэрэглэгчид вэб сайтын нууц үгийн сонголтоос хамаагүй илүү PIN кодыг сонгохдоо нухацтай ханддаг болохыг тогтоожээ: ихэнх кодууд нь бараг санамсаргүй тоонуудаас бүрддэг. Гэсэн хэдий ч анхны өгөгдлүүдийн дунд энгийн хослолууд болон төрсөн өдрүүд байдаг - өөрөөр хэлбэл, азаар халдагчид хүссэн кодыг тааж чадна.

Судалгааны эхлэл нь RockYou мэдээллийн сангаас 4 оронтой нууц үгийн дараалал (1.7 сая), iPhone дэлгэц түгжих программын 200 мянган PIN кодын мэдээллийн сан (мэдээллийн санг программ хөгжүүлэгч Даниел Амитай өгсөн) байв. . Энэхүү өгөгдөл дээр суурилсан графикууд нь сонирхолтой хэв маягийг харуулдаг - огноо, жил, давтагдсан тоо, тэр ч байтугай 69-р төгссөн PIN кодууд. Эдгээр ажиглалт дээр үндэслэн эрдэмтэд шугаман регрессийн загварыг бүтээсэн бөгөөд энэ нь PIN тус бүрийн алдар нэрийг 25 хүчин зүйлээс хамааруулан тооцдог. код нь DDMM форматын огноо мөн үү, өсөх дараалал уу гэх мэт. Эдгээр ерөнхий нөхцөл нь багц тус бүрийн PIN кодын 79% ба 93% хангагдсан байна.

Тиймээс хэрэглэгчид хэдхэн энгийн хүчин зүйл дээр үндэслэн 4 оронтой кодыг сонгодог. Хэрэв банкны ПИН кодыг ийм байдлаар сонгосон бол гуравхан оролдлого хийхэд тэдгээрийн 8-9% -ийг тааж болно! Гэхдээ мэдээжийн хэрэг хүмүүс банкны кодуудад илүү анхааралтай ханддаг. Банкны бодит мэдээлэл байхгүй тул судлаачид 1300 гаруй хүнтэй ярилцлага хийж, бодит ПИН код өмнө нь авч үзсэнээс хэр ялгаатай болохыг үнэлжээ. Судалгааны онцлогийг харгалзан судалгаанд оролцогчдоос кодуудын талаар асуугаагүй бөгөөд зөвхөн дээрх хүчин зүйлсийн аль нэгэнд (өсөлт, DDMM формат гэх мэт) нийцэж байгаа эсэхийг асуусан.

Хүмүүс банкны пин кодыг сонгохдоо илүү болгоомжтой ханддаг нь тогтоогдсон. Судалгаанд оролцогчдын дөрөвний нэг нь банкнаас үүсгэсэн санамсаргүй PIN кодыг ашигладаг. Гуравны нэгээс илүү хувь нь хуучин утасны дугаар, оюутны ID дугаар эсвэл санамсаргүй мэт харагдах бусад дугаарыг ашиглан ПИН кодоо сонгодог. Үр дүнгээс харахад карт эзэмшигчдийн 64% нь псевдо санамсаргүй PIN код ашигладаг бөгөөд энэ нь өмнөх банк бус кодтой туршилтын явцад 23-27% -иас хамаагүй илүү байна. Өөр 5% нь тооны загвар (жишээ нь 4545) ашигладаг бол 9% нь гарын хээг (жишээ нь 2684) илүүд үздэг. Ерөнхийдөө зургаан оролдлого хийсэн халдагчид (гурвыг нь АТМ-ээр, гурав нь төлбөрийн терминалаар) хэн нэгний картын ПИН кодыг таах магадлал 2%-иас бага байдаг.

Хамгийн алдартай 100 PIN код

0000, 0101-0103, 0110, 0111, 0123, 0202, 0303, 0404, 0505, 0606, 0707, 0808, 0909, 1010, 1101-1103, 1110-1112, 1123, 1201-1203, 1210-1212, 1234, 1956-2015, 2222, 2229, 2580, 3333, 4444, 5252, 5683, 6666, 7465, 7667.

P.S.Практик дээр халдагчид таны ПИН кодыг тагнаж чагнах нь үүнийг таамаглахаас хамаагүй хялбар байдаг. Гэхдээ та өөрийгөө шагайхаас хамгаалж чадна, тэр ч байтугай найдваргүй нөхцөлд ч гэсэн:

Комбинаторик бол өгөгдсөн объектуудаас тодорхой нөхцлийн дагуу хэдэн өөр хослол хийж болох тухай асуултуудыг судалдаг математикийн салбар юм. Комбинаторикийн үндэс нь санамсаргүй тохиолдлын магадлалыг тооцоолоход маш чухал, учир нь эдгээр нь үйл явдлын хөгжлийн янз бүрийн хувилбаруудын үндсэн боломжит тоог тооцоолох боломжийг олгодог.

Комбинаторикийн үндсэн томъёо

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 боломжит сонголт байх болно.

Жишээ 2 0, 1, 2, 3, 4, 5, 6-ын цифрүүд давтагдаж чадвал гурван оронтой хэдэн тэгш тоо гарах вэ?
Шийдэл: n 1 \u003d 6 (1, 2, 3, 4, 5, 6-ийн аль ч цифрийг эхний орон болгон авч болно), n 2 \u003d 7 (0-ээс ямар ч цифрийг хоёр дахь цифр болгон авч болно, 1). , 2, 3, 4, 5, 6), n 3 \u003d 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-тэй тэнцүү байна. Комбинаторикт ийм сонголт хийх аргыг нэрлэдэг дээжийг буцаах.

Жишээ 3 1, 5, 6, 7, 8 тооноос дөрвөн оронтой хэдэн тоо гаргаж болох вэ?
Шийдэл.Дөрвөн оронтой тооны цифр бүрт таван боломж байгаа тул N=5*5*5*5=5 4 =625.

n элементээс бүрдэх олонлогийг авч үзье. Комбинаторик дахь энэ олонлогийг нэрлэдэг нийт хүн ам.

n элементээс m-ээр байршуулах тоо

Тодорхойлолт 1.-аас байр nэлементүүд мкомбинаторикт дурын гэж нэрлэдэг захиалсан багц-аас мдахь нийт хүн амын дундаас сонгосон янз бүрийн элементүүд nэлементүүд.

Жишээ 4Гурван элементийн (1, 2, 3) хоёр, хоёрын өөр өөр зохицуулалт нь (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) олонлог болно. , 2). Байрлуулалт нь элементүүд болон дарааллаар нь бие биенээсээ ялгаатай байж болно.

Комбинаторик дахь байршлын тоог A n m-ээр тэмдэглэж, дараах томъёогоор тооцоолно.

Сэтгэгдэл: n!=1*2*3*...*n (унш: "en factorial"), үүнээс гадна 0!=1 гэж үздэг.

Жишээ 5. Аравтын орон ба нэгжийн орон нь өөр, сондгой байдаг хоёр оронтой хэдэн тоо байдаг вэ?
Шийдэл:учир нь 1, 3, 5, 7, 9 гэх мэт таван сондгой цифр байгаа бол энэ асуудал нь таван өөр цифрээс хоёрыг нь сонгож, хоёр өөр байрлалд байрлуулахад хүргэдэг, өөрөөр хэлбэл. өгөгдсөн тоонууд нь:

Тодорхойлолт 2. Хослол-аас nэлементүүд мкомбинаторикт дурын гэж нэрлэдэг захиалгагүй багц-аас мдахь нийт хүн амын дундаас сонгосон янз бүрийн элементүүд nэлементүүд.

Жишээ 6. (1, 2, 3) багцын хувьд (1, 2), (1, 3), (2, 3) хослолууд байна.

n элементийн хослолын тоо m

Хослолын тоог C n m-ээр тэмдэглэж, дараах томъёогоор тооцоолно.

Жишээ 7Уншигч зургаан номноос хоёрыг хэдэн аргаар сонгож болох вэ?

Шийдэл:Аргын тоо нь зургаан номын хослолын тоо хоёроор тэнцүү байна, i.e. тэнцүү байна:

n элементийн сэлгэлт

Тодорхойлолт 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 хүний ​​бүрэлдэхүүнтэй байхаар бол хэдэн өөр хувилбар байгаа вэ?
Шийдэл:Энэ жишээнд бид хорооны жагсаалтад байгаа нэрсийн дарааллыг сонирхохгүй байна. Үүний үр дүнд түүний найрлагад ижил хүмүүс гарч ирвэл бидний хувьд энэ нь ижил сонголт юм. Тиймээс бид тоог тооцоолохдоо томъёог ашиглаж болно хослолууд 20 элементээс 5.

Хорооны гишүүн бүр ажлын тодорхой чиглэлийг хариуцдаг бол бүх зүйл өөр байх болно. Дараа нь хорооны ижил цалинтай, дотор нь 5 боломжтой! сонголтууд орлуулалттэр асуудал. Өөр өөр сонголтуудын тоог (бүрэлдэхүүн болон хариуцлагын хүрээний хувьд) энэ тохиолдолд тоогоор тодорхойлно. байршуулалт 20 элементээс 5.

Өөрийгөө шалгах даалгавар
1. 0, 1, 2, 3, 4, 5, 6 гэсэн тоонуудыг давтаж чадвал гурван оронтой хэдэн тэгш тоо гаргаж болох вэ?
Учир нь Гурав дахь тэгш тоо нь 0, 2, 4, 6 байж болно, i.e. дөрвөн оронтой. Хоёрдахь орон нь долоон оронтой аль нэг нь байж болно. Эхний байр нь тэгээс бусад долоон оронтой тоо байж болно, өөрөөр хэлбэл. 6 боломж. Үр дүн =4*7*6=168.
2. Зүүнээс баруун тийш, баруунаас зүүн тийш ижил уншдаг таван оронтой тоо хэд вэ?
Эхний байр нь 0-ээс бусад тоо байж болно, i.e. 9 боломж. Хоёр дахь газар нь ямар ч тоо байж болно, i.e. 10 боломж. Гурав дахь байр нь мөн ямар ч тоо байж болно, i.e. 10 боломж. Дөрөв ба тав дахь цифрийг урьдчилан тодорхойлсон бөгөөд эхний болон хоёр дахь цифрүүдтэй давхцаж байгаа тул ийм тооны тоо 9 * 10 * 10 = 900 байна.
3. Ангид арван хичээл, өдөрт таван хичээл ордог. Та нэг өдрийн хуваарийг хэдэн аргаар гаргаж болох вэ?

4. Бүлэгт 20 хүн байвал бага хуралд 4 төлөөлөгчийг хэдэн янзаар сонгож болох вэ?

n = C 20 4 = (20!)/(4!*(20-4)!)=(16!*17*18*19*20)/((1*2*3*4)*(16! ))=(17*18*19*20)/(1*2*3*4)=4845.
5. Дугтуй бүрд ганцхан үсэг хийвэл найман өөр үсгийг найман өөр дугтуйнд хэдэн янзаар хийж болох вэ?
Эхний дугтуйнд найман үсгийн 1-ийг, хоёр дахь нь үлдсэн долоон үсгийн нэг, гурав дахь нь зургаан үсэг гэх мэтийг хийж болно. n = 8! = 1*2*3*4*5*6*7*8 = 40320.
6. Гурван математикч, арван эдийн засагчаас хоёр математикч, зургаан эдийн засагчаас бүрдсэн комисс гаргах шаардлагатай. Үүнийг хэдэн аргаар хийж болох вэ?