10
),
,
(
1
y
x
m
),...,
,
(
2
y
x
m
)
,
(
n
m
y
x
Ko‘rinib
turibdiki, bu juftliklar soni
m
n ga teng. Buni qisqacha
)
(
)
(
)
(
Y
n
X
n
Y
X
n
ko‘rinishda ham yozish mumkin.
Umuman,
n ta
n
x
x
x
,...,
,
2
1
to‘plamlar berilgan bo‘lsa, u holda
)
(
....
)
(
)
(
)
....
(
2
1
2
1
n
n
x
n
x
n
x
n
x
x
x
n
tenglik o‘rinli bo‘ladi.
2-misol. A shahardan B shaharga uchta yo‘l,
B dan
C ga esa 2 ta yo‘l olib
boradi.
A shahardan
C shaharga necha xil usul bilan borish mumkin?
Yechish. A dan
B ga 1-, 2- va 3-yo‘llar olib boradi.
B shahardan
C shaharga
a
va
b yo‘llar olib boradi.
1-rasm.
U holda
A dan
C ga qo‘yiladigan usullar bilan borish mumkin: (1,
a), (1,
b),
(2,
a), (2,
b), (3,
a), (3,
b). Buni boshqacha usul bilan ham hal qilsa bo‘ladi.
A va
B
gacha boradigan yo‘llarki, tanlash usuli 3 ta,
B dan
C gacha boradigan yo‘llarni
tanlash usuli esa 2 ta. Bunda ko‘paytma qoidasiga ko‘ra, yo‘llarning tartiblangan
juftliklarini
3
2=6 usul bilan tanlash mumkinligi ko‘rinib turibdi.
Quyida kombinatorik masalalardan o‘rin almashtirishlar,
takrorlanmaydigan
o‘rin almashtirishlar, takrorlanmaydigan o‘rinlashtirishlar va guruhlashlarni ko‘rib
chiqamiz.
3. Takrorsiz o‘rin almashtirishlar.
Agar chekli
X to‘plamning elementlari qandaydir yo‘l bilan raqamlangan
bo‘lsa, uni tartiblangan to‘plam deymiz:
}.
,...,
,
{
2
1
n
x
x
x
X
Kortej tushunchasidan
farqli o‘laroq tartiblangan to‘plam elemetlari orasida o‘zaro tenglari bo‘lmaydi.
Masalan, (2,3,2,4,5) kortej tartiblangan to‘plam emas, (2,3,4,5) esa
tartiblangan to‘plam bo‘ladi. Bitta to‘plamni turlicha tartiblash mumkin.
m
A
B
C
a
b
1
2
3
11
elementli
X to‘plamni necha xil usul bilan tartiblash
mumkin degan masalani
qaraymiz.
Har bir tartiblash quyidagicha amalga oshiriladi. To‘plamning qaysi bir
elementini 1-nomer bilan, qaysi birini 2-nomer bilan va hokazo qaysi bir
elementini
m nomer bilan belgilaymiz. Agar birinchi element tanlangan bo‘lsa,
ikkinchi elementni tanlash (
m–1) ta elementning ichidan olinadi. Demak, birinchi
element
m usul bilan, ikkinchisi esa (
m–1) usul bilan tanlanadi. Uchinchi element
(
m–2) usul bilan
va hokazo oxirgi element m-o‘rinni egallaydi. Masalan, {5,6,7}
elementli to‘plam quyidagicha tartiblanadi 567, 657, 756 – birinchi element 3 usul
bilan olindi. 657, 756 – ikkinchi element 2 usul bilan tanlandi. Oxirgi tartiblash
765 bo‘ladi.
Umumiy holda ko‘paytirish qoidasiga asosan tartiblash usulining umumiy soni
!
1
)...
1
(
m
m
m
P
m
ga teng bo‘ladi. Bunday tartiblash
m elementdan
takrorlanmaydigan o‘rin almashtirish deyiladi. Bunda har bir tartiblangan
to‘plamning elementlari turlicha bo‘ladi.