Kombinator elementlari. Kombinatorika: asosiy qoidalar va formulalar 10 ta raqamning nechta kombinatsiyasi
Download 38.85 Kb.
|
Kombinator elementlari
|
Kombinator elementlari. Kombinatorika: asosiy qoidalar va formulalar 10 ta raqamning nechta kombinatsiyasi KOMBINATORIK Kombinatorika - matematikaning ma'lum qoidalarga muvofiq elementlarni tanlash va tartibga solish muammolarini o'rganadigan bo'limi. Ehtimollar nazariyasida ehtimollikni hisoblash uchun kombinator formulalar va tamoyillar qo'llaniladi tasodifiy hodisalar va shunga mos ravishda tarqatish qonunlarini olish tasodifiy o'zgaruvchilar... Bu, o'z navbatida, ommaviy tasodifiy hodisalar namunalarini o'rganishga imkon beradi, bu tabiat va texnikada namoyon bo'ladigan statistik qonuniyatlarni to'g'ri tushunish uchun juda muhimdir. Kombinatorikada qo'shish va ko'paytirish qoidalari Yig'ish qoidasi. Agar ikkita A va B amallar bir -birini istisno qilsa va A harakatni m usulda, B ni esa n usulda bajarish mumkin bo'lsa, bu harakatlarning har qanday biri (A yoki B) n + m usulda bajarilishi mumkin. Misol 1.
Sinfda 16 o'g'il va 10 qiz bor. Bir xizmatchini necha usul bilan tayinlash mumkin?
Yechim
Yoki o'g'il yoki qiz vazifaga tayinlanishi mumkin, ya'ni. navbatchi 16 o'g'il yoki 10 qizning istalgani bo'lishi mumkin.
Yig'ish qoidasiga ko'ra, biz bitta xizmatchi 16 + 10 = 26 usulda tayinlanishi mumkin. Mahsulot qoidasi. K bosqichlarini ketma -ket bajarish talab qilinadi. Agar birinchi harakatni n 1 usulda bajarish mumkin bo'lsa, ikkinchi harakatni n 2 usulda, uchinchisini n 3 usulda va hokazo, nk usullar bilan bajarilishi mumkin bo'lgan k -chi harakatga qadar hamma k amallarni birgalikda bajarish mumkin. bajarilgan: yo'llar.
2 -misol.
Sinfda 16 o'g'il va 10 qiz bor. Qanday qilib ikkita xizmatchini tayinlash mumkin? Yechim
O'g'il yoki qizni birinchi qo'riqchi qilib tayinlash mumkin. Chunki Sinfda 16 o'g'il va 10 qiz o'qiydi, keyin siz birinchi navbatchini 16 + 10 = 26 usulda tayinlashingiz mumkin.
Birinchi xizmatchini tanlagandan so'ng, qolgan 25 kishidan ikkinchisini tanlashimiz mumkin, ya'ni. 25 usulda. Ko'paytirish teoremasiga ko'ra, 26 * 25 = 650 usulda ikkita xizmatchini tanlash mumkin. Takrorlanmagan kombinatsiyalar. Takrorlashlar bilan kombinatsiyalar Kombinatorikaning klassik muammosi - bu takrorlanmagan kombinatsiyalar soni muammosi, uning mazmunini quyidagi savol bilan ifodalash mumkin: necha yo'llar mumkin tanlang m dan n xil elementlar? Misol 3.
Sovg'a sifatida mavjud bo'lgan 10 ta kitobdan 4 tasini tanlashingiz kerak. Buni necha usul bilan qilishingiz mumkin?
Yechim
Biz 10 ta kitobdan 4tasini tanlashimiz kerak va tanlov tartibi muhim emas. Shunday qilib, siz 4 ta 10 ta elementning kombinatsiyasi sonini topishingiz kerak:
.
Takrorlashlar bilan kombinatsiyalar soni muammosini ko'rib chiqing: har xil turdagi n xil turdagi bir xil ob'ektlar mavjud; necha yo'llar mumkin tanlang m () dan shulardan (n * r) elementlar? .
Misol 4. Qandolat do'konida 4 xil pirojnoe sotildi: napoleonlar, eklerlar, qum va puffies. 7 ta kekni nechta usulda sotib olish mumkin? Yechim
Chunki 7 ta kek orasida bir xil turdagi keklar bo'lishi mumkin, keyin 7 ta kekni sotib olish usullari soni 7 dan 4 gacha takrorlangan kombinatsiyalar soni bilan belgilanadi.
.
Takrorlanmagan joylar. Takroriy joylashuvlar Kombinatorikaning klassik muammosi - bu takrorlanmagan joylashtirishlar muammosi, uning mazmunini quyidagi savol bilan ifodalash mumkin: necha yo'llar mumkin tanlang va joy yoqilgan m boshqacha joylar m dan n har xil narsalar? Misol 5.
Ba'zi gazetalarda 12 sahifa bor. Bu gazeta sahifalarida to'rtta fotosuratni joylashtirish kerak. Agar biror gazeta sahifasida bittadan ortiq fotosurat bo'lmasa, buni qanday qilish mumkin?
Yechim.
Bu vazifada biz faqat rasmlarni tanlamaymiz, balki ularni gazetaning ma'lum sahifalariga joylashtiramiz va gazetaning har bir sahifasida bittadan ko'p bo'lmagan rasm bo'lishi kerak. Shunday qilib, muammo 12 ta elementni, har biri 4 ta elementni takrorlamasdan joylashtirish sonini aniqlashning klassik muammosiga tushiriladi:
Shunday qilib, 12 sahifadagi 4 ta fotosuratni 11880 usulda joylashtirish mumkin. Kombinatorikaning klassik muammosi - bu takroriy joylashuvlar soni muammosi, uning mazmuni quyidagi savol bilan ifodalanishi mumkin. necha yo'llar mumkin sizbmezbon va joy yoqilgan m boshqacha joylar m dan n ta element,bilanorasida qaysi u yerda xuddi shu? Misol 6. Bolada stol o'yini uchun to'plamdan qolgan 1, 3 va 7 raqamli shtamplar bor edi va u bu markalardan foydalanib, barcha kitoblarga besh xonali raqamlarni qo'yishga qaror qildi - katalog tuzish uchun. O'g'il bola necha xil besh xonali son yasashi mumkin? Takrorlanmagan permutatsiyalar. Takrorlashlar bilan almashtirishlar Kombinatorikaning klassik muammosi - bu takrorlanmagan almashtirishlar soni muammosi, uning mazmunini quyidagi savol bilan ifodalash mumkin: necha yo'llar mumkin joy n har xil narsalar yoqilgan n har xil joylar? Misol 7. "Nikoh" so'zining harflaridan nechta to'rt harfli "so'z" yasash mumkin? Yechim
Umumiy aholi "nikoh" so'zining 4 harfidan iborat (b, p, a, k). "So'zlar" soni bu 4 harfning almashinuvi bilan belgilanadi, ya'ni.
Tanlangan n elementlar orasida bir xil elementlar bo'lsa (qaytish bilan tanlash), takroriy takrorlanishlar soni muammosi quyidagi savol bilan ifodalanishi mumkin: n xil joyda joylashgan n ta ob'ektni necha xil usulda o'zgartirish mumkin< n), т. e. ecть oдинakoвыe пpeдmeты. Misol 8.
"Missisipi" so'zining harflaridan nechta harf kombinatsiyasini yasash mumkin?
Yechim
1 ta "m" harfi, "i" harfi 4 ta, "c" harfi 3 ta va "p" harfi, jami 9 ta harf mavjud. Shunday qilib, takroriy takrorlanishlar soni
"KOMBINATORIKA" Bo'limining FOYDASI Kombinatorika - bu matematika bo'limi bo'lib, u berilgan ob'ektlardan ma'lum shartlar asosida qancha turli kombinatsiyalarni tuzish mumkinligi haqidagi savollarni o'rganadi. Kombinatorika asoslari tasodifiy hodisalar ehtimolini baholash uchun juda muhim, chunki aynan ular hodisalarning rivojlanishi uchun mumkin bo'lgan turli xil stsenariylarni hisoblash imkonini beradi. Kombinatorikaning asosiy formulasi K elementlar guruhi bo'lsin, va i-chi guruh n i elementlardan iborat. Keling, har bir guruhdan bittasini tanlaymiz. Keyin umumiy soni Bunday tanlashning N usullari n = n 1 * n 2 * n 3 * ... * n k munosabati bilan belgilanadi. Misol 1. Keling, bu qoidani oddiy misol bilan tushuntiraylik. Elementlarning ikkita guruhi bo'lsin va birinchi guruh n 1 elementdan, ikkinchisi esa n 2 elementdan iborat. Siz har ikki guruhdan bitta element bilan bog'lanish uchun bu ikki guruhdan nechta xil juft elementlarni tuzishingiz mumkin? Faraz qilaylik, biz birinchi elementni birinchi guruhdan oldik va uni o'zgartirmasdan, barcha mumkin bo'lgan juftlardan o'tdik, faqat ikkinchi guruh elementlarini o'zgartirdik. Bu element uchun bunday juftliklar n 2 bo'lishi mumkin. Keyin biz birinchi guruhdan ikkinchi elementni olamiz va buning uchun barcha mumkin bo'lgan juftlarni qilamiz. Bundan tashqari, 2 ta bunday juft bo'ladi. Birinchi guruhda faqat n 1 ta element bo'lgani uchun n 1 * n 2 ta variant bo'lishi mumkin. 2 -misol. Agar raqamlarni takrorlash mumkin bo'lsa, 0, 1, 2, 3, 4, 5, 6 raqamlaridan nechta uchta raqamli juft raqamlarni yasash mumkin? Yechim: n 1 = 6 (chunki birinchi raqam sifatida siz har qanday raqamni 1, 2, 3, 4, 5, 6 dan olishingiz mumkin), n 2 = 7 (chunki ikkinchi raqam sifatida 0, 1, 2 dan istalgan raqamni olishingiz mumkin) , 3, 4, 5, 6), n 3 = 4 (chunki har qanday raqamni 0, 2, 4, 6 dan uchinchi raqam sifatida olish mumkin). Shunday qilib, N = n 1 * n 2 * n 3 = 6 * 7 * 4 = 168. Agar barcha guruhlar bir xil miqdordagi elementlardan iborat bo'lsa, ya'ni. n 1 = n 2 = ... n k = n biz har bir tanlov bir xil guruhdan qilingan deb taxmin qilishimiz mumkin va tanlovdan so'ng element guruhga qaytariladi. Keyin barcha tanlash usullarining soni n k ga teng. Kombinatorikada bu tanlov usuli deyiladi qaytish bilan namuna olish. Misol 3. 1, 5, 6, 7, 8 raqamlaridan to'rtta raqamli nechta raqamni yasash mumkin? Yechim. To'rt xonali sonning har bir raqami uchun beshta imkoniyat bor, shuning uchun N = 5 * 5 * 5 * 5 = 5 4 = 625. N elementdan iborat to'plamni ko'rib chiqaylik. Kombinatoriy ma'noda bu to'plam deyiladi umumiy aholi. N ta elementni joylashtirish soni, har biri m Ta'rif 1. Turar joy n tomonidan elementlar m kombinatorikada, har qanday buyurtma to'plami dan m umumiy aholi orasidan tanlangan turli elementlar n elementlar. Misol 4. Ikkita uchta elementning (1, 2, 3) har xil joylashuvi (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) to'plamlar bo'ladi. , 2). Joylashtirish elementlar va tartib bo'yicha bir -biridan farq qilishi mumkin. Kombinatorikadagi joylashtirishlar soni A n m bilan belgilanadi va quyidagi formula bo'yicha hisoblanadi. Sharh: n! = 1 * 2 * 3 * ... * n (o'qing: "ento-faktorial"), bundan tashqari, 0! = 1 deb taxmin qilinadi. Misol 5... O'nlik va bitta farqli va g'alati bo'lgan ikkita raqamli nechta raqam bor? Yechim: beri beshta g'alati raqam bor, ya'ni 1, 3, 5, 7, 9, keyin bu vazifa besh xil raqamdan ikkitasini ikki xil pozitsiyaga tanlash va joylashtirishga to'g'ri keladi. ko'rsatilgan raqamlar quyidagicha bo'ladi: Ta'rif 2. Kombinatsiya dan n tomonidan elementlar m kombinatorikada, har qanday tartibsiz to'plam dan m umumiy aholi orasidan tanlangan turli elementlar n elementlar. Misol 6... To'plam uchun (1, 2, 3) kombinatsiyalar: (1, 2), (1, 3), (2, 3). Har bir n elementning kombinatsiyasi soni Kombinatsiyalar soni C n m bilan belgilanadi va quyidagi formula bilan hisoblanadi: Misol 7. O'quvchi mavjud oltitadan ikkita kitobni necha usul bilan tanlashi mumkin? Yechim: Yo'llar soni ikkitadan oltita kitobning kombinatsiyasi soniga teng. teng: N ta elementni almashtirish Ta'rif 3. Permutatsiya dan n elementlar har qanday deyiladi buyurtma to'plami bu elementlar. Misol 7a. Uch elementdan (1, 2, 3) iborat to'plamning barcha mumkin bo'lgan o'zgarishlari: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , (3, 2, 1), (3, 1, 2). N elementlarning turli xil almashtirish soni P n bilan belgilanadi va P n = n! Formulasi bilan hisoblanadi. Misol 8. Turli xil mualliflarning ettita kitobini tokchada bir qatorda nechta usulda joylashtirish mumkin? Yechim: Bu muammo etti xil kitobni almashtirish soni haqida. Kitoblarni joylashtirishning P 7 = 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040 usullari mavjud. Muhokama. Ko'ryapmizki, mumkin bo'lgan kombinatsiyalar sonini har xil qoidalarga (hisob -kitoblar, kombinatsiyalar, joylashtirish) ko'ra hisoblash mumkin va natija boshqacha bo'ladi. hisoblash tamoyili va formulalarning o'zi boshqacha. Ta'riflarga diqqat bilan qarasangiz, natija bir vaqtning o'zida bir qancha omillarga bog'liqligini sezasiz. Birinchidan, biz ularning elementlarini qancha elementlardan birlashtira olamiz (elementlarning umumiy soni qanchalik katta). Ikkinchidan, natija elementlarning qanchalik katta bo'lishiga bog'liq. Nihoyat, to'plamdagi elementlarning tartibi biz uchun muhimmi yoki yo'qligini bilish muhim. Oxirgi omilni quyidagi misol bilan tushuntirib beraylik. Misol 9. Yoqilgan ota -onalar yig'ilishi 20 kishi bor. Ota -onalar qo'mitasi tarkibiga 5 kishidan iborat bo'lsa, qancha xil variantlar bor? Yechim: Bu misolda bizni qo'mitalar ro'yxatidagi ismlarning tartibi qiziqtirmaydi. Agar, natijada, xuddi shu odamlar unga kiritilgan bo'lsa, demak, ma'no nuqtai nazaridan, bu biz uchun bir xil variant. Shuning uchun biz raqamni hisoblash uchun formuladan foydalanishimiz mumkin kombinatsiyalar har biri 5 ta 20 ta element. Agar qo'mitaning har bir a'zosi dastlab ma'lum bir ish yo'nalishi uchun javobgar bo'lsa, vaziyat boshqacha bo'ladi. Keyin qo'mitaning bir xil ish haqi bilan uning ichida 5 bo'lishi mumkin! variantlar almashtirishlar bu muhim. Turli xil (tarkibi bo'yicha ham, mas'uliyat sohasida ham) variantlar soni bu holda raqam bilan belgilanadi joylashtirishlar har biri 5 ta 20 ta element. O'z-o'zini tekshirish vazifalari 1. Agar raqamlarni takrorlash mumkin bo'lsa, 0, 1, 2, 3, 4, 5, 6 raqamlaridan nechta uch xonali juft sonlarni yasash mumkin? Chunki uchinchi o'rinda juft raqam 0, 2, 4, 6 bo'lishi mumkin, ya'ni. to'rtta raqam. Etti raqamdan har biri ikkinchi o'rinda bo'lishi mumkin. Noldan tashqari har qanday etti raqam birinchi o'rinda bo'lishi mumkin, ya'ni. 6 ta imkoniyat. Natija = 4 * 7 * 6 = 168. 2. Chapdan o'ngga va o'ngdan chapga bir xil o'qiladigan nechta besh xonali raqam bor? 0 dan boshqa har qanday raqam birinchi o'rinda bo'lishi mumkin, ya'ni. 9 ta imkoniyat. Har qanday raqam ikkinchi o'rinda bo'lishi mumkin, ya'ni. 10 ta imkoniyat. Dan har qanday raqam ham uchinchi o'rinda bo'lishi mumkin, ya'ni. 10 ta imkoniyat. To'rtinchi va beshinchi raqamlar oldindan belgilanadi, ular birinchi va ikkinchisiga to'g'ri keladi, shuning uchun bunday raqamlar soni 9 * 10 * 10 = 900. 3. Sinfda har kuni o'nta fan va beshta dars bor. Bir kunni qancha yo'l bilan rejalashtirish mumkin? 4. Agar guruhda 20 kishi bo'lsa, konferentsiyaga 4 ta delegatni necha usul bilan tanlash mumkin? 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. Agar har bir konvertda bitta harf bo'lsa, sakkiz xil harfni sakkiz xil konvertga necha usul bilan bukish mumkin? Siz birinchi konvertga sakkizta harfdan birini, ikkinchisiga qolgan etti dan birini, uchinchisiga oltitadan bittasini va boshqalarni qo'yishingiz mumkin. n = 8! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 = 40320. 6. Uch matematik va o'nta iqtisodchi tarkibidan ikkita matematik va oltita iqtisodchidan iborat komissiya tuzilishi kerak. Buni necha usul bilan amalga oshirish mumkin? Birinchidan, kombinatorikaning asosiy tushunchalarini - seleksiyalar va ularning turlarini tahlil qilaylik: almashtirishlar, joylashtirish va kombinatsiyalar. Ikkala darajadagi matematikadan 2020 yilgi imtihonning katta qismini hal qilish uchun ularni bilish kerak, shuningdek OGEni topshirish uchun to'qqizinchi sinf o'quvchilari. Bir misol bilan boshlaylik. Permutatsiyalar. O'zgartirishlar sonini hisoblash. Tasavvur qiling -a, siz matematikaga hech qanday aloqasi bo'lmagan kasbni tanladingiz, masalan, interyer dizayneri. Tasavvur qiling, xaridor sizdan so'rov yubordi: "Bordo va ko'k jildlar yonma -yon kelmasligi uchun tokchaga 4 ta kitob joylashtiring. Menga ko'rsating hamma joylashtirish imkoniyatlari. Men eng maqbulini tanlayman. " Nima qilmoqchisiz? Ehtimol, siz tartibga solishni va ko'rsatishni boshlaysiz. Biroq, chalkashmaslik, mumkin bo'lgan variantlardan birini o'tkazib yubormaslik va takrorlamaslik uchun, buni qandaydir tizim bo'yicha qilish kerak. Masalan, dastlab biz bordo hajmini birinchi navbatda qoldiramiz, uning yonida yashil yoki to'q sariq rang bo'lishi mumkin. Agar yashil hajm ikkinchi o'rinda bo'lsa, unda to'q sariq va ko'k, yoki ko'k va to'q sariq rangli turishi mumkin. Agar to'q sariq rangli ovoz ikkinchi o'rinda bo'lsa, unda yashil yoki ko'k, yoki ko'k va yashil navbatda turishi mumkin. Hammasi bo'lib 4 ta variant mavjud. Birinchi navbatda 4 jildning har biri bo'lishi mumkin, ya'ni tasvirlangan protsedura yana 3 marta takrorlanishi kerak. Moviy hajm birinchi o'rinda turadigan holat xuddi shu fikrlash orqali olinadi. Qolgan uchta joy bordo va ko'k ranglarni o'z ichiga olishi kerak, lekin bir -birining yonida emas. Masalan, yashil hajm birinchi o'rinda turganda, to'q sariq va ko'k ranglarni ajratish uchun uchinchi o'rinda turishi kerak, bu mos ravishda ikkinchi, to'rtinchi yoki to'rtinchi va ikkinchi bo'lishi mumkin. Natijada, biz cheklangan 4 ta kitobni javonga joylashtirishning atigi 12 variantini oldik. Bu ko'pmi yoki ozmi? Agar siz kitoblarni ko'chirishga va xaridor bilan chiqadigan versiyani muhokama qilishga bir daqiqa vaqt sarflasangiz, yaxshi bo'lardi. 12 daqiqa davomida siz kitoblarni ko'chirishingiz va gaplashishingiz mumkin. (Hisoblashga harakat qiling, hech qanday cheklovlarsiz 4 ta kitobning nechta o'zgarishi bo'lar edi?) Endi tasavvur qiling -a, xaridorda kitoblar soni 4 tadan ko'p. Xo'sh, hech bo'lmaganda 5. Aniqki, tartibga solish uchun ko'proq imkoniyatlar bo'ladi va ularni joyidan joyiga qayta tartibga solish uchun ko'proq vaqt kerak bo'ladi. takrorlashni boshlang ... tayyorgarliksiz kurash endi bunga loyiq emas. Siz avval qog'ozda o'z variantlaringizni rejalashtirishingiz kerak. Qisqalik uchun biz rangli jildlarni raqamlaymiz va ularning raqamlarini qog'ozga qayta joylashtiramiz. Kamroq xato qilish uchun, avval biz barcha almashtirish variantlarini yozamiz, so'ngra cheklovlar ostida bo'lganlarni o'chirib tashlaymiz. Shunday qilib: "5 ta kitobni javonga joylashtiring, shunda 1 va 2 -jildlar yonma -yon turmasin. Ko'rsating hamma almashtirish variantlari ". Bizda 5 ta kitob (yoki 5 ta raqam) bor, ularning har biri birinchi o'rinda turishi mumkin. Keling, ushbu 5 ta holatning har biri uchun o'z plastinkamizni tayyorlaylik. Ikkinchi o'rinda qolgan 4 ta raqam bo'lishi mumkin, ularning har biri uchun biz plastinkadagi ustunni zaxiralab qo'yamiz. Har bir ustunda biz chiziqlar juftligini joylashtiramiz, unda qolgan 3 ta raqamdan bittasi uchinchi o'rinda, oxirgi ikkita raqam esa bir -birining o'rnini bosadi. Shunday qilib, biz ehtiyotkorlik bilan yozamiz hamma almashtirish variantlari. Keling, ularning umumiy sonini hisoblaylik. 5 (jadvallar) × 4(ustun) × 3(chiziqlar juftligi) × 2(satrlar) × 1 ( variant) = 120 (variantlar). Va nihoyat, barcha jadvallardan "12" yoki "21" ni o'z ichiga olgan variantlarni o'chirib tashlang. Birinchi va ikkinchi plastinkalarda ulardan 6 tasi, qolgan 3 tasida 12 ta, jami 48 ta variant cheklovni qondirmagan. Bu shuni anglatadiki, xaridor 5 ta kitobni joylashtirishning 120 - 48 = 72 variantini ko'rsatishi kerak. Bu oladi bir soatdan ko'proq, har bir variantni muhokama qilish uchun atigi bir daqiqa sarflasangiz ham. Ammo beshta kitobni qayta tartibga solish uchun dizaynerni yollaydigan odamni qaerda ko'rdingiz? Aslida, bunday vazifalar kutubxonalarda paydo bo'ladi, bu erda siz kitoblarni tashrif buyuruvchilarga qulay bo'lishi uchun, katta kitob do'konlarida, talabni ko'paytirish uchun kitoblarni joylashtirishingiz kerak va hokazo. Ya'ni, bu erda bir nechta kitob emas, balki o'nlab emas, balki yuzlab va minglab kitoblar bor. O'zgarishlarni hisoblash faqat kitoblar uchun emas. Bu deyarli har qanday faoliyat sohasidagi ko'p sonli ob'ektlar uchun talab qilinishi mumkin. Bu shuni anglatadiki, dizaynerlarga ham, boshqa kasb egalariga ham tayyorgarlik bosqichini engillashtirish, mumkin bo'lgan natijalarni tahlil qilish va samarasiz mehnat hajmini kamaytirish uchun yordamchi kerak bo'ladi. Bunday asbob-uskunalarni olim-matematiklar yaratgan va yaratgan, keyin ularni jamiyatga tayyor formulalar tarzida berishgan. Matematiklar almashtirishlar bilan bog'liq masalalarni, shuningdek, turli elementlarning joylashishi va kombinatsiyasini e'tiborsiz qoldirmadilar. Tegishli formulalar asrlar davomida mavjud. Bu formulalar juda oddiy, ular maktab matematikasi darslarida jamiyatning o'sib borayotgan qismiga "topshiriladi". Shuning uchun, yuqorida yozilganlarning hammasi, aslida, "velosiped ixtirosi" bo'lib, uni ichki dizayner matematikaga hech qachon kerak bo'lmaydi, degan taxmin tufayli qo'llash kerak edi. Xo'sh, keling, bu farazdan voz kechaylik. Keling, matematika tushunchalarini ko'rib chiqaylik, so'ngra kitob javoni muammosiga qaytamiz. Kombinatorika matematika sohasi deb ataladi, unda ma'lum shartlar asosida qancha xilma -xil kombinatsiyalar berilishi mumkinligi haqidagi savollar berilgan to'plam elementlaridan iborat. Kombinatsiyalarni bajarishda biz aslida ushbu to'plamdan turli elementlarni tanlaymiz va ularni ehtiyojlarimizga qarab guruhlarga birlashtiramiz, shuning uchun "kombinatsiyalar" so'zining o'rniga ko'pincha elementlarning "tanlovlari" so'zi ishlatiladi. O'zgartirishlar soni uchun formulalar. Permutatsiyalar faqat elementlarning tartibida farq qiladigan elementlar tanlovi deyiladi, lekin elementlarning o'zida emas. Agar almashtirishlar dan to'plamda bajarilsa n elementlar, ularning soni formula bilan aniqlanadi P n = n·( n-1) ( n-2) ... 3 2 1 = n! n! - barchaning ishini qisqacha yozib olish uchun ishlatiladigan belgi natural sonlar 1 dan n inklyuziv va chaqirilgan " n-faktorial "(ingliz tilidan tarjima qilingan" omil "-" ko'paytiruvchi "). Shunday qilib, 5 ta kitobning umumiy soni P 5 = 5! = 1 · 2 · 3 · 4 · 5 = 120, bu biz yuqorida aytgan narsadir. Aslida, biz bu formulani kichik misol uchun oldik. Endi kattaroq misolni hal qilaylik. Muammo 1. Kitob javoni 30 jilddan iborat. 1 va 2 -jildlar yonma -yon turmasligi uchun ularni nechta usul bilan tartibga solish mumkin? Yechim.
Formulalar bo'yicha 30 ta elementning umumiy almashinish sonini aniqlang P 30=30!
Bu juda katta raqam(ikkitadan keyin yana 32 ta raqam bor). Har bir almashtirish uchun bir soniya kerak bo'lsa ham, milliardlab yillar kerak bo'ladi. Mijozning bunday talabini bajarishga arziydimi yoki unga asosli e'tiroz bildirish va qo'shimcha cheklovlarni qo'llashni talab qilish yaxshiroqmi? Permutatsiyalar va ehtimollar nazariyasi. Hatto ko'pincha variantlar sonini hisoblash zarurati ehtimollik nazariyasida paydo bo'ladi. Keyingi vazifa bilan kitob mavzusini davom ettiramiz. Muammo 2. Kitob javonida 30 jild bor edi. Bola kitoblarni javondan tashlab, keyin tasodifiy tartibda joylashtirdi. Uning ehtimoli qanday emas 1 va 2 -jildlarni yonma -yon qo'yish? Yechim.
Birinchidan, biz A hodisasining ehtimolini aniqlaymiz, bunda bola 1 va 2 -jildlarni yonma -yon qo'ygan.
Eslatma: Agar faktoriallar bilan kasrlarni qanday bekor qilish mumkinligi aniq bo'lmasa, faktorial - bu mahsulotning qisqa belgisi. Uni har doim uzun yozish mumkin va hisoblagich va maxrajda takrorlanadigan omillarni kesib o'tish mumkin. Javob bitta raqamga yaqin bo'lib chiqdi, demak, shuncha kitob bilan tasodifan berilgan ikkita jildni yonma -yon qo'yish qiyinroq. Turar joy. Joylashuvlar sonini hisoblash. Faraz qilaylik, xaridorda kitoblar ko'p va ularning barchasini ochiq javonlarga joylashtirish mumkin emas. Uning iltimosiga ko'ra, siz har qanday kitoblarning ma'lum sonini tanlab, ularni chiroyli joylashtirishingiz kerak. Chiroyli yoki chirkin bo'lib chiqdi, bu mijozning didiga bog'liq, ya'ni. u yana ko'rishni xohlaydi hamma variantlar va o'zingiz qaror qiling. Bizning vazifamiz - kitob joylashtirishning mumkin bo'lgan variantlari sonini hisoblash, uni ishontirish va oqilona cheklovlar kiritish. Vaziyatni tushunish uchun, avvalo, "ko'pchilik" 5 ta kitob, bizda faqat bitta javon bor va u faqat 3 jilddan iborat deb faraz qilaylik. Nima qilamiz? Biz 5 ta kitobdan birini tanlaymiz va uni javonga birinchi o'ringa qo'yamiz. Biz buni 5 usulda qilishimiz mumkin. Endi javonda ikkita joy qoldi va bizda 4 ta kitob qoldi. Biz ikkinchi kitobni 4 usulda tanlab, uni 5 mumkin bo'lgan birinchisining yoniga qo'yishimiz mumkin. Bunday juftliklar 5 · 4 bo'lishi mumkin. 3 ta kitob va bitta joy qoldi. 3 kitobdan bittasini 3 xil usulda tanlab, 5 · 4 juftlikdan biriga joylashtirish mumkin. Siz 5 · 4 · 3 xil uchlamli bo'lasiz. Bu shuni anglatadiki, 5 5 · 4 · 3 = 60 dan 3 ta kitobni joylashtirishning umumiy usullari mavjud. Rasmda 60 ta variantdan faqat 4 ta joylashtirish varianti ko'rsatilgan. Rasmlarni solishtiring. E'tibor bering, joylashtirishlar bir -biridan faqat elementlar tartibida farq qilishi mumkin, xuddi birinchi ikkita guruhdagidek, yoki elementlar tarkibidagi kabi. Joylashtirishlar soni formulasi. Turar joy dan n tomonidan elementlar m(joylar) bunday namunalar deyiladi, ular, ega m ma'lumotlar sonidan tanlangan elementlar n elementlar bir -biridan elementlarning tarkibi yoki joylashish tartibida farq qiladi. Joylashuvlar soni n yoqilgan m bildirilgan A n m va formula bilan aniqlanadi A n m = n·( n- 1) ( n- 2) ... ( n − m + 1) = n!/(n - m)! Keling, ushbu formula yordamida hisoblashga harakat qilaylik A n n, ya'ni dan joylashuvlar soni n yoqilgan n. A n n = n·( n-1) · ( n-2) ... ( n-n + 1) = n·( n-1) · ( n-2) ... 1 = n! Shunday qilib, A n n = P n = n! Dan joylashuvlar soni ajablanarli emas n yoqilgan n almashtirishlar soniga teng bo'lib chiqdi n elementlar, chunki biz joylashuvlarni tuzishda elementlarning butun majmuasidan foydalandik, demak ular endi elementlar tarkibida bir -biridan farq qila olmaydi, faqat joylashish tartibida, va bular almashtirishlar. 3 -muammo. Agar mavjud 30 ta kitobdan birini tanlasangiz, kitob javonida 15 jildni nechta usulda joylashtirish mumkin? Yechim.
Formulalar bo'yicha 15 ta elementning 30 ta joylashuvining umumiy sonini aniqlang
Haqiqiy kitoblarni joylashtirasizmi? Omad! Barcha variantlardan o'tish uchun qancha hayot kerakligini hisoblang. Muammo 4. Agar har birida atigi 15 jild bo'lsa, 30 ta kitobni ikkita javonga nechta usulda joylashtirish mumkin? Yechim.
I usul.
Joylashuvlar va ehtimollar nazariyasi. Ehtimollar nazariyasida, joylashtirish muammolari boshqa turdagi namunalarga qaraganda ancha kam uchraydi, chunki joylashuvlar ko'proq aniqlovchi xususiyatlarga ega - elementlarning tartibi va tarkibi, shuning uchun tasodifiy tanlanishga kam sezgir. Muammo 5. Kitob javonida bitta muallifning 6 jildlik asarlar to'plami mavjud. Xuddi shu formatdagi kitoblar aniq tartibda joylashtirilmagan. O'quvchi, qaramasdan, 3 ta kitobni oladi. U birinchi uchta jildni olish ehtimoli qanday? Yechim.
A tadbir - o'quvchi birinchi uchta jildga ega. Tanlov tartibini hisobga olgan holda, u ularni 6 usulda qabul qilishi mumkin edi. (Bu 3 elementning almashinuvi P 3 = 3! = 1 2 3 = 6, ularni ro'yxatga olish oson 123, 132, 213, 231, 312, 321.)
Kombinatsiyalar. Kombinatsiyalar sonini hisoblash. Va oxirgi holat - xaridorning barcha kitoblari bir xil rangda va bir xil o'lchamda, lekin ularning faqat bir qismini javonga qo'yish mumkin. Ko'rinib turibdiki, dizaynerda hech qanday muammo yo'q, jami kerakli miqdordagi kitobni tanlang va ularni javonga aniq tartibda joylashtiring, chunki kitoblar tashqi tomondan farq qilmaydi. Lekin ular farq qiladi va sezilarli darajada! Bu kitoblar mazmunan farq qiladi. Xaridor Shekspir fojialari qayerda va Reks Stout detektivlari qayerda, ochiq javonda yoki shkafda turgani bilan qiziqmasligi mumkin. Shunday qilib, bizda namuna elementlarining tarkibi muhim, lekin ularni joylashtirish tartibi ahamiyatsiz bo'lgan vaziyat mavjud. Rasmda "bitta muallifning 5 jildda to'plangan asarlari" dan ikkita tanlov ko'rsatilgan. Birinchisi, xaridorni ko'proq xursand qiladi, agar u bu muallifning birinchi asarlarini tez -tez o'qib chiqsa uch jild, ikkinchisi - agar u ko'pincha oxirgi jildlarga joylashtirilgan keyingi asarlarga ishora qilsa. Ikkala guruh ham bir xil darajada chiroyli (yoki bir xil darajada chirkin) ko'rinadi va guruhning 123 yoki 321 sifatida joylashuvi muhim emas. Kombinatsiyalar soni formulasi. Tartibsiz tanlovlar chaqiriladi dan n tomonidan elementlar m va bildirilgan BILAN n m. Kombinatsiyalar soni formula bilan aniqlanadi BILAN n m = n!/(n- m)! / m! Ushbu formulada ikkita bo'luvchi va belgi mavjud " / "Bu veb -sahifalarga ko'proq mos keladi. Lekin bo'linishni ikki nuqta bilan ham belgilash mumkin" : "yoki gorizontal chiziq" −−− ". Ikkinchi holda, formula shunday ko'rinadi umumiy fraktsiya, unda ketma -ket bo'linish maxrajda ikkita omil bilan ifodalanadi ... Kesirli tasvirni yaxshiroq tushunadiganlar uchun barcha formulalar sahifaning boshida va oxirida takrorlanadi. Muammo echimlarini tahlil qilganda, mening yozuvimni siz o'rgangan bilan solishtiring. Bundan tashqari, bu formuladagi barcha omillar va bo'linuvchilar ketma -ket natural sonlarning hosilalari hisoblanadi, shuning uchun kasr batafsil yozilsa yaxshi kamayishi mumkin. Ammo men muammolarning batafsil qisqartirilishini o'tkazib yubormayman, buni o'zingiz tekshirish oson. Xuddi shu boshlang'ich to'plamlar uchun n elementlar va bir xil namuna o'lchamlari (tomonidan m elementlar) kombinatsiyalar soni joylashtirishlar sonidan kam bo'lishi kerak. Darhaqiqat, har bir tanlangan guruh uchun joylashishni hisoblashda biz tanlanganlarning barcha almashinuvlarini ham hisobga olamiz m elementlar va kombinatsiyalarni hisoblashda almashtirishlar hisobga olinmaydi: C n m = A n m/P m = n!/(n - m)!/m! Muammo 6. 15 ta jildni kitob javoniga qanday joylashtirish mumkin, agar siz ularni mavjud 30 ta kitobdan tanlasangiz? Yechim.
Biz bu muammoni ichki dizayner ishi nuqtai nazaridan hal qilamiz, shuning uchun tokchada bir xil ko'rinadigan 15 ta kitobning tartibi muhim emas. Formulada 15 ta 30 ta elementning umumiy kombinatsiyasini aniqlash kerak
Muammo 7. Bir -biridan farq qilmaydigan 30 ta kitobni ikkita javonga nechta usulda joylashtirish mumkin, agar ularning har birida atigi 15 jild bo'lsa? Agar biz bu savolga ichki dizayner nuqtai nazaridan yana javob bersak, har bir tokchadagi kitoblarning tartibi ahamiyatsiz. Lekin kitoblar javonlar orasida qanday taqsimlanishi xaridorga qiziq bo'lishi mumkin yoki bo'lmasligi mumkin. 1) Masalan, agar ikkala javon yonma -yon bo'lsa, ikkalasi ham bir xil balandlikda ochiq bo'lsa, xaridor bu muhim emas deb ayta oladi. Keyin javob aniq - 1 usul, chunki aranjirovka 30 ta kitobdan iborat bo'lib, hech qanday almashish hisobga olinmaydi. 2) Lekin javonlardan biri juda baland bo'lsa, xaridor uchun qaysi kitoblar joylashganligi muhim. Bu holda, javob oldingi muammadagi kabi bo'ladi - 155117520 usullar, chunki biz birinchi javonni 30 dan 15 gacha kombinatsiyali tanlovlar bilan to'ldiramiz, ikkinchisida esa qolgan 15 ta kitobni almashtirishlarni hisobga olmasdan joylashtiramiz. Shunday qilib, muammolarning shunday formulalari borki, ularning javoblari noaniq bo'lishi mumkin. Aniq echim uchun biz odatda vaziyat kontekstidan oladigan qo'shimcha ma'lumotga muhtojmiz. Imtihon topshiriqlarini yaratuvchilar, qoida tariqasida, muammoning holatini ikki tomonlama izohlashga yo'l qo'ymaydilar, ular uni biroz uzoqroq shakllantiradi. Ammo, agar shubhangiz bo'lsa, o'qituvchingizdan so'rash yaxshidir. Kombinatsiyalar va ehtimollar nazariyasi. Ehtimollar nazariyasida kombinatsion muammolar eng ko'p uchraydi, chunki tartibsiz guruhlash aniqrog'i ajratib bo'lmaydigan elementlar uchun muhimroqdir. Agar ba'zi elementlar bir-biridan sezilarli farq qilsa, ularni tasodifiy tanlash qiyin, tasodifiy bo'lmagan tanlash bo'yicha ko'rsatmalar mavjud. Muammo 8. Kitob javonida bitta muallifning 6 jildlik asarlar to'plami mavjud. Kitoblar xuddi shunday bezatilgan va aniq tartibda joylashmagan. O'quvchi tasodifan 3 ta kitobni oladi. U birinchi uchta jildni olish ehtimoli qanday? Yechim.
A tadbir - o'quvchi birinchi uchta jildga ega. Bular 1, 2 va 3 -jildlar. U kitoblarni tanlash tartibini hisobga olmagan holda, faqat yakuniy natijaga ko'ra, u ularni bir yo'l bilan qabul qilishi mumkin edi. Qulay elementar tadbirlar soni - 1.
Bu muammoni 5 -muammo bilan solishtiring (joylashtirishda). Ikkala muammoning ham shartlari juda o'xshash va javoblari juda o'xshash. Aslida, bu xuddi shu kundalik vaziyat va shunga ko'ra, xuddi shu vazifa, u yoki bu tarzda talqin qilinishi mumkin. Asosiysi shundaki, ham ijobiy, ham mumkin bo'lgan oddiy hodisalarni hisoblashda vaziyatni bir xil tushunish mumkin. Xulosa so'zlar. Barcha formulalarni qat'iy chiqarish uchun (men bu erda bermaganman) foydalaning kombinatorikaning ikkita asosiy qoidasi: Ko'paytirish qoidasi (qoida " va"). Unga ko'ra, agar A elementni tanlash mumkin bo'lsa n yo'llar va har qanday A tanlovi uchun B elementini tanlash mumkin m yo'llar, keyin A juftligi va B ni tanlash mumkin n m yo'llar. Bu qoida ketma -ketlikning ixtiyoriy uzunligiga umumlashtiriladi. Qo'shish qoidasi (qoida " yoki"). Unda aytilishicha, agar A elementni tanlash mumkin n usullari va B elementini tanlash mumkin m yo'llar, keyin A ni tanlang yoki B mumkin n + m yo'llar. Bu qoidalar muammolarni hal qilish uchun ham zarur. Kontseptsiya faktorial nolga ham tegishli: 0! = 1 , chunki bo'sh to'plamni o'ziga xos tarzda buyurtma qilish mumkin. Kalkulyatorda ko'p sonli faktoriallarni to'g'ridan -to'g'ri ko'paytirish orqali hisoblash juda uzun va juda katta sonlar - hatto kompyuterda ham tez emas. Kompyuterlar va hisob mashinalari yaratilishidan oldin bu bilan qanday shug'ullangansiz? 18 -asr boshlarida J. Stirling va undan mustaqil ravishda A. Moivre faktoriyalarni taxminiy hisoblash formulasini olgan, bu aniqroq. ko'proq raqam n... Endi bu formula deyiladi Stirling formulasi bo'yicha: Yakuniy qiyinchilik. Kombinatorial usullar yordamida ehtimollik nazariyasidagi muammolarni echishda, namunaning turini to'g'ri tanlash uchun taklif qilingan vaziyatni sinchkovlik bilan tahlil qilish kerak. Buni quyidagi muammo bilan sinab ko'ring. Buni hal qiling, javobni taqqoslang va tugmani bosib, mening yechimni oching. Muammo 9. 6 ta sazan va 4 ta sazan, 5 ta baliq to'r bilan ushlangan akvariumdan. Ularning orasida 2 ta sazan va 3 ta sazan bo'lishi ehtimoli qanday? Yechim.
Boshlang'ich voqea "to'rda 5 baliqdan iborat guruh" dir. A tadbir - "5 baliq tutilgan orasida 3 sazan bor edi va 2 sazan ".
Izohlar.
2) E'tibor bering, biz "i-qoida" dan foydalanamiz, chunki "va" birlashmasi to'g'ridan-to'g'ri A hodisasining tavsifida, buning uchun biz ikki guruhning birgalikda tutilish ehtimolini hisoblashimiz kerak. Biroq, biz uni namunalarning mustaqilligiga ishonch hosil qilganimizdan keyingina qo'llaymiz. Darhaqiqat, to'rga suzib borayotgan sazan u erdagi birodarlarini sanay olmaydi va sazanga: "Navbat sizniki, biznikidan ikkitasi bor", deb aytolmaydi. Sazan sazanni xushnud etish uchun to'rga chiqishga rozi bo'ladimi? Ammo agar ular kelisha olsalar, bu qoida endi qo'llanilmaydi. Shartli ehtimollik tushunchasiga murojaat qilish kerak bo'lardi. Javob: 0,238. Yechimni ko'rsatish. Agar siz maktab bitiruvchisi bo'lsangiz va USE -ni qabul qilsangiz, ushbu bo'limni o'rganib chiqqandan so'ng, kombinatsion elementlar yordamida va ularsiz hal qilinishi mumkin bo'lgan (matematikada USE 2020 profil darajalari uchun 10 ta asosiy va 4 ta) qaytaring. Masalan, tanga tashlash). Muammoni hal qilishning mumkin bo'lgan usullaridan qaysi biri sizga ko'proq yoqadi? Va agar siz tanlov turini tezda aniqlashni va kerakli formulalarni topishni o'rganish uchun kombinatoriy muammolarni hal qilishda biroz ko'proq mashq qilmoqchi bo'lsangiz, sahifaga o'ting. Do'stlar! Menda bu o'lik daftar bor, shuning uchun men sizdan kecha uchta fizik, ikki iqtisodchi, bitta Politexnika universiteti va bitta gumanist kurashgan muammoni so'rash uchun foydalanaman. Biz butun miyamizni sindirib tashladik va biz doimo turli natijalarga erishmoqdamiz. Balki sizning orangizda dasturchilar va matematik daholar bordir, bundan tashqari, vazifa umuman maktab va juda oson, biz formulani chiqarmaymiz. Chunki biz aniq fanlarni o'rganishni to'xtatdik va buning o'rniga, negadir, kitob yozamiz va rasm chizamiz. Kechirasiz. Shunday qilib, fon. Menga yangi bank kartasi berildi va men odatdagidek uning pin -kodini oson topdim. Lekin ketma -ket emas. Aytmoqchimanki, aytaylik, pin -kod 8794 edi, men uni 9748 deb atadim. Ya'ni, men g'olibman. barcha raqamlarni taxmin qildi bu to'rt xonali raqamda mavjud edi. Xo'sh, ha, raqamning o'zi emas, lekin faqat uning tarkibiy qismlari bor hayron bo'ldi. Ammo raqamlar hammasi to'g'ri! QAYD - Men tasodifan harakat qildim, ya'ni ma'lum bo'lgan raqamlarni to'g'ri tartibda joylashtirishim shart emas edi, men faqat ruhda harakat qildim: bu erda menga noma'lum to'rtta raqam bor va men ishonamanki, ular orasida bo'lishi mumkin 9, 7, 4 va 8, va ularning tartibi muhim emas. Biz darhol hayron bo'ldik menda qancha variant bor edi(ehtimol, men buni qabul qilganim va taxmin qilganim qanchalik yaxshi ekanligini tushunish uchun). Ya'ni, to'rtta raqamning nechta kombinatsiyasini tanlashim kerak edi? Va keyin, tabiiyki, do'zax boshlandi. Bizning boshimiz kechqurun portladi va natijada hamma boshqacha javob berdi! Men hatto bu kombinatsiyalarning barchasini ketma -ket daftarga yozishni boshladim, lekin ularning soni to'rt yuzdan oshganini tushundim (har holda bu fizik Threshning javobini rad etdi). Menda to'rt yuz kombinatsiya bor edi, lekin baribir aniq emas edi) - va taslim bo'ldi. Aslida, savolning mohiyati. To'rt xonali sonda mavjud bo'lgan to'rtta raqamni (har qanday tartibda) taxmin qilish ehtimoli qanday? Yoki yo'q, biz buni aniqroq va ravshan qilish uchun (men gumanistman, meni kechiring, garchi menda matematikaning har doim katta zaifligi bo'lsa ham) qayta tuzamiz. necha takrorlanmaydigan raqamlarning kombinatsiyasi 0 dan 9999 gacha bo'lgan tartib sonlar qatorida mavjudmi? ( Iltimos, buni "nechta kombinatsiya" degan savol bilan adashtirmang takrorlanmaydigan raqamlar "!!! raqamlar takrorlanishi mumkin! Aytmoqchimanki, bu holda 2233 va 3322 bir xil kombinatsiyadir !!). Yoki aniqrog'i. Men o'ntadan bittasini to'rt marta taxmin qilishim kerak. Lekin ketma -ket emas. Xo'sh, yoki boshqa narsa. Umuman olganda, kartaning pin -kodi hosil bo'lgan raqamli kombinatsiya uchun menda qancha variant borligini aniqlash kerak. Yordam bering, yaxshi odamlar! Iltimos, yordam bering, darhol bu 9999 variantlari haqida yozishni boshlamang(kecha hamma boshiga tushdi) chunki bu bema'nilik - axir, bizni tashvishga soladigan nuqtai nazardan, 1234 raqami, 3421 raqami, 4312 raqami va boshqalar. xuddi shu! Xo'sh, ha, raqamlarni takrorlash mumkin, chunki 1111 yoki u erda pin-kod mavjud, masalan, 0007. Siz pin-kod o'rniga mashina raqamini ko'rsatishingiz mumkin. Aytaylik, avtomobil raqamini tashkil etuvchi yagona raqamlarni taxmin qilish ehtimoli qanday? Yoki ehtimollik nazariyasini butunlay olib tashlash uchun - nechta raqamli kombinatsiyani tanlashim kerak edi? Iltimos, javoblaringizni va fikrlaringizni aniq formulalar bilan qo'llab -quvvatlang, chunki kecha biz deyarli aqldan ozganmiz. Oldindan katta rahmat! P.S. Bir aqlli odam, dasturchi, rassom va ixtirochi, juda to'g'ri taklif qilgan to'g'ri yechim muammolar, menga bir necha daqiqa ajoyib kayfiyat bag'ishladi: " muammoning echimi shunda: u obsesif-kompulsiv kasallikka chalingan bo'lsa, davolanish: turmushga chiq va pomidor bilan bog'lan. Men uning o'rnida "ehtimollik nima" degan savol emas, balki "men bu raqamlarning barchasiga e'tibor beramanmi" degan savoldan ko'proq tashvishlanardim. Umuman olganda, qo'shadigan hech narsa yo'q :) Quyidagi kalkulyator n dan m gacha bo'lgan barcha elementlarning kombinatsiyasini yaratish uchun mo'ljallangan. Bunday kombinatsiyalar sonini kombinatsion elementlar kalkulyatori yordamida hisoblash mumkin. Permutatsiyalar, joylashtirish, kombinatsiyalar. Kalkulyator ostida ishlab chiqarish algoritmining tavsifi. Algoritm
Keling, algoritmning misolini ko'rib chiqaylik. Oddiylik uchun indekslari 1, ya'ni 1 2 3 4 5 bilan boshlanadigan beshta elementni ko'rib chiqing. M = 3 o'lchamdagi barcha kombinatsiyalarni yaratish kerak. Birinchidan, berilgan m hajmining birinchi kombinatsiyasi ishga tushiriladi - indekslar o'sish tartibida 1 2 3 Keyin oxirgi element tekshiriladi, ya'ni i = 3. Agar uning qiymati n - m + i dan kichik bo'lsa, u holda 1 ga ko'payadi. 1 2 4 Oxirgi element yana tekshiriladi va yana ortadi. 1 2 5 Endi elementning qiymati mumkin bo'lgan maksimalga teng: n - m + i = 5 - 3 + 3 = 5, i = 2 bo'lgan oldingi element tekshiriladi. Agar uning qiymati n - m + i dan kichik bo'lsa, u 1 ga ko'paytiriladi va keyingi barcha elementlar uchun qiymat oldingi elementning qiymatiga 1 ga teng bo'ladi. 1 (2+1)3 (3+1)4 = 1 3 4 Keyin yana i = 3 uchun chek bor. 1 3 5 Keyin - i = 2 ni tekshiring. 1 4 5 Keyin navbat i = 1 bo'ladi. (1+1)2 (2+1)3 (3+1)4 = 2 3 4 Va yana, 2 3 5 2 4 5 3 4 5 - oxirgi kombinatsiya, chunki uning barcha elementlari n - m + i ga teng. Ga qaramay muhim rol PIN -kodlar global infratuzilmada bo'lsa -da, odamlar PIN -kodlarni qanday tanlashlari to'g'risida hali ilmiy tadqiqotlar o'tkazilmagan. Kembrij universiteti tadqiqotchilari Soren Preibush va Ross Anderson vaziyatni tuzatib, dunyodagi birinchi nashrni nashr etishdi miqdoriy tahlil 4-raqamli bank PIN-kodini topish qiyinligi. Tadqiqotchilar bank bo'lmagan manbalardan va onlayn so'rovnomalardan parollar oqishi haqidagi ma'lumotlardan foydalanib, PIN-kodlarni tanlash foydalanuvchilar uchun veb-saytlar uchun parol tanlashdan ko'ra jiddiyroq ekanligini aniqladilar: aksariyat kodlar deyarli tasodifiy raqamlar to'plamini o'z ichiga oladi. Shunga qaramay, boshlang'ich ma'lumotlar orasida oddiy kombinatsiyalar ham, tug'ilgan kunlar ham bor - bu omadli bo'lsa, tajovuzkor kerakli kodni taxmin qilishi mumkin. Tadqiqotning boshlang'ich nuqtasi RockYou ma'lumotlar bazasidagi 4 ta raqamli ketma-ketlik ketma-ketligi (1,7 million) va iPhone ekranini qulflash dasturining 200 ming PIN-kodlari ma'lumotlar bazasi edi (ma'lumotlar bazasi ishlab chiqaruvchi tomonidan taqdim etilgan). dastur Daniel Amitay). Bu ma'lumotlarga asoslangan grafikalarda qiziqarli naqshlar paydo bo'ladi-sanalar, yillar, takrorlanadigan raqamlar va hatto 69 bilan tugaydigan PIN-kodlar. Bu kuzatuvlar asosida olimlar har bir PIN-kodning mashhurligini baholaydigan chiziqli regressiya modelini yaratdilar. Kod 25 DDMM sanasi bo'ladimi, bu ketma -ket ketma -ketlikmi va hokazo. Ushbu umumiy shartlar har bir to'plamdagi PIN-kodlarning 79% va 93% ga bajariladi. Shunday qilib, foydalanuvchilar bir nechta oddiy omillarga asoslanib 4 xonali kodlarni tanlaydilar. Agar bank PIN-kodlari shu tarzda tanlangan bo'lsa, ularning 8-9 foizini atigi uchta urinishda taxmin qilish mumkin edi! Albatta, odamlar bank kodlariga ko'proq e'tibor berishadi. Haqiqiy bank ma'lumotlarining katta to'plami bo'lmagan taqdirda, tadqiqotchilar haqiqiy PIN-kodlar ko'rib chiqilganlardan qanday farq qilishini baholash uchun 1300 dan ortiq odam bilan intervyu o'tkazdilar. Tadqiqotning o'ziga xos xususiyatlarini inobatga olgan holda, respondentlardan kodlarning o'zi haqida emas, balki ularning yuqoridagi omillarning har biriga mos kelishi (o'sish, DDMM formati va boshqalar) so'ralgan. Ma'lum bo'lishicha, odamlar haqiqatan ham bank PIN-kodlarini tanlashda ancha ehtiyotkor bo'lishgan. So'ralganlarning to'rtdan bir qismi bank tomonidan ishlab chiqarilgan tasodifiy PIN -koddan foydalanadi. Uchdan biridan ko'prog'i eski telefon raqamini, talabalik guvohnomasi raqamini yoki tasodifiy ko'rinadigan boshqa raqamlar to'plamidan foydalanib PIN kodini tanlaydi. Olingan natijalarga ko'ra, karta egalarining 64 foizi soxta tasodifiy PIN-koddan foydalanadilar, bu esa bank bo'lmagan kodlar bilan o'tgan tajribalarda 23-27 foizdan ko'p. Yana 5% raqamli naqshdan foydalanadi (masalan, 4545), 9% esa klaviatura naqshini afzal ko'radi (masalan, 2684). Umuman olganda, oltita urinish bilan (uchtasi bankomat bilan va uchtasi to'lov terminali bilan) tajovuzkorning boshqa birovning kartasi PIN -kodini taxmin qilish ehtimoli 2% dan kam. — Источник: https://muegn.ru/uz/encyclopedia/elementy-kombinatoriki-kombinatorika-osnovnye-pravila-i-formuly-skolko.html © muegn.ru Download 38.85 Kb. Do'stlaringiz bilan baham: 
|