Diskret tuzilmalar fanidan tayyorlagan iv-mustaqil ish

Takrorli gruppalash
r. Har bir element! birlashmaga istalgancha marta kiritiladigan va turli л ta elementlardan m tadan olinadigan hamda elementlar tartibi e ’tiborga olinmaydigan birlashmalarm (kortejlarni) qaraymiz. 3- ta ’rif. Bimaqa birlashmalar n ta turli elementlardan in tadan takrorlanuvchi elementlar qatnashgan gruppalashlar (qisqacha, takrorli gruppalashlar) deb ataladi. n ta elementdan m tadan takrorlanuvchi elementlar qatnashgan gruppalashlar ta ’rifidan ko'rinib turibdiki, turli kombinatsiyalar bir-birlaridan hech bo'lmasa bitta element! bilan farq qiladi. « ta elementdan m tadan --ni takrorli gruppalashlar sonini С „ deb belgilaymiz.



Isboti. {al,a ^,...,a n} to'plam uchun n ta elementdan m tadan takrorli gruppalashlar sonini aniqlash zarur. Har bir takrorli gruppalashdagi elementlami n ta qismga shunday bo'lish mumkinki, har bir /- bo'lakda a. element qanchadir marta qatnashadi yoki biror marta ham qatnashmaydi. Har bir shunday gruppalashni nol va birlardan iborat kod yordamida quyidagicha shifrlaymiz: har bir aj element o'rniga bu element i- boTakda necha marta qatnashsa, shuncha birlar yozamiz (tabiiyki, bu element biror marta ham qatnashmasligi mumkin, u holda hech narsa yozilmaydi); turli bo Так elementlarini bir-biridan nollar bilan ajratamiz (bu yerda yonma-yon joylashgan nollar hosil bo'lishi mumkin - bu nollar mos elementlarning gruppalashda qatnashmaganhgini anglatadi). Masalan, {a,b,c,d,e,f} to'plam elementlaridan tuzilgan 6ta elementdan 9tadan takrorli bbbcddddf gruppalashga 01110101111001 shifr, 6ta elementdan 12tadan takrorli aaaabeeeeeff gruppalashga esa 1111010011111011 shifr, aksincha, 10100011110 shifrga 6ta elementdan 6tadan takrorli abeeee gruppalash mos keladi. Shunday qilib, n ta elementdan m tadan har bir takrorli gruppalash uchun qandaydir m ta birlar va ( n - 1 )ta nollardan iborat ketma-ketlikni va, aksincha, m ta birlar va (/? —l )ta nollardan tashkil topgan har bir ketma-ketlik uchun n ta elementdan m tadan biror takrorli gruppalashni mos qo'ygan bo'lamiz (bir qiymatli moslik o'rnatildi). Binobarin, /? la 114 elementdan /«tadan takrorli gruppalashlar soni ( n - 1 )ta nol va m ta birlardan tashkil topgan kortej elementlaridan tuzilgan takrorli o'rin almashtirishlar soniga, y a ’ni Cn_m_, (m, n - 1) ga tengdir. Demak,

lasi. Takrorli kombinalsiyalar vositasida Nyuton binomi tushunchasi ni umumlashtiramiz, y a’ni (с/, + a, f ... + a )" ifodaning yoyilmasini topish muammosini qaraymiz. Bulling uchun qaralayotgan ifodam n ta bir xil ifodalar ko'paytmasi, y a’ni