12
Bunda
!
m
P
A
m
m
m
bo‘ladi, bu yerda 0!=1 deb olinadi.
5. Takrorlanuvchi o‘rinlashtirishlar.
Bu yerda quyidagi masala qaraladi:
m elementli
X to‘plamdan nechta uzunligi
k ga teng bo‘lgan kortejlar tuzish mumkin. Bu
masalani hal qilish uchun
X
X
X
...
dan iborat
k ta ko‘paytuvchiga ega bo‘lgan Dekart ko‘paytmadagi
kortejlar sonini topish yetarli. Bunda
k
m
k
A
m
m
m
m
X
n
X
n
X
n
X
X
X
n
....
)
(
)...
(
)
(
)
...
(
Demak,
m elementli
X to‘plamdan tuzilgan uzunligi
k ga teng bo‘lgan kortejlar
soni
k
k
m
m
A
ga teng.
m elementli
X to‘plam elementlaridan tuzilgan uzunligi
k ga teng bo‘lgan
kortej,
m elementdan
k tadan tuzilgan
takrorlanadigan o‘rinlashtirish deyiladi.
3-misol.
}
,
,
{
c
b
a
X
uch elementli to‘plam elementlaridan uzunligi 2
ga teng
bo‘lgan nechta kortej tuzish mumkin.
Yechish. Ular quyidagilardan iborat:
(a, a), (a, b), (a, c)
(b, a), (b, b), (b, c)
(c, a), (c, b), (c, c)
Ularning soni
9
3
2
2
3
A
ta bo‘ladi.
4-misol. Agar sonning yozuvida raqamlarning takrorlanishi mumkin bo‘lsa, 1,
2, 3
raqamlardan foydalanib nechta 3 xonali son tuzish mumkin?
Yechish. Uch xonali sonlarning yozuvidagi har bir o‘ringa berilgan uchta
raqamdan istalgan birini qo‘yish mumkin, ya’ni 1-raqamning tanlash usuli 3 ta, 2-
raqamning tanlash usuli 3 ta, 3-raqamning tanlash usuli ham 3 ta. Demak, bu holda
27
3
3
ta uch xonali son tuzish mumkin.
6. Takrorsiz guruhlashlar.
Endi biz kombinatorikaning quyidagi masalasini qaraymiz:
m elementli
X elementlaridan nechta
har biri k elementli qism to‘plamlar tuzish
mumkin?
13
Bunday qism to‘plamlar
m elementdan
k tadan
takrorlanmaydigan
guruhlashlar deyiladi. Ularning soni
k
m
C
bilan belgilanadi.
Ko‘rsatish mumkinki,
!
)!
(
!
k
k
m
m
C
k
m
bo‘ladi.
5-misol. 12 kishilik guruhdan nechta 5 kishilik (ishchilar) delegatsiya tuzish
mumkin.
Yechish.
.
792
5
4
3
2
1
12
11
10
9
8
!
5
!
7
!
12
5
12
C
7. Chekli to‘p lamning qism to‘plamlari soni.
Chekli to‘plamlarning qism to‘plamlari soni.
Umumiy holda chekli m
elementli
X to‘plamning barcha qism to‘plamlari sonini topish masalasini
qaraymiz. Uni hal qilish uchun istalgan tarzda
X to‘plamni tartiblaymiz. So‘ng har
bir qism to‘plamni
m o‘rinli kortej sifatida shifrlaymiz: qism to‘plamga
kirgan
element o‘rniga 1, kirmagan element o‘rniga 10 yozamiz. Shunda qism to‘plamlar
soni 2 ta 50,1 elementdan tuzilgan barcha m o‘rinli kortejlar soniga teng bo‘ladi.
.
2
2
m
k
A
Masalan, 2 element to‘plam ostilari soni 2
2
=4, 3 elementli
to‘plamning to‘p lam ostilari soni 2
3
=8 ga teng.
