Ularning aytishicha, kombinatorika va ehtimollar nazariyasi elementlarini yaratishning asosiy sharti odamlarning lotereya, zar, karta va boshqa tasodifiy oʻyinlarga qaramligi edi. Antik davrda qimor o'yinlari katta ahamiyatga ega bo'lgan. Ba'zilar boylik, yerlar, xotinlar qo'lga kiritdilar. Boshqalar esa oxirgi ko'ylakgacha bor narsalarini yo'qotdilar. Haqiqatan ham, xavf o'yinlari yoki tasodifiy o'yinlarning ta'siri sodir bo'ldi. Biroq, fanning jadal rivojlanishini o'z ichiga olgan ko'proq fundamental sabablar bor edi: eksperimentlar, bir qator eksperimentlar jarayonini bashorat qilish va natijalardagi xatoni baholash zarurati. Bularning barchasi va yana ko'p narsalar kombinatorika va ehtimollar nazariyasi elementlarining paydo bo'lishiga olib keldi.
Bernulli teoremasi
Kombinatorika 17-asrda Kardano, Paskal, Galiley, Ferma, Leybnits, Bernulli kabi olimlarning mehnatlari tufayli paydo boʻlgan deb ishoniladi. Aynan ular maxsus atamalarni kiritdilarbu fan uchun va bir qator fundamental qonunlar va kombinatorikaning birinchi formulalarini isbotladi. Misol uchun, Bernulli teoremasi, unda faqat bir-biridan mustaqil bo'lgan va bir xil sharoitlarda har qanday marta takrorlanishi mumkin bo'lgan tasodifiy tajribalar va tajribalarni ko'rib chiqishga arziydi. Bu teorema kombinatorika va ehtimollar nazariyasining fan sifatida keyingi rivojlanishini belgilab bergani umumiy qabul qilingan.
Chastotalar barqarorligi
Kombinatorika elementlarini oʻrganishga oʻtishdan oldin, keling, baʼzi fikrlarni bildiruvchi aniq bir misol keltiraylik – zar otish. Oddiylik uchun bitta suyakni ko'rib chiqaylik. Bu olti qirrali kub bo'lib, uning har bir tomoni raqamlangan. Agar biz n ta otishni o'rganish bo'yicha bir qator tajribalar o'tkazsak va G1 1-raqamli chekka tomchilar soni deb faraz qilsak, G2 - 2 raqami va boshqalar bilan, ma'lum bo'lishicha, uloqtirishlar sonining ortishi bilan n, chastota G1/n, G2 /n, …, G 6/n, ular tajriba boshida tasodifiy bo’lib ko’rinadi, ular juda aniq qiymatlarni oladi. Muvozanatli zar uchun esa har bir faset chastotasi katta aniqlik bilan teng bo‘ladi.
Yana bir misol - tangalar tajribasi. Shunday qilib, olim Pirson 24 000 ta tanga otishdan so'ng, tanganing bir tomondan tushish chastotasi 0,5 ga yaqinlashsa, qanchalik aniq bo'lsa, shuncha ko'p otish amalga oshiriladi, degan xulosaga keldi. Shunday qilib, u gerbning yo'qolishi uchun 0,5005 ehtimolini oldi. Bu tamoyilchastota barqarorligi ham nazariyaning asoslaridan biridir.
Tarixiy eslatma
Ehtimollar nazariyasi va kombinatorika 20-asrda eng faol ishlab chiqilgan. Va bu masalaga rus va sovet matematiklari katta hissa qo'shdilar. Ular orasida, masalan, Kolmogorov, Chebyshev, Lyapunov, Markov. Ular qo'llash sohalarini sezilarli darajada kengaytirdilar, katta sonlar qonunini, markaziy chegara teoremasini va ehtimollar nazariyasi aksiomatikasini o'rgandilar va tavsifladilar. Bularning barchasi butun bir fan uchun asos bo'ldi. Bugungi kunda fizika, kimyo, biologiya va boshqa ko'plab sohalarda, ayniqsa ularning amaliy sohasida, kombinatorika va ehtimollar nazariyasi elementlarining ahamiyatini ortiqcha baholash qiyin.
Kombinatorika masalalariga misollar
Kombinatorika - bu ma'lum shartlarga rioya qilgan holda har qanday elementlar to'plamidan tashkil topgan mumkin bo'lgan kombinatsiyalar sonini baholash. Buning uchun kombinatorikada kerakli masalani qulay va tez yechish imkonini beruvchi formulalar olingan. Ammo bu formulalarni ko‘rsatishdan oldin, keling, ularga sabab bo‘lgan savollarga misollarni ko‘rib chiqaylik.
1-topshiriq. Jahon chempionatining pley-off bosqichida 16 ta jamoa ishtirok etadi. Ular o'zaro joylarni necha xil usulda taqsimlashlari mumkin? Masalan:
- (3, 1, 2, 4..16) - 3-raqamli jamoa birinchi oʻrinda, 1-jamoa ikkinchi oʻrinda va hokazo.
- (16, 1, 2, 3, 4..15) - 16-raqamli jamoa birinchi oʻrinda, …
- (1..7, 9, 8, 10..16) - jamoaning birinchi oʻrinlarida 1, 2, 3, …
Bularning barchasi variantlarga misollar. Bu muammoning aniq yechimi hammasini yozish bo'ladimumkin bo'lgan kombinatsiyalar. Biroq, bu juda ko'p vaqtni oladi, chunki ularning soni bir xil bo'ladi, chunki joylarda 16 ta raqamni qayta joylashtirish usullari mavjud. Kombinatorika elementlari shu kabi misollarni bir zumda hal qiladi.
Muammo 2. Ushbu 16 ta jamoadan faqat uchtasi sovrin olishi mumkin. G'oliblar necha usulda aniqlanadi? Bunda vazifa avvalgisidan farq qiladi, chunki turnir jadvalining qanday ko'rinishi va finalchilarning tartibi qanday bo'lishi umuman muhim emas. Darhaqiqat, barcha jamoalar orasida sovrinlar uchun kurashadigan faqat uchtasini topish muhim. Ya'ni, to'plamlar {3, 2, 1}, {5, 12, 7}, {8, 1, 2} va hokazo kabi ko'rinishi mumkin.
3-muammo. Savolni biroz boshqacha qo'ysak nima bo'ladi: pley-offda ishtirok etuvchi 16 ta jamoaga medallarni taqsimlashning nechta usuli bor? Ikkinchi vazifa bilan farq butunlay aniq bo'lmasligi mumkin. Biroq, endi biz nafaqat sovrinli o'rinlar uchun kurashadigan uchta jamoani tanlashimiz, balki ulardan qaysi biri qaysi o'rinni egallashini aniqlashimiz kerak. Boshqacha qilib aytganda, agar ikkinchi vazifa uchun, masalan, to'plamlar (5, 12, 1) va (1, 12, 5) ekvivalent bo'lgan bo'lsa, endi buyruqlar tartibi vaznga ega. Darhaqiqat, birinchi holatda 5-raqamli jamoa oltin medalni oladi, ikkinchi holatda esa 1-raqamli jamoa.
Quyida biz har bir vazifa kombinatorikaning qaysi boʻlimlariga tegishli ekanligini koʻrib chiqamiz va ularni qanday hal qilishni batafsil bayon qilamiz. Ayni paytda siz berilgan savollar haqida oʻzingiz oʻylab koʻrishingiz mumkin.
Buyurtmadan qat'iy nazar kombinatsiyalar yoki kombinatsiyalar
Faqat n-qism elementlarning kombinatsiyasik 1 dan n gacha qiymatlarni qabul qilishi mumkin bo'lgan k-bo'lak elementlar to'plami - n ta elementdan tanlangan k elementning har qanday birikmasi. Bu holda, agar ulardan birida n dan istalgan element bo'lsa, lekin ikkinchisiga tegishli bo'lmasa, ikkita to'plam boshqacha hisoblanadi. Boshqacha aytganda, ular faqat tarkibida farqlanadi. Kombinatorika elementlarida kombinatsiyalar kirish asosi hisoblanadi.
N dan k gacha boʻlgan birikmalar soni C k bilan belgilanadi, inglizcha Combination soʻzidan olingan. C 1=n va C =1 bayonotlari juda mos Ya'ni, bir vaqtning o'zida n ta elementdan birini tanlash uchun atigi n ta variant mavjud (elementlarning o'zi bilan bir xil son) va shunga mos ravishda siz n ta element miqdorida n ta element to'plamini yaratishingiz mumkin, faqat bitta.
Demak, masalan, {e, 2, a} uchta elementdan iborat toʻplamni koʻrib chiqaylik. Uning uchun C31=3: {a}, {2}, {e}; C32=3: {e, 2}, {2, a}, {a, e}; va nihoyat C33=1: {e, 2, a}. Eslatib o'tamiz, bu holda to'plamdagi elementlarning tartibi muhim emas.
C 0 nima ekanligini aniqlashga harakat qilsangiz nima bo'ladi?
Buyurtma asosida joylashtirish yoki kombinatsiya
Joylashtirish kombinatorikasini tushunish juda oson. Bu bir xil kombinatsiyalar, faqat hozir nafaqat kompozitsiya, balki har bir kombinatsiyadagi tartib ham hisobga olinadi. Shunday qilib, n ta elementni k bo'lakdan iborat kombinatsiyalarga (to'plamlarga) joylashtirish orqali, bu erda k 1 dan n gacha qiymatlarni qabul qilishi mumkin,n dan elementlarning ma'lum bir tartibda joylashtirilgan k-bo'laklaridan tashkil topgan har qanday birikma deyiladi. Boshqacha qilib aytganda, ikkita joylashtirish kombinatsiyasi uchta holatda farqlanadi:
- tarkibida farqlanadi;
- toʻplamlardagi elementlar tartibida farqlanadi;
- ular tarkibida ham, tartibida ham farqlanadi.
N dan k gacha boʻlgan joylashtirishlar soni Arrangements dan A k bilan belgilanadi. Uch elementli {x, e, z} toʻplami uchun barcha joylashtirish variantlarini koʻrib chiqing:
- A31=3: (x), (e), (z);
- A32=6: (x, e), (e, x), (x, z), (z, x), (e, z), (z, e);
- A33=6: (x, e, z), (e, x, z), (z, x, e), (x, z, e), (e, z, x), (z, e, x).
Oxirgi qator A33 alohida e'tiborga loyiq. Bular almashtirishdan boshqa narsa emas.
Oʻzgartirishlar
Yuqorida aytib o'tilganidek, almashtirishlar ma'no jihatidan juda oddiy. Bu oddiygina har biri n ta elementdan iborat n ta elementning joylashuvi. Ya'ni, biz elementlarning tartibida va faqat ularda farq qiladigan barcha kombinatsiyalarga qiziqamiz. Yoki ekvivalenti A . O'zgartirishlar soni Permutation so'zidan P harfi bilan belgilanadi. Kombinatorika elementlarida almashtirishlar faqat bitta indeks bilan ta'minlanadi. Masalan, oldingi bobda bilib olganimizdek, P3=6.
Toʻplamlar nazariyasi orqali kombinatsiyalar
Ma'lumki, matematikada noaniq ob'ektlar bilan bog'lanish qiyin: to'plam, kombinatsiya va hokazo. Yaxshi bo'lardi.nima bilan shug'ullanayotganimizni matematik jihatdan aniq belgilang. Bu erda to'plamlar nazariyasi tili yordam beradi. Keling, to'plamlar nazariyasi tilida kombinatorikaning elementlari nima ekanligini aniqlaymiz.
Ba'zi n-to'plamlar berilgan bo'lsin A={a1, a2, …, a }, u n ta elementdan iborat. N-to'plamdan uning k-kichik to'plamini aniqlash oson, bu erda k n dan kichik yoki teng. Keyin n dan k gacha bo'lgan birikmalar n to'plamning barcha k to'plamlari deb ataladi. Ushbu ta'rif tufayli C 0 yozuvi qanday ko'rinishi haqidagi savolga javob berish oson. To'plam nazariyasida bo'sh to'plam har qanday kichik to'plamda bo'lganligi sababli, u holda C 0=1. Boshqacha qilib aytganda, u bittadan iborat kombinatsiya bo'ladi. element - boʻsh toʻplam.
Shunday qilib, uchta elementdan iborat {c, b, a} toʻplamini oʻrganib chiqsak, C 0 =1: { }; C31=3: {a}, {b}, {c}; C32=3: {a, b}, {b, c}, {c, a}; va nihoyat C33=1: {a, b, c}.
Shunga ko'ra, ular joylashtirish kombinatorikasida ham xuddi shunday aniqlanadi. Yagona farq shundaki, siz n-to'plamdan buyurtma qilingan k-kichik to'plamlarni tanlashingiz kerak. Va barcha kichik to'plamlar bo'sh to'plamni ham o'z ichiga oladi. U shartli ravishda 0 donadan iborat n ta elementning tartiblangan kombinatsiyasi hisoblanadi, ya'ni. A 0=1.
Noaniq konstruksiyalardan toʻplamlar nazariyasida aniq belgilangan obʼyektlarga oʻtganligi sababli, savollardan biriga javob berish unchalik ahamiyatsiz boʻlib chiqdi.yuzaga kelgan savollar. Hammasi matematika.
Qo'shish printsipi
Bu kombinatorikaning ikkita asosiy qoidalaridan biridir. Moskva shahrida A nuqtadan B nuqtasiga 5 ta avtobus, 3 ta tramvay va 1 ta metro poyezdi orqali borish mumkin. Ma'lum bo'lishicha, to'g'ri joyga borishning 5 + 3 + 1=9 yo'li bor. Bu qo'shishning kombinatsion printsipi.
Agar muammoni koʻrib chiqishda uni n ta usulda yechish mumkin boʻlsa, bu usullarning birinchisi m1 marta qoʻllanilishi mumkin boʻlsa, ikkinchisi - m 2marta va hokazo, keyin bu muammo hal qilinadi m1 + m2 + … + musul.
Ko'paytirish printsipi
Endi tasavvur qilaylik, siz Moskvadan Qozonga Nijniy Novgorod orqali borishingiz kerak. Shu bilan birga, Moskva va Nijniy Novgorodni 2 ta poyezd, 3 ta reys va 10 ta avtomashina, Nijniy Novgorod va Qozonni esa 1 ta poyezd, 1 ta reys va 2 ta avtobus bog‘laydi. Qo'shish tamoyiliga ko'ra, biz Moskvadan Nijniy Novgorodga va u erdan Qozonga borishning 13 yo'li bor degan xulosaga kelamiz - 4. Moskva va Qozonni bog'laydigan yo'llarning umumiy soni: 134=52 bo'ladi..
Shunday qilib, ko'paytirishning kombinatorlik printsipi quyidagicha o'qiladi. Agar muammo ketma-ket n ta bosqichda hal qilinsa, birinchi bosqichda m1, ikkinchi bosqichda m2 va hokazo., Bu holda, bu ketma-ket bosqichlar mustaqildir, ya'ni oldingi bosqichlarda qanday qaror qabul qilinganiga qarab yo'llar soni o'zgarmaydi, keyin muammo hal qilinadi m1 m2 …m yo'llari. Agar qadamlarda kamida bitta farq boʻlsa, ikkita yechim boshqacha hisoblanadi.
Asosiy formulalar
Keling, formulalarni darhol koʻrsatamiz, soʻng ular qayerdan kelganini qisqacha tasvirlab beramiz va kombinatorikaning ushbu elementlaridan foydalangan holda yuqorida tasvirlangan misollarni hal qilamiz.
Turar joy. Bu formuladan boshlaymiz, chunki boshqalar undan olingan
| A k= | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1)= | n! |
| (n-k)! |
Oʻzgartirishlar
| P= | A = | n(n-1)(n-2)(n-3)(n-4)(n-5)…4321= | n! |
Kombinatsiyalar
| C k= | A k | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1) | n! |
| k! | k! | k!(n-k)! |
Bu formulalarning isboti kombinatorika elementlari tamoyillari - qoʻshish va koʻpaytirish qoidalariga asoslanadi. Joylashuvlar sonini topish uchun birinchi formulani ko'rib chiqing. Birinchi bosqichda biz n ta elementdan birini olamiz va buni amalga oshirishning n ta usuli bor. Ikkinchi bosqichda bizda n-1 elementlar va shunga mos ravishda n-1 tanlovlari qoladi. Uchinchidan - n-3 yo'l. To'plamimizda k element bo'lguncha buni davom ettiramiz. Ko'paytirish qoidasiga ko'ra, biz jami n (n-1) (n-2) (n-3) (n-4) (n-5) … (n-k + 1) mavjudligiga kelamiz.) k elementni tanlash usullari. O'zgartirishlarni topishning ikkinchi formulasi birinchisining oddiy natijasidir.almashtirishlar soni m=k. Kombinatsiyalar sonini beruvchi oxirgi formula n ta elementning birikmalarini qidirishda har safar k dona ko'rishga kelganimizda k! n dan k gacha bo'lgan tartiblar (ular k elementning almashinishi sifatida olinadi). Shuning uchun bizda A k=C kk!.
Endi biz avval e'lon qilingan vazifalarga qaytishimiz va variantlar sonini baholashimiz mumkin. Birinchi muammo uchun biz almashtirish formulasidan foydalanishimiz kerak, ya'ni P16=16!=20 922 789 888 000 ≈ 211012 16 ta jamoani turnir jadvalida qanday joylashtirish mumkin boʻlgan variantlar. Ikkinchi muammo kombinatsiyalarga tegishli, ya'ni C163=16! / [3!(16-3)!]=560 g'olib. Nihoyat, oxirgi muammo joylashtirish bilan bog'liq, ya'ni A163=16! / (16-3)!=16 ta jamoadan 3 tasi sovrinlarni baham koʻrishi mumkin boʻlgan 3360 ta usul.
Yuqoridagilarni hisobga olib, katta sonlar kombinatorikalari qanday ishlashi haqida gapirish ortiqcha.
