Yechish.
Bu
misolda
10
n
va
3
m
.
Hammasi
bo‗lib
3
10
10 9 8
720
N
A
ta kombinasiya tuzish mumkin.
Javob: 720.
Guruhlashlar (Mosliklar)
n
ta element orasidan
m
ta elementdan tuzilgan guruhlashlar (mosliklar)
deb har birida berilgan
n
ta elementdan
m
tasi olingan shunday birikmalarga
aytiladiki, ularning har biri hech bo‗lmaganda bitta elementi bilan farq qiladi.
Masalan, uchta element
, ,
A B C
lardan ikkita elementli uchta moslik mavjud:
,
,
AB AC BC
.
n
ta element orasidan
m
ta elementdan turli mosliklar soni
m
n
C
bilan
belgilanadi va quyidagicha aniqlanadi:
!
,
(0
).
!(
)!
m
n
n
C
m
n
m n
m
Xossalari:
1.
0
0
0
1
n
C
C
2 .
1
n
C
n
3 .
m
n m
n
n
C
C
4 .
0
1
...
2
n
n
n
n
n
C
C
C
5 .
1
1
1
m
m
m
n
n
n
C
C
C
rekurrent formula, bu yerda
0
m
n
.
3-misol.
Tijorat banki boshqarmasi bir xil lavozimlarga 10 ta nomzoddan 3
tasini tanlamoqda. Har bir nomzod bir xil imkoniyatga ega. 10 ta nomzoddan 3
kishidan iborat nechta guruh tuzish mumkin?
Yechish.
Bu misolda
10
3
n
va m
. Turli guruhlar tarkibi, hech
bo‗lmaganda, bitta nomzodga farq qilishi kerak. Demak, bu birikmalar moslikdan
iborat. Hammasi bo‗lib
3
10
10!
120
7! 3!
N
C
ta guruh tuzish mumkin.
Javob: 120.
Takrorlanishli o‘rin almashtirishlar
Aytaylik,
n
ta
, ,...,
A B
C
elementlar mavjud bo‗lib, ularning ichida
A
element
marta,
B
element
marta va hakozo hamda
C
element
marta
takrorlansin va
...
n
bo‗lsin. U holda, takrorlanishli o‗rin
almashtirishlar quyidagi formula yordamida topiladi:
!
.
! !... !
takr
n
P
Masalan, aytaylik 4 element mavjud bo‗lib, ularning ikkitasi bir xil bo‗lsin:
, , ,
A A B C
. Ulardan mumkin bo‗lgan barcha o‗rin almashtirishlar quyidagicha:
AABC
ABAC
ACBA
BAAC
BCAA
CABA
AACB
ABCA
ACAB
BACA
CBAA
CAAB
Yuqoridagi formula yordamida hisoblanganda ham
!
4!
12
! ! !
2! 1! 1!
takr
n
P
ni hosil qilamiz.
4-misol.
m
n
s
ta predmetni uch guruhga bittasida
t
ta, ikkinchisida
p
ta, uchinchisida esa
s
ta predmet bo‗ladigan qilib necha usul bilan bo‗lish
mumkin?
Yechish.
Yuqoridagi formuladan foydalanib
(
)!
(
)
! ! !
m n s takr
t
p
s
N
P
n m s
ni topamiz.
Takrorlanishli o‘rinlashtirishlar
n
ta elementdan
m
tadan takrorlanishli o‗rinlashtirishlarda (
m n
) ixtiyoriy
element
1 dan
m
martagacha uchrashi yoki umuman uchramasligi mumkin, ya‘ni
har bir
n
ta elementdan
m
tadan takrorlanishli o‗rinlashtirish nafaqat turli
elementlardan, balki
t
ta ixtiyoriy ravishda takrorlanuvchi ixtiyoriy elementlardan
tashkil topgan hech bo‗lmaganda elementlarining joylashish tartibi bilan farq
qiluvchi guruhlarning har xil guruhi hisoblanadi.
Masalan, uchta
, ,
A B C
elementdan ikkitadan takrorlanishli o‗rinlashtirishlar
quyidagicha:
AA
,
BB
,
CC
,
AC
,
BC
,
CA
,
CB
,
BA
,
AB
.
n
ta elementdan
m
tadan takrorlanishli o‗rinlashtirishlar soni
m
n takr
A
bilan
belgilanadi va quyidagi formula bilan hisoblanadi:
.
m
m
n takr
A
n
5-misol.
Seyfning shifrli kodi olti xonali sondan iborat. Kodlashtirganda
nechta turli kombinatsiya tuzish mumkin?
Yechish.
Bu misolda
10
n
, chunki kodlashtirishda
0,1,2,3,4,5,6,7,8,9
raqamlarning hammasidan foydalanish mumkin va kod olti xonali son bo‗lgani
uchun
6
m
. Demak, seyfni
6
10
1000000
m
m
n takr
A
n
usul bilan kodlashtirish mumkin.
Javob: 1000000.
Takrorlanishli guruhlashlar (Mosliklar)
n
ta elementdan
m
tadan element bo‗lgan takrorlanishli mosliklarda
ixtiyoriy element
1 dan
m
martagacha uchrashi yoki umuman uchramasligi
mumkin, ya‘ni har bir
n
ta elementdan
m
tadan takrorlanishli o‗rinlashtirish
nafaqat turli elementlardan, balki
m
ta ixtiyoriy ravishda takrorlanuvchi ixtiyoriy
elementlardan tashkil topishi mumkin. Tarkibi bir xil bo‗lib, faqat elementlarining
tartibi bilan farq qiluvchi guruhlar farq qilinmaydi, ya‘ni faqat elementlarining
joylashish tartibi bilangina farq qiluvchi guruhlar bir xil guruh hisoblanadi.
Masalan, uch
, ,
A B C
elementdan ikkitadan takrorlanishli mosliklar
quyidagicha:
,
,
,
,
,
.
AA BB CC AC BC AB
n
ta elementdan
m
tadan takrorlanishli mosliklar soni
m
n takr
C
bilan
belgilanadi va quyidagi formula bilan hisoblanadi:
1
(
1)!
!(
1)!
m
m
n takr
n m
n
m
C
C
m n
Ta‘kidlash joizki,
m n
dan katta ham bo‗lishi mumkin.
6-misol.
Qandolat do‗konidagi 4 xil shirinlikdan 6 donasini necha xil usul
bilan tanlash mumkin?
Yechish.
Bu misolda
4
6
n
va m
. Demak,
4 turdagi shirinliklardan 6
donasini
6
6
6
4
4 6 1
9
9!
84
6!3!
takr
C
C
C
usul bilan tanlash mumkin.
Javob: 84.
Kombinatorikaning asosiy qoidalari
Kombinatorikaning asosiy qoidalarini keltiramiz.
Qo‘shish qoidasi (mantiqiy qo‘shish tamoyili)
Agar
a
elementni
m
ta usul bilan,
b
elementni esa boshqa
n
ta usul bilan
tanlash mumkin bo‗lsa, u holda ularning birlashmasidan
a
yoki
b
ni
m
n
usul
bilan tanlash mumkin.
Ko‘paytirish qoidasi (mantiqiy ko‘paytirish tamoyili)
Agar
a
elementni
m
ta usul bilan tanlash mumkin bo‗lib, har bir ana
shunday tanlashdan so‗ng
b
elementni
m
ta usul bilan tanlash mumkin bo‗lsa, u
holda
( , )
a b
juftlikni ko‗rsatilgan tartibda
m n
usul bilan tanlash mumkin.
Bu qoidalar ixtiyoriy sondagi elementlar uchun ham o‗rinli.
7-misol.
Maishiy texnika do‗konida sotuvga uch xil televizor va ikki xil
telefon chiqarilgan. Xaridor televizor yoki telefon sotib olish imkoniyatiga ega.
a) u bitta xaridni necha usul bilan amalga oshirishi mumkin?
b) agar xaridor televizor va telefon sotib olmoqchi bo‗lsa, u holda nechta
turli juftliklar bo‗lishi mumkin?
Yechish.
a) Bitta televizorni uchta usul bilan, telefonni esa ikki usul bilan
sotib olish mumkin. U holda televizor yoki telefonni besh usul bilan sotib olish
mumkin, ya‘ni
3 2
5
N
n
m
b)
, ,
a b c
— televizorlar rusumi;
,
x u
— telefonlar rusumi bo‗lsin. Agar
a
rusumdagi televizor tanlangan bo‗lsa, u holda
ax
va
au
juftliklari bo‗lishi
mumkin. Agar
b
rusumdagi televizor tanlangan bo‗lsa,
bx
va
bu
juftliklarni hosil
qilish mumkin. Va nihoyat,
c
rusumdagi televizor tanlangan bo‗lsa,
cx
va
cu
juftliklarni hosil qilish mumkin. Shunday qilib, televizor tanlanganidan so‗ng ikki
usul bilan telefon tanlanishi mumkin. Demak, hammasi bo‗lib 6 ta turli juftliklar
tanlash mumkin ekan.
3 2
6
N
n m
.
Javob: 6.
| 