Kombinatorikada qo'shish va ko'paytirish qoidalari

Takrorlashsiz almashtirishlar. Takrorlashlar bilan almashtirishlar
Kombinatorikaning klassik muammosi - takrorlanmasdan almashtirishlar soni masalasi bo'lib, uning mazmunini savol bilan ifodalash mumkin: necha yo'llari mumkin joy n har xil buyumlar ustida n boshqacha joylar?
7-misol
“Nikoh” so‘zining harflaridan nechta to‘rt harfli “so‘z” yasalishi mumkin?
Qaror
Umumiy to'plam "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) 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 ob'ektni n ta turli joyga necha xil usulda joylashtirish mumkin?< n), т. е. есть одинаковые предметы.
8-misol
"Mississipi" so'zining harflaridan nechta turli harf birikmalarini yasash mumkin?
Qaror
1 ta “m”, 4 ta “i”, 3 ta “c” va 1 ta “p” harfi, jami 9 ta harf bor. Shuning uchun, takroriy almashtirishlar soni
"KOMBİNATORIKA" BO'limi bo'yicha XULOSA
Ushbu maqolada asosiy e'tibor matematikaning kombinatorika deb ataladigan maxsus bo'limiga qaratiladi. Formulalar, qoidalar, muammolarni 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. Lekin ichida bu holat ob'ektlar olxo'ri, nok yoki olma emas, balki boshqa narsadir. Kombinatorika bizga hodisa ehtimolini topishga yordam beradi. Misol uchun, karta o'ynaganda - raqibning kozi borligi 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.
Kombinatsion konfiguratsiyalar
Kombinatorikaning asosiy tushunchalari va formulalari haqidagi savolni ko'rib chiqsak, biz kombinatorik konfiguratsiyalarga e'tibor bermaslik mumkin emas. Ular nafaqat shakllantirish, balki hal qilish uchun ham qo'llaniladi turli misollar bunday modellar:

• 
  turar joy;
  
• 
  almashtirish;
  
• 
  kombinatsiya;
  
• 
  raqam tarkibi;
  
• 
  raqamni ajratish.
  

Birinchi uchtasi haqida keyinroq batafsilroq gaplashamiz, ammo biz ushbu bo'limda kompozitsiyaga va bo'linishga e'tibor beramiz. Ular ma'lum sonning tarkibi haqida gapirganda (aytaylik, a) a sonining ba'zilarning tartibli yig'indisi sifatida ifodalanishini anglatadi. ijobiy raqamlar. Bo'linish tartibsiz yig'indidir.
Bo'limlar
To'g'ridan-to'g'ri kombinatorika formulalariga va muammolarni ko'rib chiqishga o'tishdan oldin, matematikaning boshqa bo'limlari kabi kombinatorikaning ham o'ziga xos bo'limlari borligiga e'tibor qaratish lozim. Bularga quyidagilar kiradi:

• 
  sanoqli;
  
• 
  tizimli;
  
• 
  ekstremal;
  
• 
  Remsi nazariyasi;
  
• 
  ehtimollik;
  
• 
  topologik;
  
• 
  cheksiz.
  

