Hosil qiluvchi funksiyalar. Kompozitsiya fomulasi isbotiva misollar

Takrorli gruppalashlar. Har bir elementi birlashmaga istalgancha marta kiritiladigan va turli n ta elementlardan m tadan olinadigan hamda elementlar tartibi e’tiborga olinmaydigan birlashmalarni (kortejlarni) qaraymiz. Bunaqa birlashmalar n ta turli elementlardan m tadan takrorlanuvchi elementlar qatnashgan gruppalashlar (qisqacha, takrorli gruppalashlar) deb ataladi.
n ta elementlardan m tadan takrorlanuvchi elementlar qatnashgan gruppalashlar ta’rifidan ko’rinib turibdiki, turli kombinatsiyalar bir-birlaridan hech bo’lmasa bitta elementi bilan farq qiladi. n ta elementdan m tadan takrorli gruppalashlar sonini deb belgilaymiz.
3- teorema. n ta elementdan m tadan takrorli gruppalashlar soni ga teng, ya’ni .
Isboti. to’plam uchun n ta elementdan m tadan takrorli gruppalashlar sonini aniqlash zarur. Har bir takrorli gruppalashdagi elementlarni n ta qismga shunday bo’lish mumkinki, har bir i - bo’lakda element qanchadir marta qatnashadi yoki biror marta ham qatnashmaydi. Har bir shunday gruppalashni nol va birlardan iborat kod yordamida quyidagicha shifrlaymiz: har bir element o’rniga bu element i - bo’lakda necha marta qatnashsa, shuncha birlar yozamiz (tabiiyki, bu element biror marta ham qatnashmasligi mumkin, u holda hech narsa yozilmaydi); turli bo’lak elementlarini bir-biridan nollar bilan ajratamiz (bu yerda yonma-yon joylashgan nollar hosil bo’lishi mumkin – bu nollar mos elementlarning gruppalashda qatnashmaganligini anglatadi). Masalan, to’plam elementlaridan tuzilgan 6 ta elementdan 9 tadan takrorli gruppalashga0111010111 1001 shifr, 6 ta elementdan 12 tadan takrorli gruppalashga esa 1111010011111011 shifr, aksincha, 0 1010001111 shifrga 6ta elementdan 6tadan takrorli 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 (n-1)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, n ta elementdan m tadan takrorli gruppalashlar soni (n-1)ta nol va m ta birlardan tashkil topgan kortej elementlaridan tuzilgan takrorli o’rin almashtirishlar soniga, ya’ni ga tengdir. Demak,
.