62
̅
formula orqali hisoblanadi.
Isboti:
ta elementli {
} to„plamdan tadan olib
tuzilgan takrorli guruhlashlar sonini topish uchun har bir kombinatsiya-
lar tarkibidagi
̅̅̅̅ elementlarni nol va bir raqamlaridan iborat
kodlar yordamida shifrlaymiz. Agar
element
kombinatsiyada necha
marta qatnashsa, shuncha birlar yozamiz, agar qatnashmasa, hech narsa
yozmaymiz.
Berilgan
{
} to„plam tarkibidagi
vergullarni nol raqami bilan almashtiramiz.
Masalan,
{ } to„plam elementlaridan tuzilgan 4 ta
elementdan 5 tadan takrorli
guruhlashlarga 01100111 shifr
mos keladi. Bu yerda
{ } to„plamdagi elementdan keyingi
vergul 0
raqamiga,
kombinatsiyada element ikki marta
qatnashgani uchun ikkita 11 raqamiga,
{ } to„plamdagi va
elementdan keyingi vergullar 00 raqamiga,
kombinatsiyada
d element uch marta qatnashgani uchun uchta 111
raqamiga akslantirilgan. 01100111 shifr tarkibida beshta 1
raqami va
uchta 0 raqami qatnashmoqda. Agar bu yerda ixtiyoriy bitta 1 va 0
raqami o„rni almashtirilsa, bu shifrga mos yangi kombinatsiya hosil
bo„ladi.
Masalan, 01100111 shifrning birinchi ikki raqami o„rni almash-
tirilsa, hosil bo„lgan 10100111 shifrga
mos kombinatsiya
ko„rinishida bo„lib qolgan kombinatsiyalardan hech bo„lmaganda bitta
elementi bilan farq qiladi. 01100111, 10100111 va hokazo shifrlar
tarkibida
ta va ta nol raqami qatnashyapti.
Demak,
ta elementli {
} to„plamdan
tadan olib
tuzilgan takrorli guruhlashlar sonini 0 va 1 raqamlardan iborat
shifrlarning o„rin almashtirishlar soniga teng. Bu shifr tarkibida
ta 0 raqami,
ta 1 raqami mavjud. Shuning uchun
̅
formula kelib chiqadi.