Birinchi holda, biz hisoblash kombinatoriyasi haqida gapiramiz, muammolar ro'yxatga olish yoki hisoblashni ko'rib chiqadi. turli xil konfiguratsiyalar, ular to'plamlar elementlari orqali hosil bo'ladi. Qoidaga ko'ra, 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. Ehtimoliy kombinatorika 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 uzoq vaqtdan beri tanish bo'lgan juda oddiylarini ham 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 butun fikrni etkazishga harakat qilamiz oddiy misol. Keling, olamiz o'rtacha aholi bir sinf o'quvchilari - yigirma besh, deylik. 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 maktab o'quvchisi osonlikcha bajara oladigan juda oddiy misolni olamiz boshlang'ich maktab: 15 + 10. Hisoblashdan keyin biz javob olamiz: yigirma besh. Ya'ni, bugungi kun uchun navbatchi sinfini belgilashning faqat yigirma beshta usuli bor.
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 c1 * c2 * c3 * ... * ca.
Shunga qaramay, nazariy jihatdan hech narsa aniq emas, keling, ko'paytirish qoidasini qo'llashning oddiy misoliga o'taylik. 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 navbatchini tanlaymiz, oxirgi xatboshida qaror qilganimizdek, biz yigirma beshni olamiz variantlari. 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 biz kombinatorikaning yana bir formulasini ko'rib chiqamiz. Maqolaning ushbu qismida biz almashtirishlar haqida gapiramiz. Muammoni darhol misol bilan ko'rib chiqing. Keling, bilyard to'plarini olaylik, bizda ularning n-soni bor. Biz hisoblashimiz kerak: ularni ketma-ket joylashtirish, ya'ni buyurtma qilingan to'plamni yaratish uchun qancha variant bor.
Boshlaylik, agar bizda to'plar bo'lmasa, bizda ham joylashtirish variantlari 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). Ikkita to'p ikkiga joylashtirilishi mumkin turli yo'llar bilan: 1.2 va 2.1. Demak, P2 = 2. Uchta sharni oltita usulda joylashtirish mumkin (P3=6): 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 = n*P(n-1). Agar formulani soddalashtirishga harakat qilsak, biz olamiz: Pn = n* (n - 1) *…* 2 * 1. Va bu birinchisining mahsulotidir. natural sonlar. Bunday son faktorial deyiladi va n sifatida belgilanadi!
Keling, muammoni ko'rib chiqaylik. Rahbar har kuni ertalab o'z otryadini bir qatorga (yigirma kishi) quradi. Jamoada uchta eng yaqin do'st- 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 bizda faqat o'n sakkizta mavzu 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 ga teng. Agar foizlarga tarjima qilingan bo'lsa, bu faqat 1,6% ni tashkil qiladi.
Turar joy
Endi biz yana bir juda muhim va zarur kombinatorik formulani 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, n ta elementni m ga almashtirishlarini ko'rib chiqamiz.
Kombinatorikaning asosiy formulalarini shunchaki eslab qolmaslik, 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 ixcham formulaga ega bo'lamiz: A \u003d n! / (n - m)!
Kombinatsiya
Kombinatorikaning deyarli barcha asosiy formulalarini misollar bilan ko'rib chiqdik. Endi ko'rib chiqishning yakuniy bosqichiga o'tamiz asosiy kurs kombinatorika - birikma bilan tanishish. Endi biz mavjud bo'lgan n dan m ta elementni tanlaymiz, hammasi esa hammasini tanlaymiz mumkin bo'lgan usullar. Xo'sh, bu turar joydan qanday farq qiladi? Biz buyurtmani hisobga olmaymiz. Bu tartibsiz to'plam kombinatsiya bo'ladi.
Biz darhol belgini kiritamiz: C. Biz n dan m to'pning joylashishini olamiz. 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 kerak maksimal raqam elementlarning yarmini tanlashga urinish orqali kombinatsiyalarga erishish mumkin.
Muammoni hal qilish uchun formulani qanday tanlash mumkin?
Biz kombinatorikaning asosiy formulalarini batafsil ko'rib chiqdik: joylashtirish, almashtirish va kombinatsiya. Endi bizning vazifamiz tanlovni osonlashtirishdir zarur formula kombinatorikadagi masalani yechish. Siz quyidagi juda oddiy sxemadan foydalanishingiz mumkin:

1. 
   O'zingizga savol bering: topshiriq matnida elementlarning tartibi hisobga olinadimi?
   
2. 
   Agar javob yo'q bo'lsa, kombinatsiya formulasidan foydalaning (C \u003d n! / (m! * (n - m))).
   
3. 
   Agar javob yo'q bo'lsa, unda yana bir savolga javob berish kerak: barcha elementlar kombinatsiyaga kiritilganmi?
   
4. 
   Agar javob ha bo'lsa, almashtirish formulasidan foydalaning (P = n!).
   
5. 
   Agar javob yo'q bo'lsa, unda joylashtirish formulasidan foydalaning (A = n! / (n - m)!).
   

