Ushbu maqolada asosiy e'tibor matematikaning kombinatorika deb ataladigan maxsus bo'limiga qaratiladi. Formulalar, qoidalar, muammoni hal qilish misollari - bularning barchasini maqolani oxirigacha o'qish orqali topishingiz mumkin.
Xo'sh, bu bo'lim nima? Kombinatorika har qanday ob'ektlarni hisoblash masalasi bilan shug'ullanadi. Ammo bu holda ob'ektlar olxo'ri, nok yoki olma emas, balki boshqa narsadir. Kombinatorika bizga hodisa ehtimolini topishga yordam beradi. Masalan, karta o'ynaganda, raqibning ko'zi bo'lish ehtimoli qanday? Yoki bunday misol - yigirmata to'pdan iborat sumkadan aniq oq rangga ega bo'lish ehtimoli qanday? Aynan shu turdagi vazifalar uchun biz hech bo'lmaganda matematikaning ushbu bo'limining asoslarini bilishimiz kerak.
Kombinatorli konfiguratsiyalar
Kombinatorikaning asosiy tushunchalari va formulalari masalasini ko'rib chiqsak, kombinatorik konfiguratsiyalarga e'tibor bermay bo'lmaydi. Ular faqat formulalash uchun emas, balki turli kombinatsion masalalarni yechish uchun ham qo'llaniladi. Bunday modellarga misollar:
- joylashtirish;
- oʻzgartirish;
- kombinatsiya;
- raqam tarkibi;
- ajratilgan raqam.
Birinchi uchtasi haqida keyinroq batafsil toʻxtalib oʻtamiz, ammo bu boʻlimda kompozitsiya va boʻlinishlarga eʼtibor qaratamiz. Ular ma'lum bir sonning (aytaylik, a) tarkibi haqida gapirganda, ular a sonining ba'zi ijobiy sonlarning tartibli yig'indisi sifatida ifodalanishini anglatadi. Bo‘linish esa tartibsiz yig‘indidir.
Boʻlimlar
Toʻgʻridan-toʻgʻri kombinatorika formulalari va masalalarni koʻrib chiqishga oʻtishdan oldin, matematikaning boshqa boʻlimlari kabi kombinatorikaning ham oʻziga xos boʻlimlari borligiga eʼtibor qaratish lozim. Bunga quyidagilar kiradi:
- numerativ;
- strukturaviy;
- ekstremal;
- Ramsi nazariyasi;
- ehtimolli;
- topologik;
- cheksiz.
Birinchi holatda, biz sanab chiquvchi kombinatorika haqida gapiramiz, muammolar to'plam elementlari tomonidan tuzilgan turli xil konfiguratsiyalarni sanab o'tish yoki hisoblashni ko'rib chiqadi. Qoida tariqasida, ushbu to'plamlarga ba'zi cheklovlar qo'yiladi (ajralish, farqlanmaslik, takrorlash imkoniyati va boshqalar). Va bu konfiguratsiyalar soni qo'shish yoki ko'paytirish qoidasi yordamida hisoblab chiqiladi, biz biroz keyinroq gaplashamiz. Strukturaviy kombinatorikaga grafiklar va matroidlar nazariyalari kiradi. Ekstremal kombinatorika masalasiga misol sifatida quyidagi xossalarni qanoatlantiradigan grafikning eng katta o'lchami nima bo'lishi mumkin… To'rtinchi xatboshida biz tasodifiy konfiguratsiyalarda muntazam tuzilmalar mavjudligini o'rganuvchi Ramsey nazariyasini eslatib o'tdik. EhtimoliyKombinatorika savolga javob berishga qodir - berilgan to'plamning ma'lum bir xususiyatga ega bo'lish ehtimoli qanday. Siz taxmin qilganingizdek, topologik kombinatorika topologiyada usullarni qo'llaydi. Va nihoyat, ettinchi nuqta - cheksiz kombinatorika kombinatorika usullarini cheksiz to'plamlarga qo'llashni o'rganadi.
Qoʻshish qoidasi
Kombinatorika formulalari orasida bizga anchadan beri tanish bo'lgan juda oddiylarini topish mumkin. Masalan, yig'indisi qoidasi. Bizga ikkita harakat (C va E) berilgan deylik, agar ular bir-birini istisno qilsa, C harakat bir necha usulda (masalan, a) va E harakat b-shaklda bajarilishi mumkin, u holda ulardan istalgani (C) yoki E) a + b usulida bajarilishi mumkin.
Nazariy jihatdan buni tushunish juda qiyin, biz oddiy misol bilan butun fikrni etkazishga harakat qilamiz. Keling, bitta sinfdagi o'quvchilarning o'rtacha sonini olaylik - yigirma beshtani tashkil qilaylik. Ular orasida o‘n besh qiz, o‘n nafar o‘g‘il bor. Sinfga har kuni bitta xizmatchi ajratiladi. Bugungi kunda sinf navbatchisini tayinlashning nechta usuli bor? Muammoni hal qilish juda oddiy, biz qo'shimcha qoidaga murojaat qilamiz. Vazifa matnida faqat o'g'il bolalar yoki faqat qizlar navbatchilik qilishi mumkinligi aytilmagan. Shuning uchun, bu o'n besh qiz yoki o'n o'g'ilning har biri bo'lishi mumkin. Yig'indi qoidasini qo'llagan holda, biz boshlang'ich sinf o'quvchisi osonlikcha engishi mumkin bo'lgan juda oddiy misolni olamiz: 15 + 10. Hisoblab chiqqach, biz javob olamiz: yigirma besh. Ya'ni, faqat yigirma beshta yo'l borbugunga navbatchilik sinfini tayinlang.
Ko'paytirish qoidasi
Ko'paytirish qoidasi ham kombinatorikaning asosiy formulalariga tegishli. Keling, nazariyadan boshlaylik. Faraz qilaylik, bir necha amalni bajarishimiz kerak (a): birinchi harakat 1 usulda, ikkinchisi 2 usulda, uchinchisi 3 usulda va shunga o'xshash oxirgi a-harakat sa usullarda bajarilguncha davom etadi. Keyin bu barcha harakatlar (bizda jami bor) N ta usulda bajarilishi mumkin. Noma'lum N ni qanday hisoblash mumkin? Bu bizga formula yordam beradi: N \u003d c1c2c3…ca.
Yana, nazariy jihatdan hech narsa aniq emas, keling, koʻpaytirish qoidasini qoʻllashning oddiy misoliga oʻtamiz. Keling, yigirma besh kishilik bir sinfni olaylik, unda o'n besh qiz va o'n nafar o'g'il o'qiydi. Faqat bu safar biz ikkita xizmatchi tanlashimiz kerak. Ular faqat o'g'il yoki qiz yoki qiz bolali bola bo'lishi mumkin. Muammoning elementar yechimiga murojaat qilamiz. Biz birinchi xizmatchini tanlaymiz, oxirgi xatboshida qaror qilganimizdek, biz yigirma beshta mumkin bo'lgan variantni olamiz. Navbatchi ikkinchi shaxs qolgan har qanday kishi bo'lishi mumkin. Bizda yigirma besh talaba bor edi, biz bittasini tanladik, demak, qolgan yigirma to‘rt kishidan istalgani ikkinchi navbatchi bo‘lishi mumkin. Nihoyat, biz ko'paytirish qoidasini qo'llaymiz va ikkita xizmatchi olti yuzta usulda tanlanishi mumkinligini topamiz. Biz bu raqamni yigirma besh va yigirma to‘rtni ko‘paytirish orqali oldik.
Almashtirish
Endi yana bitta kombinatorik formulani ko'rib chiqamiz. Maqolaning ushbu qismida bizKeling, almashtirishlar haqida gapiraylik. Muammoni darhol misol bilan ko'rib chiqing. Keling, bilyard to'plarini olaylik, bizda ularning n-soni bor. Hisoblashimiz kerak: ularni ketma-ket joylashtirish, ya'ni buyurtma qilingan to'plamni yaratish uchun nechta variant bor.
Boshlaylik, agar bizda to'plar bo'lmasa, bizda joylashtirish variantlari ham nolga teng. Va agar bizda bitta to'p bo'lsa, unda tartib ham bir xil bo'ladi (matematik jihatdan buni quyidagicha yozish mumkin: R1=1). Ikki sharni ikki xil usulda joylashtirish mumkin: 1, 2 va 2, 1. Demak, R2=2. Uchta sharni oltita usulda (R3=6) joylashtirish mumkin: 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Va agar bunday to'plar uchta emas, balki o'n yoki o'n besh bo'lsa? Barcha mumkin bo'lgan variantlarni sanab o'tish juda uzoq, keyin kombinatorika yordamimizga keladi. O'zgartirish formulasi bizning savolimizga javob topishga yordam beradi. Pn=nP(n-1). Agar formulani soddalashtirishga harakat qilsak, biz olamiz: Pn=n (n - 1) … 21. Va bu birinchi natural sonlarning mahsulotidir. Bunday son faktorial deyiladi va n sifatida belgilanadi!
Muammoni ko'rib chiqaylik. Rahbar har kuni ertalab o'z otryadini bir qatorga (yigirma kishi) quradi. Otryadda uchta eng yaxshi do'st bor - Kostya, Sasha va Lesha. Ularning yonma-yon bo'lish ehtimoli qanday? Savolga javob topish uchun siz "yaxshi" natija ehtimolini natijalarning umumiy soniga bo'lishingiz kerak. O'zgartirishlarning umumiy soni 20 ta!=2,5 kvintillion. "Yaxshi" natijalar sonini qanday hisoblash mumkin? Aytaylik, Kostya, Sasha va Lesha bitta supermen. Keyin bizBizda faqat o'n sakkizta fan bor. Bu holda almashtirishlar soni 18=6,5 kvadrillion. Bularning barchasi bilan Kostya, Sasha va Lesha o'zlarining bo'linmas uchliklarida o'zboshimchalik bilan harakat qilishlari mumkin va bu yana 3 ta!=6 ta variant. Shunday qilib, bizda jami 18 ta "yaxshi" yulduz turkumi bor!3! Biz faqat kerakli ehtimollikni topishimiz kerak: (18!3!) / 20! Bu taxminan 0,016. Agar foizga aylantirilsa, u atigi 1,6% bo'ladi.
Turar joy
Endi biz yana bir juda muhim va zarur kombinatorika formulasini ko'rib chiqamiz. Turar joy bizning navbatdagi masalamiz bo'lib, uni maqolaning ushbu qismida ko'rib chiqishingizni tavsiya qilamiz. Biz yanada murakkablashamiz. Faraz qilaylik, biz mumkin bo'lgan almashtirishlarni faqat butun to'plamdan (n) emas, balki kichikroq (m) dan ko'rib chiqmoqchimiz. Ya'ni, biz n ta elementning m ga almashtirilishini ko'rib chiqamiz.
Kombinatorikaning asosiy formulalarini shunchaki yodlash emas, balki tushunish kerak. Hatto ular murakkablashayotganiga qaramay, bizda bitta emas, ikkita parametr bor. Aytaylik, m \u003d 1, keyin A \u003d 1, m \u003d 2, keyin A \u003d n(n - 1). Agar biz formulani yanada soddalashtirsak va faktoriallar yordamida yozuvga o'tsak, biz juda qisqa formulaga ega bo'lamiz: A \u003d n! / (n - m)!
Kombinatsiya
Biz kombinatorikaning deyarli barcha asosiy formulalarini misollar bilan koʻrib chiqdik. Keling, kombinatorikaning asosiy kursini ko'rib chiqishning yakuniy bosqichiga o'tamiz - kombinatsiya bilan tanishish. Endi biz mavjud bo'lgan n dan m ta elementni tanlaymiz, shu bilan birga ularning barchasini barcha mumkin bo'lgan usullar bilan tanlaymiz. Xo'sh, bu turar joydan qanday farq qiladi? Biz qilmaymiztartibni ko'rib chiqing. Bu tartibsiz toʻplam kombinatsiya boʻladi.
Darhol belgini kiriting: C. Biz n tadan m ta sharni joylashtiramiz. Biz buyurtmaga e'tibor berishni to'xtatamiz va takroriy kombinatsiyalarni olamiz. Kombinatsiyalar sonini olish uchun biz joylashtirishlar sonini m ga bo'lishimiz kerak! (m faktorial). Ya'ni, C \u003d A / m! Shunday qilib, n ta to'pni tanlashning bir necha yo'li mavjud, ular deyarli hamma narsani tanlash uchun qanchaga teng. Buning mantiqiy ifodasi bor: ozgina tanlash deyarli hamma narsani tashlash bilan bir xil. Shu o‘rinda shuni ham ta’kidlash kerakki, elementlarning yarmini tanlashda maksimal kombinatsiyalar soniga erishish mumkin.
Muammo yechish uchun formulani qanday tanlash mumkin?
Biz kombinatorikaning asosiy formulalarini batafsil ko'rib chiqdik: joylashtirish, almashtirish va kombinatsiya. Endi bizning vazifamiz kombinatorikadagi masalani yechish uchun kerakli formulani tanlashni osonlashtirishdir. Siz quyidagi juda oddiy sxemadan foydalanishingiz mumkin:
- Oʻzingizdan soʻrang: muammo matnida elementlarning tartibi hisobga olinganmi?
- Agar javob yoʻq boʻlsa, kombinatsiya formulasidan foydalaning (C=n! / (m!(n - m)!)).
- Agar javob yoʻq boʻlsa, siz yana bitta savolga javob berishingiz kerak: barcha elementlar kombinatsiyaga kiritilganmi?
- Agar javob ha boʻlsa, almashtirish formulasidan foydalaning (P=n!).
- Agar javob yoʻq boʻlsa, ajratish formulasidan foydalaning (A=n! / (n - m)!).
Misol
Biz kombinatorika elementlari, formulalar va boshqa ba'zi masalalarni ko'rib chiqdik. Endi o'tamizhaqiqiy muammoni hisobga olgan holda. Tasavvur qiling-a, oldingizda kivi, apelsin va banan bor.
Birinchi savol: ularni nechta usulda qayta tartibga solish mumkin? Buning uchun biz almashtirish formulasidan foydalanamiz: P=3!=6 ta usul.
Ikkinchi savol: bitta mevani nechta usulda tanlash mumkin? Bu aniq, bizda faqat uchta variant bor - kivi, apelsin yoki bananni tanlang, lekin biz kombinatsiya formulasini qo'llaymiz: C \u003d 3! / (2!1!)=3.
Uchinchi savol: ikkita mevani nechta usulda tanlash mumkin? Bizda qanday variantlar bor? kivi va apelsin; kivi va banan; apelsin va banan. Ya'ni, uchta variant, lekin buni kombinatsiya formulasi yordamida tekshirish oson: C \u003d 3! / (1!2!)=3
To'rtinchi savol: uchta mevani nechta usulda tanlash mumkin? Ko'rib turganingizdek, uchta mevani tanlashning faqat bitta usuli bor: kivi, apelsin va banan oling. C=3! / (0!3!)=1.
Beshinchi savol: kamida bitta mevani nechta usulda tanlashingiz mumkin? Bu holat bitta, ikkita yoki uchta mevani olishimiz mumkinligini anglatadi. Shuning uchun biz C1 + C2 + C3=3 + 3 + 1=7 qo'shamiz. Ya'ni, dasturxondan kamida bitta meva olishning ettita usuli bor.
