Toshkent axboorot texnologiyalari universiteti qarshi filiali

1- t e o r e m a . Ixtiyoriy chekli 
A 
to‘plam uchun 
2
A
 
2
A
tenglik o‘rinlidir. 
I s b o t i . Matematik induksiya usulini berilgan 
to‘plamning quvvati bo‘yicha qo‘llaymiz. 
Baza. Dastlab 
A 
to‘plamning elementlari soni 
nolga teng, ya’ni 
| A |0 
bo‘lganda teoremaning 
tasdig‘i bajarilishini ko‘rsatamiz. 
A 
bo‘lsin. U 
holda 
A  A 
uchun 
| A |0
, 
2
A 
2

 {} 
va

---

A 
A 
A 
A 


a 
a 



2

{}  1 2
0 
2
|| 
bo‘ladi. Demak, teoremaning 
tasdig‘i 
| A |0 
bo‘lgan hol uchun to‘g‘ridir. 
Induksion o‘tish. Chekli 
k 
elementli ixtiyoriy 
k 
to‘plam uchun teoremaning tasdig‘i to‘g‘ri bo‘lsin, 
ya’ni 
A 
k 
bo‘lganda 
2
A 
2
| A| 
tenglik bajarilsin. 
k 1 
elementli 
k 1 
to‘plamni qaraymiz. Ravshanki, 
A 
k 1 
uchun 
| A |k 1 
bo‘ladi. Qaralayotgan 
A 
to‘plamning 
ixtiyoriy 
a 
elementi uchun 
2
A 
bulean to‘plamni o‘zaro 
kesishmaydigan ikkita
B
a 
 {X | X 2
A
, a X }
va 
B
a 
 {X | X 2
A
, a X } 
to‘plamlar birlashmasi sifatida 
yozish mumkin. Demak, 
2
A 
 B

 B

. 
Tuzilishiga ko‘ra, 
B
a 
to‘plam 
k 
elementli 

---

to‘plamning buleanidan induksion o‘tish faraziga 
REJA: 
O’rin almashtirishning hosil qiluvchi funksiyasi, guruhlashning hosil 
qiluvchi funksiyasi.

---

n 
n 
n 
1 
1 
1 
n! 
1 
Takrorli o‘rin almashtirishlar.Kombinatorikada oldin qaralgan 
birlashmalardan tashqari tarkibidagi elementlari takrorlanishi mumkin bo’lgan 
boshqa birlashmalar ham o’rganiladi. Masalan, takrorlanuvchi elementlar 
qatnashgan o’rin almashtirishlar, o’rinlashtirishlar va gruppalashlar. 
Avval o’rganilgan o’rin almashtirishlar shunday tuzilmalar ediki, ular 
tarkibidagi elementlar bir-biridan farq qilardi. Endi o’rin almashtirishlar 
tarkibidagi elementlar takrorlanishi mumkin bo’lgan holni qaraymiz. Tabiiyki, 
aynan 
bir 
xil elementlar o’rinlari almashtirilishi natijasida yangi 
o’rin 
almashtirish hosil bo’lmaydi. Shuning uchun tarkibidagi elementlari soni 
o’zgarmaganda elementlari takrorlanishi mumkin bo’lgan o’rin almashtirishlar 
soni turli elementlardan tashkil topgan o’rin almashtirishlar soniga qaraganda 
kichik bo’ladi. 
Faraz qilaylik, qandaydir kortejning n ta elementlari orasida bir xil (aynan bir 
xil) 
1
ta birinchi tur, bir xil 
n
2
ta ikkinchi tur, va hokazo, bir xil 
n
k
ta k - tur 
elementlar bo’lsin, bu yerda 
1 
,
n
2 
,…
n
k
– hech bo’lmaganda bittasi 1dan farqli 
natural sonlar. Bu n ta 
elementlarning 
o’rinlarini 
imkoniyati 
boricha 
almashtirishlar 
natijasida hosil bo’lgan kortejlar (kombinatsiyalar) 
takrorlanuvchi elementlar qatnashgan o‘rin almashtirishlar (qisqacha, takrorli 
o‘rin almashtirishlar) deb ataladi. 
n ta elementlari orasida 
1 
ta birinchi tur, 
n
2 
ta ikkinchi tur, va hokazo, 
n
k 
ta 
k-tur bir xil elementlar bo’lgan takrorli o’rin almashtirishlar sonini 
C
n 
(n , n
2 
,..., n
k 
) 
bilan belgilaymiz.