Misol
Biz kombinatorikaning elementlarini, formulalarni va boshqa ba'zi masalalarni ko'rib chiqdik. Endi ko'rib chiqaylik haqiqiy vazifa. Tasavvur qiling-a, sizning oldingizda kivi, apelsin va banan bor.
Birinchi savol: ularni necha xil usulda qayta tartibga solish mumkin? Buning uchun biz almashtirish formulasidan foydalanamiz: P = 3! = 6 yo'l.
2-savol: Bitta mevani necha xil usulda tanlash mumkin? Bu aniq, bizda faqat uchta variant bor - kivi, apelsin yoki bananni tanlang, ammo biz kombinatsiya formulasini qo'llaymiz: C \u003d 3! / (2! * 1!) = 3.
3-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
4-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.
5-savol: Kamida bitta mevani necha xil usulda tanlashingiz mumkin? Bu holat bitta, ikkita yoki uchta mevani olishimiz mumkinligini anglatadi. Shuning uchun biz C1 + C2 + C3 = 3 + 3 + 1 = 7 ni qo'shamiz. Ya'ni, bizda stoldan kamida bitta meva olishning ettita usuli bor.
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 hodisalarning rivojlanishi.
Kombinatorikaning asosiy formulasi
Elementlarning k guruhi bo'lsin, va i-guruh n i elementdan iborat. Har bir guruhdan bitta elementni tanlaymiz. Keyin umumiy soni Bunday tanlovni amalga oshirishning N ta 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, birinchi guruh n 1 ta elementdan, ikkinchisi esa n 2 ta elementdan iborat. Bu ikki guruhdan nechta turli juft elementlar yasash mumkin, shunda juftlikda har bir guruhdan bitta element bo‘ladi? Aytaylik, biz birinchi guruhdan birinchi elementni oldik va uni o'zgartirmasdan, faqat ikkinchi guruhning elementlarini o'zgartirib, barcha mumkin bo'lgan juftliklardan o'tdik. Bu element uchun n ta 2 ta shunday juftlik mavjud. Keyin biz birinchi guruhdan ikkinchi elementni olamiz va buning uchun barcha mumkin bo'lgan juftlarni ham qilamiz. Shuningdek, n ​​2 ta shunday juftlik bo'ladi. Birinchi guruhda faqat n 1 ta element bo'lgani uchun n 1 *n 2 ta mumkin bo'lgan variant bo'ladi.
2-misol Raqamlarni takrorlash mumkin bo'lsa, 0, 1, 2, 3, 4, 5, 6 raqamlaridan nechta uch xonali juft sonlar yasalishi mumkin?
Qaror: n 1 \u003d 6 (chunki siz birinchi raqam sifatida 1, 2, 3, 4, 5, 6 dan istalgan raqamni olishingiz mumkin), n 2 \u003d 7 (chunki siz 0 dan istalgan raqamni ikkinchi raqam sifatida olishingiz mumkin , 1 , 2, 3, 4, 5, 6), n 3 \u003d 4 (chunki siz uchinchi raqam sifatida 0, 2, 4, 6 dan istalgan raqamni olishingiz mumkin).
Demak, N=n 1 *n 2 *n 3 =6*7*4=168.
Barcha guruhlar bo'lganda bir xil raqam elementlar, ya'ni. n 1 =n 2 =...n k =n har bir tanlov bir xil guruhdan qilingan deb faraz qilishimiz mumkin va element tanlovdan keyin guruhga qaytadi. Keyin tanlashning barcha usullari soni n k ga teng. Kombinatorikada tanlashning bunday usuli deyiladi namunalarni qaytarish.
3-misol 1, 5, 6, 7, 8 raqamlaridan nechta to‘rt xonali son yasash mumkin?
Qaror. To'rt xonali sonning har bir raqami uchun beshta imkoniyat mavjud, shuning uchun N=5*5*5*5=5 4 =625.
n ta elementdan iborat to'plamni ko'rib chiqaylik. Kombinatorikadagi bu to'plam deyiladi umumiy aholi.
n ta elementdan joylashtirishlar soni m