Mavzu: Bo‘laklashlar kombinatorikasi

1- teorema. Qo‘shiluvchilar tartibini e’tiborga olgan holda istalgan natural sonning ta qo‘shiluvchilarga bo‘laklanishlari soni ( )ta elementdan ( )talab gruppalashlar soniga teng, ya’ni .
Isboti o‘quvchiga havola qilinadi. ■
Yuqorida bayon etilgan mulohazalar yordamida va 1- teoremaga tayangan holda isbotlash osonligini ta’kidlab, quyidagi teoremani boshqa usul bilan isbotlaymiz.
2- teorema. Qo‘shiluvchilar tartibini e’tiborga olgan holda ixtiyoriy natural sonning barcha bo‘laklanishlari soni ga teng, ya’ni .
Isboti. Natural sonning barcha bo‘laklanishlari to‘plamini deb, shu sonning birinchi qo‘shiluvchisi ga ( ) teng bo‘lgan bo‘laklanishlari to‘plamini esa bilan belgilaymiz. Tushunarliki, bo‘ladi. Agar to‘plam elementlari sonini deb belgilasak, yuqoridagi tenglikka asosan bo‘ladi. Endi ( ) va tengliklarni hisobga olib,

tenglikka ega bo‘lamiz. Bu tenglik ixtiyoriy natural son uchun to‘g‘ri. Shuning uchun, bu tenglikdagi ni ( )ga almashtirib,
,
ya’ni ( ) ko‘rinishdagi rekurrent munosabatni hosil qilamiz. Bu rekurrent munosabat ketma-ket qo‘llanilsa, kelib chiqadi. ■
2- misol. To‘qqiz qavatli binoning birinchi qavatidan sakkiz kishi liftda yuqoriga ko‘tarilayotgan bo‘lsin. Agar to‘qqizinchi qavatga liftdagi kishilarning faqat bittasi chiqishi shart bo‘lsa, lift yo‘lovchilarining bino qavatlariga chiqish imkoniyatlari sonini aniqlang.
Masalaning shartiga binoan, liftdagi sakkiz kishidan faqat bir kishi to‘qqizinchi qavatga chiqishi shart bo‘lgani uchun, qolgan yetti kishining ikkinchi qavatdan sakkizinchi qavatgacha chiqishining ko‘p imkoniyatlari bor. Bu imkoniyatlar soni liftning birinchi va to‘qqizinchi qavatlar orasidagi to‘xtashlar sonidan bog‘liq bo‘lib, yettining barcha bo‘laklanishlari yordamida ifodalanishi mumkin. Masalan, lift binoning ikkinchi qavatidan sakkizinchi qavatigacha faqat bir marta to‘xtab, liftdagi yetti kishi tushib qolgan bo‘lsa, u holda bu hodisa ko‘rinishdagi bo‘laklash vositasida ifodalanadi; agar to‘qqizinchi qavatgacha lift ikki marta to‘xtab, oldin uch kishi, keyin to‘rt kishi tushib qolgan bo‘lsa, bu holatga ko‘rinishdagi bo‘laklash mos keladi va hokazo.
2- teoremadan foydalanib, yettining barcha bo‘laklanishlari soni ekanligini topamiz. Demak, agar to‘qqizinchi qavatga faqat bir kishi chiqishi shart bo‘lsa, u holda lift yo‘lovchilarining bino qavatlariga chiqish imkoniyatlari soni 64ga tengdir. Agar hal qilingan masalada to‘qqizinchi qavatga faqat bir kishining chiqishi sharti bo‘lmasa edi, u holda sakkizning barcha bo‘laklanishlari sonini topishga to‘g‘ri kelar edi. ■
Endi natural sonlarni qo‘shiluvchilar tartibi e’tiborga olinmagan vaziyatda bo‘laklash masalasi bilan shug‘ullanamiz.
Odatda, natural sonning ixtiyoriy ta ( – natural son, ) qo‘shiluvchilarga bo‘laklanishini qandaydir shartlarga, masalan, yoki tengsizliklarga bo‘ysunadigan qilib olish qulay bo‘ladi.
Qo‘shiluvchilar tartibi e’tiborga olinmagan holda natural sonning ta qo‘shiluvchilarga bo‘laklanishlari sonini bilan, uning barcha bo‘laklanishlari sonini esa bilan belgilaymiz.
Bundan keyin, bo‘laklash deganda qo‘shiluvchilar tartibi e’tiborga olinmagan holdagi bo‘laklashni nazarda tutamiz.
Tabiiyki, quyidagi tenglik o‘rinlidir:
.
Osonlik bilan ko‘rish mumkinki, , , , , , , .