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

Isboti . Berilgan n uchun takrorli o’rinlashtirishdagi elementlar soni m
bo’yicha matematik induksiya usulini qo’llaymiz. Baza: takrorli o’rinlashtirishlar m=1 bo’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: .

Induksion o’tish: teoremaning tasdig’i m=k bo’lganda to’g’ri, ya’ni 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 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 .