KOMBINATORIKA
Kombinatorika - matematikaning ma'lum bir asosiy to'plamdan elementlarni berilgan qoidalarga muvofiq tanlash va joylashtirish masalalarini o'rganadigan bo'limi. Kombinatorikaning formulalari va tamoyillari ehtimollar nazariyasida tasodifiy hodisalarning ehtimolini hisoblash va shunga mos ravishda taqsimot qonunlarini olish uchun ishlatiladi. tasodifiy o'zgaruvchilar. Bu, o'z navbatida, tabiatda va texnologiyada o'zini namoyon qiladigan statistik qonuniyatlarni to'g'ri tushunish uchun juda muhim bo'lgan ommaviy tasodifiy hodisalarning qonuniyatlarini o'rganish imkonini beradi.
Kombinatorikada qo'shish va ko'paytirish qoidalari
Jamlama qoidasi. Agar ikkita A va B harakat bir-birini istisno qilsa va A harakat m usulda, B n ta usulda bajarilishi mumkin bo'lsa, u holda bu harakatlardan biri (A yoki B) n + m usulda bajarilishi mumkin.
1-misol.
Sinfda 16 o'g'il va 10 qiz. Bitta navbatchini necha xil usulda belgilashingiz mumkin?
Yechim
Yoki o'g'il yoki qiz vazifaga tayinlanishi mumkin, ya'ni. navbatchi 16 nafar o‘g‘il yoki 10 nafar qizning har biri bo‘lishi mumkin.
Yig‘indi qoidasidan foydalanib, bitta navbatchini 16+10=26 usulda tayinlash mumkinligini aniqlaymiz.
Mahsulot qoidasi. Ketma-ket bajarilishi kerak bo'lgan k harakat bo'lsin. Agar birinchi harakatni n ta usulda, ikkinchi harakatni n ta usulda, uchinchisini n ta 3 usulda va shunga o'xshash n k ta usulda bajarish mumkin bo'lgan k-harakatgacha davom etishi mumkin bo'lsa, u holda barcha k harakatni birgalikda bajarish mumkin. :
yo'llari.
2-misol.
Sinfda 16 o'g'il va 10 qiz. Ikki navbatchi necha usulda tayinlanishi mumkin?
Yechim
Birinchi navbatchi sifatida o'g'il yoki qiz tayinlanishi mumkin. Chunki Sinfda 16 o'g'il va 10 qiz bor, keyin birinchi navbatchini 16+10=26 usulda belgilashingiz mumkin.
Birinchi navbatchini tanlaganimizdan so'ng, qolgan 25 kishidan ikkinchisini tanlashimiz mumkin, ya'ni. 25 yo'l.
Ko'paytirish teoremasiga ko'ra, ikkita yordamchini 26*25=650 usulda tanlash mumkin.
Takrorlashsiz kombinatsiyalar. Takrorlashlar bilan kombinatsiyalar
Kombinatorikaning klassik muammosi - bu takrorlanmaydigan kombinatsiyalar soni muammosi, uning mazmuni savol bilan ifodalanishi mumkin: necha yo'llari mumkin tanlang m dan n turli xil elementlar?
3-misol.
Sovg'a sifatida mavjud bo'lgan 10 xil kitobdan 4 tasini tanlashingiz kerak. Buni necha usulda qilish mumkin?
Yechim
Biz 10 ta kitobdan 4 tasini tanlashimiz kerak va tanlov tartibi muhim emas. Shunday qilib, siz 4 ta 10 ta elementdan iborat kombinatsiyalar sonini topishingiz kerak:
.
Takrorlashlar bilan kombinatsiyalar soni masalasini ko'rib chiqing: n xil turdagi har birining r bir xil ob'ektlari mavjud; necha yo'llari mumkin tanlang m() dan bular (n*r) elementlar?
.
4-misol.
Qandolat do'konida 4 turdagi tortlar sotilgan: napoleonlar, eklerlar, pirojnoe va puff pastries. 7 ta tortni necha xil usulda sotib olish mumkin?
Yechim
Chunki 7 ta tort orasida bir xil turdagi keklar bo'lishi mumkin, keyin 7 ta tortni sotib olish mumkin bo'lgan usullar soni 7 dan 4 gacha bo'lgan takroriy kombinatsiyalar soniga qarab belgilanadi.
.
Takrorlanmasdan joylashtirish. Takrorlashlar bilan joylashtirish
Kombinatorikadagi klassik muammo - bu takrorlanmasdan joylashtirishlar soni muammosi, uning mazmuni savol bilan ifodalanishi mumkin: necha yo'llari mumkin tanlang Va post tomonidan m boshqacha joylar m dan n boshqacha buyumlar?
5-misol.
Ba'zi gazetalar 12 sahifadan iborat. Ushbu gazeta sahifalarida to'rtta fotosuratni joylashtirish kerak. Agar gazetaning hech bir sahifasida bir nechta fotosurat bo'lmasa, buni necha usul bilan amalga oshirish mumkin?
Yechim.
Bu vazifada biz faqat fotosuratlarni tanlamaymiz, balki ularni gazetaning ma'lum sahifalariga joylashtiramiz va gazetaning har bir sahifasida bittadan ortiq fotosurat bo'lmasligi kerak. Shunday qilib, muammo 4 ta elementning 12 ta elementini takrorlamasdan joylashtirish sonini aniqlashning klassik muammosiga tushiriladi:
Shunday qilib, 12 sahifadagi 4 ta fotosuratni 11 880 ta usulda joylashtirish mumkin.
Kombinatorikaning klassik muammosi - bu takroriy joylashtirishlar soni muammosi, uning mazmuni savol bilan ifodalanishi mumkin: necha yo'llari mumkin Sizbarmiya Va post tomonidan m boshqacha joylar m dan n ta element,Bilantayyor qaysi Mavjud xuddi shu?
6-misol.
Bolaning stol o‘yinlari to‘plamida hali ham 1, 3 va 7 raqamlari yozilgan markalar bor edi.U bu markalar yordamida barcha kitoblarga besh xonali raqamlarni qo‘yib, katalog yaratishga qaror qildi. O'g'il bola necha xil besh xonali sonlarni yaratishi mumkin?
Takrorlashsiz almashtirishlar. Takrorlashlar bilan almashtirishlar
Kombinatorikaning klassik muammosi - takrorlanmasdan almashtirishlar soni muammosi, uning mazmuni savol bilan ifodalanishi mumkin: necha yo'llari mumkin post n har xil buyumlar yoqilgan n boshqacha joylar?
7-misol.
“Nikoh” so‘zining harflaridan nechta to‘rt harfli “so‘z” yasash mumkin?
Yechim
Umumiy aholi "nikoh" so'zining 4 ta harfi (b, p, a, k). "So'zlar" soni ushbu 4 ta harfning almashtirilishi bilan belgilanadi, ya'ni.
Tanlangan n ta element orasida bir xil (qaytish bilan tanlash) mavjud bo'lsa, takroriy almashtirishlar soni masalasini savol bilan ifodalash mumkin: Agar n ta ob'ekt orasida n ta turli xil (k) bo'lsa, n ta turli joyda joylashgan n ta ob'ektni necha xil usulda joylashtirish mumkin?< n), т. е. есть одинаковые предметы.
8-misol.
"Mississipi" so'zining harflaridan nechta turli harf birikmalarini yasash mumkin?
Yechim
1 ta “m”, 4 ta “i”, 3 ta “c” va 1 ta “p” harfi, jami 9 ta harf bor. Shuning uchun takroriy takroriy almashtirishlar soni teng
"KOMBİNATORIKA" BO'limi UCHUN XULOSA
Barcha N elementlar va hech biri takrorlanmaydi, keyin bu almashtirishlar soni bilan bog'liq muammo. Yechimni oddiy topish mumkin. Qatorda birinchi o'rin har qanday N element bo'lishi mumkin, shuning uchun N ta variant mavjud. Ikkinchi o'rinda - har qanday, birinchi o'rin uchun allaqachon ishlatilganidan tashqari. Shuning uchun, allaqachon topilgan N variantning har biri uchun (N - 1) ikkinchi o'rin variantlari mavjud va kombinatsiyalarning umumiy soni N* (N - 1) ga aylanadi.
Xuddi shu narsa seriyaning qolgan elementlari uchun ham takrorlanishi mumkin. Eng oxirgi o'rin uchun faqat bitta variant qoldi - oxirgi qolgan element. Oxirgi variant uchun ikkita variant mavjud va hokazo.
Shuning uchun N takrorlanmaydigan elementlar qatori uchun mumkin bo'lgan almashtirishlar 1 dan N gacha bo'lgan barcha butun sonlarning ko'paytmasiga teng. Bu ko'paytma N ning faktoriali deyiladi va N bilan belgilanadi! ("en faktorial" ni o'qing).
Oldingi holatda, mumkin bo'lgan elementlarning soni va qatordagi joylar soni bir-biriga to'g'ri keldi va ularning soni N ga teng edi. Ammo qatorda mumkin bo'lgan elementlardan kamroq joylar mavjud bo'lganda vaziyat mumkin. Boshqacha qilib aytganda, namunadagi elementlarning soni ma'lum M soniga va M ga teng< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Birinchidan, umumiy sonni hisoblashingiz kerak bo'lishi mumkin mumkin bo'lgan usullar, bu N dan M elementni qatorga joylashtirish uchun ishlatilishi mumkin.Bunday usullar joylashtirishlar deyiladi.
Ikkinchidan, tadqiqotchini N dan M elementni tanlash mumkin bo'lgan usullarning soni qiziqtirishi mumkin. Bu holda, elementlarning tartibi endi muhim emas, lekin har qanday ikkita variant bir-biridan kamida bitta element bilan farq qilishi kerak. . Bunday usullar kombinatsiyalar deb ataladi.
M elementning N dan joylashuvi sonini topish uchun siz almashtirishdagi kabi fikr yuritish usuliga murojaat qilishingiz mumkin. Birinchi navbatda hali ham N element, ikkinchi o'rinda N - 1 va hokazo bo'lishi mumkin. Ammo oxirgi o'rin uchun mumkin bo'lgan variantlar soni bittaga teng emas, lekin (N - M + 1), chunki joylashtirish tugagach, hali ham (N - M) foydalanilmagan elementlar bo'ladi.
Shunday qilib, N dan M elementning joylashuvi soni (N - M + 1) dan N gacha bo'lgan barcha butun sonlarning ko'paytmasiga teng yoki bir xil bo'lgan N!/(N - M) bo'lak!
Shubhasiz, N dan M elementlarning kombinatsiyasi soni joylashtirish sonidan kamroq bo'ladi. Har bir mumkin bo'lgan kombinatsiya uchun M mavjud! bu kombinatsiya elementlarining tartibiga qarab mumkin bo'lgan joylashtirishlar. Shuning uchun bu miqdorni topish uchun M elementning joylashuv sonini N dan N ga bo'lish kerak! Boshqacha qilib aytganda, N dan M elementning birikmalari soni N!/(M!*(N - M)!) ga teng.
Do'stlar! Menda bu o'lik daftar borligi sababli, men kechagi uchta fizik, ikkita iqtisodchi, biri politexnikadan biri va yana biri gumanitar fanlardan qiynalayotgan muammoni so'rash uchun foydalanaman. Biz butun miyamizni sindirib tashladik va biz doimo turli xil natijalarga erishamiz. Ehtimol, sizning orangizda dasturchilar va matematik daholar bordir, bundan tashqari, muammo umuman maktab va juda oson, biz formulani aniqlay olmaymiz. Chunki biz o'qishni tashladik aniq fanlar va uning o'rniga, negadir, biz kitoblar yozamiz va rasm chizamiz. Kechirasiz.
Shunday qilib, fon.
Menga yangi bank kartasi berildi va men odatdagidek uning PIN kodini o'ynab taxmin qildim. Lekin ketma-ket emas. Aytmoqchimanki, PIN-kod 8794 edi, men esa 9748 dedim. Ya'ni, g'alaba qozondim. barcha raqamlarni taxmin qildi, bu to'rt xonali raqamda mavjud edi. Xo'sh, ha, raqamning o'zi emas, lekin shunchaki uning tarkibiy qismlari Men ... bilishni xohlardim. Ammo barcha raqamlar to'g'ri! QAYD - Men tasodifiy harakat qildim, ya'ni allaqachon ma'lum bo'lgan raqamlarni to'g'ri tartibda joylashtirishim shart emas edi, men shunchaki ruhda harakat qildim: bu erda menga to'rtta noma'lum raqam bor va ular orasida bo'lishi mumkinligiga ishonaman. 9, 7, 4 va 8 va ularning tartibi muhim emas. Biz darhol o'zimizga savol berdik: Menda nechta variant bor edi?(ehtimol, bu qanchalik ajoyib ekanligini tushunish uchun men uni oldim va taxmin qildim). Ya'ni, men to'rtta raqamning nechta kombinatsiyasini tanlashim kerak edi? Va keyin, tabiiyki, jahannam bo'shab ketdi. Kechqurun boshimiz portlab ketdi va oxir-oqibat barchamiz mutlaqo chiqdik turli xil variantlar javob bering! Men hatto bu kombinatsiyalarning barchasini ketma-ket daftarga yozishni boshladim, chunki ular ko'paydi, lekin to'rt yuzta men ularning to'rt yuzdan ortiq ekanligini angladim (har holda, bu fizik Thrashning javobini rad etdi, u meni ishontirdi. to'rt yuz kombinatsiya bor edi, lekin bu hali ham aniq emas) - va taslim bo'ldi.
Aslida, savolning mohiyati. To'rt xonali sonda joylashgan to'rtta raqamni (har qanday tartibda) taxmin qilish ehtimoli qanday?
Yoki bo'lmasa, keling, uni aniqroq va aniqroq qilish uchun uni qayta ta'riflaylik (men gumanistman, meni kechiring, garchi men matematika uchun doimo juda zaif bo'lganman). Necha takrorlanmaydigan 0 dan 9999 gacha tartib sonlar qatoridagi sonlar birikmasi? ( Iltimos, buni "qancha kombinatsiyalar" degan savol bilan aralashtirib yubormang takrorlanmaydigan raqamlar"!!! raqamlar takrorlanishi mumkin! Aytmoqchimanki, 2233 va 3322 bu holda bir xil kombinatsiyadir!).
Yoki aniqroq. Men to'rt marta o'ntadan bitta raqamni taxmin qilishim kerak. Lekin ketma-ket emas.
Xo'sh, yoki boshqa narsa. Umuman olganda, men kartaning PIN-kodi tuzilgan raqamli kombinatsiya uchun qancha variant borligini aniqlashim kerak. Yordam bering, yaxshi odamlar! Iltimos, yordam berayotganda, bular uchun 9999 ta variant borligini darhol yozishni boshlamang(kecha hammaning xayoliga shu narsa keldi), chunki bu bema'nilik - axir, bizni xavotirga soladigan nuqtai nazardan, 1234 raqami, 3421 raqami, 4312 raqami va boshqalar. xuddi shu narsa! Xo'sh, ha, raqamlar takrorlanishi mumkin, chunki PIN-kod 1111 yoki, masalan, 0007. PIN-kod o'rniga avtomobil raqamini tasavvur qilishingiz mumkin. Aytaylik, avtomobil raqamini tashkil etuvchi barcha bir xonali raqamlarni taxmin qilish ehtimoli qanday? Yoki ehtimollik nazariyasini butunlay olib tashlash uchun - nechta raqam birikmasidan birini tanlashim kerak edi?
Iltimos, javoblaringizni va mulohazalaringizni aniq formulalar bilan qo'llab-quvvatlang, chunki kecha biz aqldan ozgan edik. Barchangizga oldindan katta rahmat!
P.S. Bir aqlli odam, dasturchi, rassom va ixtirochi, muammoning to'g'ri echimini juda to'g'ri taklif qildi va menga bir necha daqiqa ajoyib kayfiyat bag'ishladi: " Muammoning yechimi shunday: u obsesif-kompulsiv buzuqlikka ega, davolash bu: turmushga chiqish va tepalik pomidor. Agar men uning o'rnida bo'lsam, meni "ehtimollik nima" degan savol emas, balki "nima uchun bu raqamlarning barchasiga e'tibor beryapman" degan savol qiziqtirgan bo'lardi? Umuman olganda, qo'shadigan hech narsa yo'q :)
Quyidagi kalkulyator n dan m ta elementning barcha kombinatsiyalarini yaratish uchun mo'ljallangan.
Bunday kombinatsiyalar sonini "Combinatorics Elements" kalkulyatori yordamida hisoblash mumkin. Permutatsiyalar, joylashtirishlar, kombinatsiyalar.
Kalkulyator ostida generatsiya algoritmining tavsifi.
Algoritm
Kombinatsiyalar leksikografik tartibda hosil qilinadi. Algoritm to'plam elementlarining tartib indekslari bilan ishlaydi.
Keling, misol yordamida algoritmni ko'rib chiqaylik.
Taqdimotning soddaligi uchun indekslari 1 dan boshlanadigan besh elementdan iborat to'plamni ko'rib chiqing, ya'ni 1 2 3 4 5.
m = 3 o'lchamdagi barcha kombinatsiyalarni yaratish talab qilinadi.
Berilgan o'lchamdagi m birinchi kombinatsiyasi birinchi bo'lib ishga tushiriladi - o'sish tartibida indekslar
1 2 3
Keyinchalik, oxirgi element tekshiriladi, ya'ni i = 3. Agar uning qiymati n - m + i dan kichik bo'lsa, u 1 ga oshiriladi.
1 2 4
Oxirgi element yana tekshiriladi va yana ko'paytiriladi.
1 2 5
Endi elementning qiymati maksimal mumkin bo'lgan qiymatga 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 oshiriladi va undan keyingi barcha elementlar uchun qiymat oldingi elementning qiymatiga plyus 1 ga teng bo'ladi.
1 (2+1)3 (3+1)4 = 1 3 4
Keyin yana i = 3 ni tekshiramiz.
1 3 5
Keyin i = 2 ni tekshiring.
1 4 5
Keyin i = 1 ning navbati keladi.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
Va bundan keyin,
2 3 5
2 4 5
3 4 5
- oxirgi kombinatsiya, chunki uning barcha elementlari n - m + i ga teng.
Dunyo infratuzilmasida PIN-kodlarning muhim roliga qaramay, odamlar PIN-kodlarni qanday tanlashlari haqida hech qanday akademik tadqiqotlar o'tkazilmagan.
Kembrij universiteti tadqiqotchilari Sören Preibush va Ross Anderson dunyoda birinchi bo'lib nashr etish orqali vaziyatni tuzatdilar. miqdoriy tahlil 4 xonali bank PIN kodini taxmin qilishda qiyinchilik.
Bankdan tashqari manbalardan va onlayn soʻrovlardan parollar sizib chiqishi haqidagi maʼlumotlardan foydalanib, olimlar foydalanuvchilar PIN-kodlarni tanlashga veb-saytlar uchun parollarni tanlashdan koʻra jiddiyroq yondashishlarini aniqladilar: aksariyat kodlarda deyarli tasodifiy raqamlar toʻplami mavjud. Biroq, dastlabki ma'lumotlar orasida oddiy kombinatsiyalar va tug'ilgan kunlar ham mavjud - ya'ni omad bilan tajovuzkor qimmatbaho kodni shunchaki taxmin qilishi mumkin.
Tadqiqotning boshlang'ich nuqtasi RockYou ma'lumotlar bazasidan 4 xonali parollar ketma-ketligi (1,7 million) va iPhone ekranini blokirovka qilish dasturidan 200 ming PIN kodlar ma'lumotlar bazasi (ma'lumotlar bazasi dastur ishlab chiqaruvchisi Daniel Amitay tomonidan taqdim etilgan) edi. . Ushbu ma'lumotlar asosida tuzilgan grafiklarda qiziqarli naqshlar paydo bo'ladi - sanalar, yillar, takroriy raqamlar va hatto 69 bilan tugaydigan PIN kodlar. Ushbu kuzatishlar asosida olimlar chiziqli regressiya modelini yaratdilar, u har bir PIN kodning mashhurligini 25 omilga qarab baholaydi. , masalan, kod DDMM sanasimi, ortib borayotgan ketma-ketlikmi va hokazo. Bu umumiy sharoitlar to'plamlarning har biridagi PIN-kodlarning 79% va 93% ga to'g'ri keladi.
Shunday qilib, foydalanuvchilar bir nechta oddiy omillarga asoslangan 4 xonali kodlarni tanlashadi. Agar bank PIN-kodlari shu tarzda tanlangan bo'lsa, ularning 8-9 foizini faqat uchta urinishda taxmin qilish mumkin edi! Lekin, albatta, odamlar bank kodlariga ko'proq e'tibor berishadi. Haqiqiy bank ma'lumotlarining katta to'plami yo'qligi sababli, tadqiqotchilar 1300 dan ortiq odamni so'roq qilishdi va haqiqiy PIN-kodlar allaqachon ko'rib chiqilganlardan qanchalik farq qilishini baholashdi. Tadqiqotning o'ziga xos xususiyatlarini hisobga olgan holda, respondentlardan kodlarning o'zi haqida so'ralmagan, faqat ularning yuqoridagi omillardan biriga (o'sish, DDMM formati va boshqalar) muvofiqligi haqida so'ralgan.
Ma'lum bo'lishicha, odamlar haqiqatan ham bank PIN kodlarini ancha ehtiyotkorlik bilan tanlaydilar. Respondentlarning chorak qismi bank tomonidan yaratilgan tasodifiy PIN-koddan foydalanadi. Uchdan bir qismidan ko‘pi eski telefon raqami, talaba ID raqami yoki tasodifiy ko‘rinadigan boshqa raqamlar to‘plamidan foydalanib, o‘z PIN-kodlarini tanlaydi. Natijalarga ko'ra, karta egalarining 64 foizi psevdo-tasodifiy PIN-koddan foydalanadi, bu bankdan tashqari kodlar bilan oldingi tajribalardagi 23-27 foizdan ancha yuqori. 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 kartasining PIN kodini taxmin qilish imkoniyati 2 foizdan kam bo‘ladi.
| Faktor | Misol | RockYou | iPhone | Tadqiqot |
|---|---|---|---|---|
| Sanalar | ||||
| DDMM | 2311 | 5.26 | 1.38 | 3.07 |
| DMGG | 3876 | 9.26 | 6.46 | 5.54 |
| MMDD | 1123 | 10.00 | 9.35 | 3.66 |
| MMYY | 0683 | 0.67 | 0.20 | 0.94 |
| YYYY | 1984 | 33.39 | 7.12 | 4.95 |
| Jami | 58.57 | 24.51 | 22.76 | |
| Klaviatura namunasi | ||||
| qo'shni | 6351 | 1.52 | 4.99 | - |
| kvadrat | 1425 | 0.01 | 0.58 | - |
| burchaklar | 9713 | 0.19 | 1.06 | - |
| kesib o'tish | 8246 | 0.17 | 0.88 | - |
| diagonal chiziq | 1590 | 0.10 | 1.36 | - |
| gorizontal chiziq | 5987 | 0.34 | 1.42 | - |
| so'z | 5683 | 0.70 | 8.39 | - |
| vertikal chiziq | 8520 | 0.06 | 4.28 | - |
| Jami | 3.09 | 22.97 | 8.96 | |
| Raqamli naqsh | ||||
| 69 bilan tugaydi | 6869 | 0.35 | 0.57 | - |
| faqat 0-3 raqamlari | 2000 | 3.49 | 2.72 | - |
| faqat 0-6 raqamlari | 5155 | 4.66 | 5.96 | - |
| takrorlanuvchi juftliklar | 2525 | 2.31 | 4.11 | - |
| bir xil raqamlar | 6666 | 0.40 | 6.67 | - |
| tushuvchi ketma-ketlik | 3210 | 0.13 | 0.29 | - |
| ortib borayotgan ketma-ketlik | 4567 | 3.83 | 4.52 | - |
| Jami | 15.16 | 24.85 | 4.60 | |
| Raqamlarni tasodifiy terish | 23.17 | 27.67 | 63.68 | |
Hammasi yaxshi bo'lar edi, lekin, afsuski, respondentlarning muhim qismi (23%) sana ko'rinishidagi PIN-kodni tanlaydi - va ularning deyarli uchdan bir qismi tug'ilgan sanasidan foydalanadi. Bu vaziyatni sezilarli darajada o'zgartiradi, chunki deyarli barcha (99%) respondentlar bank kartalari bilan hamyonida ushbu sana bosilgan turli xil identifikatsiya hujjatlarini saqlashlarini aytishdi. Agar tajovuzkor karta egasining tug'ilgan kunini bilsa, u holda vakolatli yondashuv bilan PIN-kodni taxmin qilish ehtimoli 9% gacha ko'tariladi.
100 ta eng mashhur PIN kodlar
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. Amalda, albatta, tajovuzkor uchun PIN-kodingizni taxmin qilishdan ko'ra uni josuslik qilish osonroq. Ammo siz hatto umidsiz bo'lib tuyulgan vaziyatda ham o'zingizni ko'zdan kechirishdan himoya qilishingiz mumkin:
Kombinatorika matematikaning bir boʻlimi boʻlib, berilgan obʼyektlardan maʼlum shartlarga rioya qilgan holda necha xil birikmalar yasash mumkinligi haqidagi savollarni oʻrganadi. Kombinatorika asoslari tasodifiy hodisalar ehtimolini baholash uchun juda muhimdir, chunki ular bizga fundamental mumkin bo'lgan sonni hisoblash imkonini beradi turli xil variantlar voqealarning rivojlanishi.
Kombinatorikaning asosiy formulasi
K element guruhi bo'lsin, va i-guruh n i elementdan iborat. Har bir guruhdan bitta elementni tanlaymiz. Keyin umumiy soni Bunday tanlovni amalga oshirishning N usuli N=n 1 *n 2 *n 3 *...*n k munosabati bilan aniqlanadi.
1-misol. Keling, ushbu qoidani oddiy misol bilan tushuntiramiz. Elementlarning ikkita guruhi bo'lsin va birinchi guruh n 1 ta elementdan, ikkinchisi esa n 2 ta elementdan iborat. Bu ikki guruhdan nechta turli juft elementlar yasash mumkinki, bu juftlik har bir guruhdan bitta elementni o‘z ichiga oladi? Aytaylik, biz birinchi guruhdan birinchi elementni oldik va uni o'zgartirmasdan, faqat ikkinchi guruh elementlarini o'zgartirib, barcha mumkin bo'lgan juftliklardan o'tdik. Bu element uchun n 2 ta shunday juft bo'lishi mumkin. Keyin biz birinchi guruhdan ikkinchi elementni olamiz va buning uchun barcha mumkin bo'lgan juftlarni ham qilamiz. Bundan tashqari, n 2 ta shunday juftlik bo'ladi. Birinchi guruhda faqat n 1 ta element mavjud bo'lganligi sababli, umumiy mumkin bo'lgan variantlar n 1 * n 2 bo'ladi.
2-misol. Raqamlarni takrorlash mumkin bo'lsa, 0, 1, 2, 3, 4, 5, 6 raqamlaridan nechta uch xonali juft sonlar yasalishi mumkin?
Yechim: n 1 =6 (chunki siz birinchi raqam sifatida 1, 2, 3, 4, 5, 6 dan istalgan raqamni olishingiz mumkin), n 2 =7 (chunki 0 dan istalgan raqamni ikkinchi raqam sifatida qabul qilishingiz mumkin , 1, 2 , 3, 4, 5, 6), n 3 =4 (chunki 0, 2, 4, 6 dan har qanday raqam uchinchi raqam sifatida olinishi mumkin).
Demak, 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 har bir tanlov bir xil guruhdan qilingan deb faraz qilishimiz mumkin va tanlangandan keyingi element guruhga qaytariladi. U holda barcha tanlash usullari soni n k ga teng. Kombinatorikada tanlashning bunday usuli deyiladi qaytariladigan namunalar.
3-misol. 1, 5, 6, 7, 8 raqamlaridan nechta to‘rt xonali son yasash mumkin?
Yechim. To'rt xonali sonning har bir raqami uchun beshta imkoniyat mavjud, ya'ni N=5*5*5*5=5 4 =625.
n ta elementdan iborat to'plamni ko'rib chiqaylik. Kombinatorikada bu to'plam deyiladi umumiy aholi.
n ta elementni joylashtirish soni m
Ta'rif 1. dan turar joy n tomonidan elementlar m kombinatorikada har qanday buyurtma qilingan to'plam dan m aholi orasidan tanlab olingan turli elementlar n elementlar.
4-misol.(1, 2, 1), (1, 3), (3, 1), (2, 3), (3) ikkitadan uchta elementning (1, 2, 3) turli xil joylashuvi bo'ladi. , 2). Joylashuvlar ham elementlar, ham ularning tartibida bir-biridan farq qilishi mumkin.
Kombinatorikadagi joylashtirishlar soni A n m bilan belgilanadi va quyidagi formula bilan hisoblanadi:
Izoh: n!=1*2*3*...*n (o‘qing: “en faktorial”), bundan tashqari, 0!=1 deb qabul qilinadi.
5-misol. O'nlik va birlik raqamlari aniq va toq bo'lgan nechta ikki xonali sonlar mavjud?
Yechim: chunki Agar beshta g'alati raqam, ya'ni 1, 3, 5, 7, 9 bo'lsa, unda bu vazifa besh xil raqamdan ikkitasini ikki xil pozitsiyada tanlash va joylashtirishga to'g'ri keladi, ya'ni. ko'rsatilgan raqamlar bo'ladi:
Ta'rif 2. Kombinatsiya dan n tomonidan elementlar m kombinatorikada har qanday tartibsiz to'plam dan m aholi orasidan tanlab olingan turli elementlar n elementlar.
6-misol. (1, 2, 3) to'plam uchun kombinatsiyalar (1, 2), (1, 3), (2, 3).
n ta elementdan iborat birikmalar soni, har biri m
Kombinatsiyalar soni C n m bilan belgilanadi va quyidagi formula bilan hisoblanadi:
7-misol. O'quvchi oltita kitobdan ikkitasini nechta usulda tanlashi mumkin?
Yechim: Usullar soni ikkitadan oltita kitobning kombinatsiyasi soniga teng, ya'ni. teng:
n ta elementning almashtirilishi
Ta'rif 3. Permutatsiya dan n elementlar har qanday deyiladi buyurtma qilingan to'plam bu elementlar.
Misol 7a. Uch elementdan (1, 2, 3) tashkil topgan to‘plamning barcha mumkin bo‘lgan almashtirishlari: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2).
n ta elementning turli almashtirishlar soni P n bilan belgilanadi va P n =n! formula bilan hisoblanadi.
8-misol. Turli mualliflarning yettita kitobini javonda bir qatorda nechta usulda joylashtirish mumkin?
Yechim: bu muammo ettita almashtirish soni haqida turli kitoblar. Kitoblarni tartibga solishning P 7 =7!=1*2*3*4*5*6*7=5040 usuli mavjud.
Munozara. Ko'ramizki, mumkin bo'lgan kombinatsiyalar sonini turli qoidalar (o'zgartirishlar, kombinatsiyalar, joylashtirishlar) bo'yicha hisoblash mumkin va natija boshqacha bo'ladi, chunki Hisoblash printsipi va formulalarning o'zi boshqacha. Ta'riflarni diqqat bilan ko'rib chiqsangiz, natija bir vaqtning o'zida bir nechta omillarga bog'liqligini sezasiz.
Birinchidan, qancha elementlardan biz ularning to'plamlarini birlashtira olamiz (elementlar umumiyligi qanchalik katta).
Ikkinchidan, natija bizga kerak bo'lgan elementlar to'plamining hajmiga bog'liq.
Nihoyat, to'plamdagi elementlarning tartibi biz uchun ahamiyatli yoki yo'qligini bilish muhimdir. Keling, quyidagi misol yordamida oxirgi omilni tushuntiramiz.
9-misol. Yoniq ota-onalar yig'ilishi 20 kishi hozir. Ota-onalar qo'mitasi tarkibiga 5 kishi kirishi kerak bo'lsa, uning tarkibi necha xil bo'lishi mumkin?
Yechim: Ushbu misolda bizni qo'mita ro'yxatidagi ismlarning tartibi qiziqtirmaydi. Agar natijada xuddi shu odamlar uning bir qismi bo'lib chiqsa, demak, biz uchun bu bir xil variant. Shuning uchun raqamni hisoblash uchun formuladan foydalanishimiz mumkin kombinatsiyalar 20 ta elementdan har biri 5 tadan.
Har bir qo'mita a'zosi dastlab ma'lum bir ish sohasi uchun javobgar bo'lsa, hamma narsa boshqacha bo'ladi. Keyin, qo'mitaning bir xil ro'yxat tarkibi bilan, ehtimol uning tarkibida 5 ta bo'lishi mumkin! variantlari almashtirishlar bu muhim. Turli xil variantlar soni (tarkibida ham, mas'uliyat sohasida ham) bu holda raqam bilan belgilanadi joylashtirishlar 20 ta elementdan har biri 5 tadan.
O'z-o'zini tekshirish vazifalari
1. Raqamlarni takrorlash mumkin bo'lsa, 0, 1, 2, 3, 4, 5, 6 raqamlaridan nechta uch xonali juft sonlar yasash mumkin?
Chunki Uchinchi o'rindagi juft son 0, 2, 4, 6 bo'lishi mumkin, ya'ni. to'rtta raqam. Ikkinchi o'rin ettita raqamdan har qanday bo'lishi mumkin. Birinchi o'rin noldan tashqari ettita raqamdan har qanday 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 sonlar bor?
Birinchi o'rin 0 dan tashqari har qanday raqam bo'lishi mumkin, ya'ni. 9 ta imkoniyat. Har qanday raqam ikkinchi o'rinda bo'lishi mumkin, ya'ni. 10 ta imkoniyat. Uchinchi o'rin ham har qanday raqam bo'lishi mumkin, ya'ni. 10 ta imkoniyat. To'rtinchi va beshinchi raqamlar oldindan belgilangan, ular birinchi va ikkinchisiga to'g'ri keladi, shuning uchun bunday raqamlar soni 9 * 10 * 10 = 900 ni tashkil qiladi.
3. Sinfda o'nta fan va kuniga beshta dars bor. Bir kun uchun jadvalni necha xil usulda tuzish mumkin?
4. Guruhda 20 kishi bo‘lsa, konferensiyaga 4 nafar delegat necha usulda saylanishi 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. Har bir konvertga bitta harf qo‘yilgan bo‘lsa, sakkiz xil harfni sakkiz xil konvertga necha xil usulda joylashtirish mumkin?
Birinchi konvertga sakkizta harfdan 1 tasini, ikkinchisiga qolgan yettitadan birini, uchinchisiga oltitadan birini va hokazolarni qoʻyishingiz mumkin. n = 8! = 1*2*3*4*5*6*7*8 = 40320.
6. Ikkita matematik va olti nafar iqtisodchidan iborat komissiya uch nafar matematik va o‘n nafar iqtisodchidan iborat bo‘lsin. Buni necha usulda qilish mumkin?
