Takrorli kombinatsiyalar Takrorli o‘rin almashtirishlar

1- misol. Ikkita , bitta va ikkita harflardan tashkil topgan kortej uchun barcha takrorli o‘rin almashtirishlarni tuzing.
Bu misolda uch turdagi ( ) harflar soni beshga teng (n=5) bo‘lib, (ikkita ), (bitta ) va (ikkita ). Dastlabki ikkita harflarning (xuddi shuningdek, oxirgi ikkita harflarning ham) o‘rinlarini o‘zaro almashtirsak yangi o‘rin almashtirishlar hosil bo‘lmaydi. Barcha takrorli o‘rin almashtirishlar soni bo‘ladi. Bu o‘ttizta o‘rin almashtirishlarning hammasi quyida keltirilgan:
,
,
,
,
.
Takrorli joylashtirishlar. ta elementlardan tashkil topgan to‘plam berilgan bo‘lsin. Bu elementlardan foydalanib, ta elementdan tashkil topgan kortejlarni shunday tuzamizki, bu kortejlarga har bir element hohlagancha marta (albatta dan oshmagan miqdorda) kirishi mumkin bo‘lsin va bu kortejlar bir-biridan ularni tashkil etuvchi elementlar turlari bilan yoki bu elementlarning joylashishlari bilan farq qilishsin. Shunday usul bilan tuzilgan kortejlarning har biri ta turli elementlardan takrorlanuvchi elementlar qatnashgan tadan joylashtirish (qisqacha, takrorli joylashtirish) deb ataladi.
ta turli elementlardan tadan takrorli joylashtirishlar sonini bilan belgilaymiz.
2- teorema. ta turli elementlardan tadan takrorli joylashtirishlar soni ga teng, ya’ni .
Isboti. Berilgan uchun takrorli joylashtirishdagi elementlar soni bo‘yicha matematik induksiya usulini qo‘llaymiz. Baza: takrorli joylashtirishlar bo‘lganda bitta elementdan tuzilishi ravshan. Tabiiyki, bunda hech qanaqa takrorlanish haqida gap bo‘lishi mumkin emas. Bu holda elementlar soni bo‘lgani uchun takrorli joylashtirishlar soni ham ga teng: .
Induksion o‘tish: teoremaning tasdig‘i bo‘lganda to‘g‘ri, ya’ni bo‘lsin. Bu tasdiq bo‘lganda ham to‘g‘ri bo‘lishini isbotlaymiz. Buning uchun ta turli elementlardan tadan takrorli joylashtirishning istalgan birini olib, unga elementli to‘plamning ixtiyoriy bitta elementini ( )- element sifatida kiritamiz. Natijada qandaydir ( )tadan takrorli joylashtirishni paydo qilamiz. Tabiyki, qaralayotgan tadan joylashtirishlarning har biridan yangi ta ( )tadan takrorli joylashtirishlar hosil qilish mumkin. Shunday usul bilan ishni davom ettirsak, barcha mumkin bo‘lgan ( )tadan takrorli joylashtirishlarni hosil qilamiz, bu yerda birorta ham ( )tadan takrorli joylashtirishlar qolib ketmaydi va hech qaysi ilgari ko‘rilgan ( )tadan takrorli joylashtirish qaytadan paydo bo‘lmaydi. Ko‘paytirish qoidasiga asosan ta turli elementlardan ( )tadan takrorli joylashtirishlar soni tadan takrorli joylashtirishlar soniga nisbatan marta ortiqdir, ya’ni .