Toshkent axboorot texnologiyalari universiteti qarshi filiali

2- teorema. n ta turli elementlardan m tadan takrorli o‘rinlashtirishlar soni 
n
m
ga 
teng, ya’ni 
A
m 
n
m 
. 
Isboti .Berilgan n uchun takrorli o’rinlashtirishdagi elementlar soni m 
bo’yicha 
matematik 
induksiya 
usulini 
qo’llaymiz. 
Baza: 
takrorli 
o’rinlashtirishlar m=1bo’lganda bitta elementdan tuzilishi ravshan. Tabiiyki, 
bunda hech qanaqa takrorlanish haqida gap bo’lishi mumkin emas. Bu holda 
elementlar soni n bo’lgani uchun takrorli o’rinlashtirishlar soni ham n ga teng: 
A n n
1 
. 
Induksion o’tish: teoremaning tasdig’i m=k bo’lganda to’g’ri, ya’ni 
A
k 
n
k 
bo’lsin. Bu tasdiq m=k+1 bo’lganda ham to’g’ri bo’lishini isbotlaymiz. Buning 
uchun n ta turli elementlardan k tadan takrorli o’rinlashtirishning istalgan birini 
olib, unga n elementli to’plamning ixtiyoriy bitta elementini (k+1)- element 
sifatida kiritamiz. Natijada qandaydir (k+1) tadan takrorli o’rinlashtirishni 
paydo qilamiz. Tabiyki, qaralayotgan k tadan o’rinlashtirishlarning har biridan 
yangi n ta (k+1) tadan takrorli o’rinlashtirishlar hosil qilish mumkin. Shunday 
usul bilan ishni davom ettirsak, barcha mumkin bo’lgan (k+1) tadan takrorli

---

n 
n 
5 
o’rinlashtirishlarni hosil qilamiz, bu yerda birorta ham (k+1) tadan takrorli 
o’rinlashtirishlar qolib ketmaydi va hech qaysi ilgari ko’rilgan (k+1) tadan 
takrorli o’rinlashtirish qaytadan paydo bo’lmaydi. Ko’paytirish qoidasiga 
asosan n ta turli elementlardan (k+1) tadan takrorli o’rinlashtirishlar soni k 
tadan 
takrorli 
o’rinlashtirishlar soniga nisbatan n marta ortiqdir, ya’ni 
A
k 1 
nA
k 
nn
k 
n
k 1 
.