Mavzu: O’rin almashtirishning hosil qiluvchi funksiyasi, guruhlashning hosil qiluvchi funksiyasi

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,


.