Universiteti mustaqil ish

Teorema 2.1. Berilgan n ta elementdan m tadan tuzilgan takroriy oʻrinlashtirishlar soni
(2.5)
formula bilan aniqlanadi.
Isbot. Teoremani matematik induksiya yordamida isbotlaymiz. mq1 da teorema toʻgʻri, chunki bunda elementlarning oʻzidir:

Demak, ni tuzamiz. Faraz qilaylik n elementdan (m-1) tadan tuzilgan takroriy oʻrinlashtirishlar uchun teorema toʻgʻri boʻlsin, ya`ni takroriy oʻrinlashtirishlar soni quyidagiga teng
.
Berilgan n elementdan m tadan tuzish mumkin boʻlgan takroriy oʻrinlashtirishlar tuzamiz. Ularni lardan tuzamiz. Bu n ta elementdan (sonlardan) m tadan tuzilgan takroriy oʻrinlashtirishlar
k<sub>1</sub>, k<sub>2</sub>, …, k<sub>m-1</sub>, k<sub>m</sub>
sonlardan tuziladi. Bundagi dastlabki (m-1) ta
k<sub>1</sub>, k<sub>2</sub>, …, k<sub>m-1</sub>
sonlar n ta sonlardan (1, 2, 3, …, n sonlardan) (m-1) tadan tuzilgan takroriy oʻrinlashtirishning koʻrinishini ifodalaydi. Oxirgi k<sub>m</sub> element sifatida 1, 2, 3, …, n sonlardan ixtiyoriy bittasini olish mumkin, ya`ni . Bu k_m ning har xil qiymatida har xil birlashma hosil boʻladi. Shu usul bilan berilgan (m-1) tadan tuzilgan oʻrinlashtirishlardan m tadan tuzilgan n ta har xil oʻrinlashtirishlar hosil qilinadi. Ikkita (m-1) tartibli har xil oʻrinlashtirishlar ikkita m tartibli oʻrinlashtirishlarni hosil qiladi, ya`ni, agar
k₁, k₂, …, k_m-1 va l₁, l₂, …, l_m-1
lar har xil boʻlsa, u holda
k₁, k₂, …, k_m-1, k_m va l₁, l₂, …, l_m-1, l_m
oʻrinlashtirishlar ham har xil boʻladi, bunda k_s=l_s, s=1, 2, …, m-1.
Shunday qilib har bir m-1 tartibli oʻrinlashtirishlardan n ta m tartibli oʻrinlashtirish hosil boʻladi. Bu oʻrinlashtirishlar har xil boʻlib barcha m – tartibli oʻrinlashtirishlardan iborat. Shunday qilib, hamma m tartibli oʻrinlashtirishlar soni

ga teng. Demak, teorema ixtiyoriy m uchun oʻrinli. Bunda m>n, mqn, m boʻlishi mumkin.