Kombinator elementlari. Kombinatorika: asosiy qoidalar va formulalar 10 ta raqamning nechta kombinatsiyasi

uy Entsiklopediya
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!
"Qo'shimcha" almashtirishlar sonini hisoblash uchun, birinchi navbatda, 2 -jildning o'ng tomonidagi 1 -chi yonida nechta variant borligini aniqlang. Bunday almashtirishlarda 1 -jild birinchisidan 29 -chigacha, 2 -chi ikkinchisidan 30 -chigacha - bu juft kitoblar uchun atigi 29 o'rinni egallashi mumkin. Birinchi ikkita jildning har bir pozitsiyasi uchun qolgan 28 ta kitob o'zboshimchalik bilan qolgan 28 o'rinni egallashi mumkin. 28 ta kitobni qayta tartibga solish variantlari P 28= 28! Hammasi bo'lib, agar 2 -jild 1 -chining o'ng tomonida joylashgan bo'lsa, u 29 · 28 bo'lib chiqadi! = 29!.
Xuddi shunday, 2 -jild 1 -chi yonida, lekin uning chap tomonida joylashgan holatni ko'rib chiqing. Bir xil miqdordagi 29 · 28 variantlari chiqadi! = 29!.
Bu shuni anglatadiki, 2 · 29! "Ortiqcha" almashtirishlar bor! Va kerakli tartibga solish usullari 30! -2 · 29! Keling, bu qiymatni hisoblaylik.
o'ttiz! = 29! 30; 30! -2 · 29! = 29! (30−2) = 29! 28.
Shunday qilib, biz barcha natural sonlarni 1 dan 29 gacha ko'paytirishimiz va yana 28 ga ko'paytirishimiz kerak.
Javob: 2.4757335 10 32.

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.
Boshlang'ich voqea - bu kitoblarni javonlarga joylashtirish. Umumiy soni aniq hammasidan elementar hodisalar barcha mumkin bo'lgan almashtirishlarning umumiy soniga teng bo'ladi P 30=30!.
A hodisasi uchun qulay bo'lgan elementar hodisalar soni 1 va 2 -jildlar yonma -yon joylashtirilgan almashtirishlar soniga teng. Biz avvalgi muammoni hal qilib, bunday almashtirishlarni ko'rib chiqdik va 2 · 29 ni oldik! almashtirishlar.
Ehtimoliy qulay hodisalar sonini barcha mumkin bo'lgan oddiy hodisalar soniga bo'lish yo'li bilan aniqlanadi:
P (A) = 2 29! / 30! = 2 29!/(29! 30) = 2/30 = 1/15.
B hodisasi - bola emas 1 va 2 -jildlarni yonma -yon qo'ying - A hodisasiga qarama -qarshi, shuning uchun uning ehtimoli P (B) = 1 - P (A) = 1-1 / 15 = 14/15 = 0,9333
Javob: 0,9333.

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

A 30 15= 30 29 28 ... (30−15 + 1) = 30 29 28 ... 16 = 202843204931727360000.
Javob: 202843204931727360000.

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.
Tasavvur qilaylik, biz birinchi javonni oldingi vazifada bo'lgani kabi to'ldiramiz. Keyin 30 kitobdan 15gacha turar joy variantlari bo'ladi A 30 15= 30 29 28 ... (30−15 + 1) = 30 29 28 ... 16.

Va har safar kitoblarni birinchi javonga qo'yganimizda, biz hali ham P 15= 15! kitoblarni ikkinchi tokchaga joylashtirishning usullari. Axir, ikkinchi javon uchun bizda 15 ta joy qolgan 15 ta kitob bor, ya'ni. faqat almashtirish mumkin.
Umumiy yo'llar bo'ladi A 30 15 P 15, bu holda, 30 dan 16 gacha bo'lgan barcha sonlarning hosilasi hali ham 1 dan 15 gacha bo'lgan barcha sonlarning ko'paytmasiga ko'paytirilishi kerak bo'ladi, siz 1 dan 30 gacha bo'lgan barcha natural sonlarning mahsulotini olasiz, ya'ni. o'ttiz!
II usul.
Endi tasavvur qilaylik, bizda 30 o'rinli bitta uzun javon bor edi. Biz unga 30 ta kitobni joylashtirdik, so'ngra muammoning shartini qondirish uchun tokchani ikkita teng qismga kesib oldik. Qancha joylashtirish variantlari bo'lishi mumkin? 30 ta kitobdan iloji boricha ko'p o'zgartirishlar, ya'ni. P 30 = 30!
Javob: 30!.
Matematik muammoni qanday hal qilish muhim emas. Siz buni hayotiy vaziyatda o'z harakatlaringizni tasavvur qilganingizdek hal qilasiz. Baribir to'g'ri javob olish uchun mantiqdan chetga chiqmaslik muhim.

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.)
Shunday qilib, qulay elementar hodisalar soni 6 ga teng.
Mumkin bo'lgan elementar hodisalarning umumiy soni 6 dan 3 gacha bo'lgan joylashtirishlar soniga teng, ya'ni. A 6 3 = 6 ... (6−3 + 1) = 6 5 4 = 120.
P (A) = 6/120 = 1/20 = 0,05.
Javob: 0,05.

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

BILAN 30 15 = 30! /(30 − 15)!/15! = 155117520.
Javob: 155117520.

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.
Mumkin bo'lgan elementar hodisalarning umumiy soni guruhdagi elementlarning tartibini hisobga olmagan holda tuzilgan 6 dan 3 gacha bo'lgan guruhlar soniga teng, ya'ni. kombinatsiyalar soniga teng S 6 3= 6! / 3! / (6 - 3)! = 4 5 6 / (1 2 3) = 4 5 = 20.
P (A) = 1/20 = 0,05.
Javob: 0,05.

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: