Mavzu: Kombinatorika elementlari

O‘rinlashtirishlar, o’rin almashtirishlar, birikmalar.

Predmetlardan tashkil topgan tuzilmalar kombinatsiyalardeb ataladi.
Uch xil turdagi kombinatsiyalar o‘rganiladi: o‘rin almashtirish, o‘rinlashtirish va birikmalar.

O’rinlashtirishlar

A ^{alfavit n ta belgidan tashkil topgan bo‘lsin. Uzunligi m ga teng bo‘lgan} so‘zlar (ya’ni uzunligi m ga teng bo‘lgan ketma-ketliklar) sonini sanab chiqaylik.
Har bir so‘zni tashkil etgan belgilar orasidagi takrorlanadiganlari bor

bo‘lgan holda bunday so‘zlar sonini



n
A^m ( n ta elementdan m tadantakrorli

A

n
o‘rinlashtirishlar soni), bu belgilarning barchasi har hil bo‘lgan holda ^m
(takrorsiz o‘rinlashtirishlar soni ) deb belgilaymiz.
Bu ikki miqdor uchun formulalar quyidagicha:

n
^{Am  nm} ,
A^m  n(n 1)(n  2) (n  m  1) 
n! _.
(n  m)!

n
Bu yerda n!  1 2  3 ... n, 0!  1 (n – faktorial deb o‘qiladi)
^{Endi uzunligi} m ^{dan ko‘p bo‘lmagan so‘zlar sonini sanab chiqaylik.}
Bunda qo’shish (jamlash) qoidasiga ko‘ra so‘zlarni tashkil etgan belgilar orasidagi takrorlanadiganlari bor bo‘lgan holda bunday so‘zlar soni
n

n n n n n
_ ^{Ak  A0  A1  A2  ...  Am  1  n  n2  n3  ...  nm} ga,
k 0
bu belgilarningbarchasi har hil bo‘lgan holda

_ ^{A A  A  A  ...  A} ga teng.
n
k 0 1 2 m
n n n n n
k 0
Misol. 1)20 ta belgidan tashkil topgan alfavit berilgan bo‘lsin.
Uzunligi 3 ga teng bo‘lgan so‘zlar sonini sanab chiqaylik. Bunda belgilarning barchasi takrorlanmasin.

A

20
Yechilishi. ³  20(20 1)(20  2)  6840
2) 20 ta belgidan tashkil topgan alfavit berilgan bo‘lsin.
Uzunligi 3 ga teng bo‘lgan so‘zlar sonini sanab chiqaylik. Bunda belgilarning ayrimlari takrorlanishi mumkin.

Yechilishi.



A

20
^{3  203  8000} . ■

O’rin almashtirishlar.

n ^{ta elementli o‘rin almashtirishlar deb, bir-biridan faqat elementlarining
tartibi bilan farq qiladigan} n ^{ta elementli birikmalarga aytiladi.}

^{Masalan, 3 ta} A,
B va C
elementdan 6 ta o‘rin almashtirish bajarish

mumkin:
ABC,
BAC,
ACB,
CAB,
CBA,
BCA^.

n ^{ta elementli o‘rin almashtirishlar soni quyidagi formula yordamida}

hisoblanadi:
^{Pn  1 2  } ^{n 1} ^{ n  n!}

Misol.1)Afsuski, bugun, yomg‘ir, yog‘adi so‘zlaridan nechta gap tuzish mumkin?

Yechilishi.
P₄  1 2  3  4  24 . ■

2)w,e,d,i,g,m,a,t,h harflarining “we”,”dig”,”math” so‘zlaridan hech qaysisini o‘z ichiga olmagan barcha o‘rin almashtirishlar nechta? Masalan, d,g,i,w,e,t,h,m,a shu shartni qanoatlantirmaydi.
Yechilishi. Barcha o‘rin almashtirishlar soni 9!  362880 ga teng.
“we” so‘zini o‘z ichiga olmagan barcha o‘rin almashtirishlar to‘plamini A₁
,”dig” so‘zini o‘z ichiga olmagan barcha o‘rin almashtirishlar to‘plamini A₂

”math” so‘zini o‘z ichiga olmagan barcha o‘rin almashtirishlar to‘plamini A₃
deylik.
Kamida bitta so‘zni o‘z ichiga olmagan barcha o‘rin almashtirishlar soni

A₁
ga teng. Ravshanki,
 A₂  A₃

• 
  A₁
  

• 
  A₁
  

A₁  8! (we,d,i,g,m,a,t,h elementlarning o‘rin almashtirishlari soni), A₂  7! (w,e,dig,m,a,t,h elementlarning o‘rin almashtirishlari soni), A₃  6! (w,e,d,i,g,math elementlarning o‘rin almashtirishlari soni),

A₁ A₂
A₂ A₃
A₁ A₃ A₁
 6! (we,dig,m,a,t,h elementlarning o‘rin almashtirishlari soni),
 4! (w,e,dig,math) elementlarning o‘rin almashtirishlari soni),
 5!(we,d,i,g,math) elementlarning o‘rin almashtirishlari soni), (we,dig,math) elementlarning o‘rin almashtirishlari soni).

Demak, A₁ A₂ A₃  8! 7! 6! 6! 5! 4! 3!  45222 .
U holda, “we”,”dig”,”math” so‘zlarini o‘z ichiga olmagan barcha o‘rin
almashtirishlar soni 9! 45222  362880  45222  317658 .
Faraz qilaylik, qandaydir so‘zni tashkil qilgan belgilar orasida aynan bir xil

n₁ ta birinchi tur, bir xil
n₂ ta ikkinchi tur, va hokazo, bir xil
n_k ta
k - tur belgilar

bo‘lsin, bu yerda
n₁ ,
n₂ ,… n_k
– natural sonlar. Bu belgilarning o‘rinlarini

almashtirish natijasida hosil bo‘lgan so‘zlar takrorli o‘rin almashtirishlar
(anagrammalar) deb ataladi.

Barcha anagrammalar sonini
P(n₁, n₂ ,..., n_k )
bilan belgilasak, u uchun

P(n , n ,..., n
_{) } (n₁  n₂  ...  n_k )!

formula o‘rinlidir.

1 2 k
n₁ !n₂ !...n_k !

M isol .KOMBINATORIKA so‘zidan nechta anagramma tuzish mumkin?
Yechilishi.Bu so‘z ikkita K, ikkita O, bitta M, bitta B, ikkita I, bitta N, ikkita A, bitta T va bitta R harfidan tashkil topganligi bois, anagrammalar soni

P(2, 2,1,1, 2,1, 2,1,1) 
13!
_ 13!

ga teng.

2! 2! 2! 2! 16
Qiziqarli ma’lumot. Ayrim adabiyotlarda nafaqat so‘zlardan, balki so‘z birikmalari hamda gaplardan tashkil topgan anagrammalar qaraladi.
Anagrammalarni tuzish – tabiiy til so‘zlari hamda gaplari bilan kombinatorik mashqlarning qadimiy turi bo‘lib, unga 2000 yildan oshdi. Shunisi qiziqki ANAGRAMS so‘zining harflaridan ARS MAGNA – buyuk san’at (lot.) so‘z birikmasini tuzish mumkin.
Ma’lumki, fransuz qiroli Lyudovik o‘zining qarorgohida anagrammist lavozimini kiritib, uning yillik maoshini 1200 livr deb belgilagan.

Ayrim anagrammalar nafaqat ma’noga, balki dastlabki so‘zga (yoki so‘z birikmasiga ) qarama-qarshi ma’nodagi so‘zni (yoki so‘z birikmasini) tashkil qiladi.
Ulardan ayrimlarini keltiramiz:

1. 
   evils agents (jahannam elchilari) – evangelists (evangelistlar)
   
2. 
   real fun (katta xursandchilik) – funerals (dafn marosimi)
   
3. 
   no more stars (boshqa yulduzlar yo‘q) – astronomer (astronom)
   

Birikmalar.

Agar elementlar tartibi nazarda soqit qilinsa, shunday masala vujudga keladi: n elementli to‘plamdan nechta m elementli turli qism to‘plam ajratish mumkin? Bunday qism to‘plamlar n ta elementdan m tadan tuzilgan birikmalar deyiladi.
^{Uzunligi n ga teng bo‘lgan va tarkibida aynan m ta} a ^{harf bo‘lgan}

a...ab...b
m nm
ko‘rinishdagi so‘z bunday birikmani tashkil qiladi.

Birikmalar soni ^{Cm   n   n!} formulasi bilan hisoblanadi.

n  

m
 
m!(n  m)!

Misol. Ikkita unli va uchta undosh fonemadan iborat besh fonemali so‘zlar
soni

C ² 
5! _ 1 2  3  4  5 _{ 10}

ga teng

⁵ 2!3! 1 2 1 2  3


QIZIQARLI KOMBINATORIKA.
Bir qator amaliy masalalarni yechish uchun berilgan to’plamdan uning qandaydir xossaga ega bo’lgan elementlarini tanlab olish va ularni ma’lum bir tartibda joylashtirishga to’g’ri keladi.
Ta’rif. Biror chekli to’plam elementlari ichida ma’lum bir xossaga ega bo’lgan elementlaridan iborat qism to’plamlarni tanlab olish yoki to’plam elementlarini ma’lum bir tartibda joylashtirish bilan bog’liq masalalar kombinatorik masalalar deyiladi.
Masalan, o’nta ishchidan to’rt kishidan iborat brigadalarni necha xil usulda tuzish mumkinligini (ishlab chiqarishni tashkil etish), molekulada atomlar qanday usullarda birlashishi mumkinligi (kimyo), oqsil moddalarda aminokislotalarni qanday tartiblarda joylashtirish mumkinligi (biologiya), turli bloklardan iborat mexanizmda bu bloklarni turli tartiblarda birlashtirish (konstruktorlik), bir necha dala uchastkalarida turli xil ekinlarni almashtirib ekish (agronomiya), davlat budjetini ishlab chiqarish tarmoqlari bo’yicha taqsimoti (iqtisodiyot) kabilar kombinatorik masalalarga keladi va kombinatorikani inson faoliyatining turli yo’nalishlarida qo’llanishini ko’rsatadi.
Ta’rif. Kombinatorik masalalar bilan shug’ullanadigan matematik fan kombinatorika deyiladi.
Kombinatorikani mustaqil fan sifatida birinchi bo’lib olmon matematigi G.Leybnits o’rgangan va 1666 yilda “Kombinatorika san’ati haqida” asarini chop etgan.
Kombinatorikada qo’shish va ko’paytirish qoidasi deb ataluvchi ikkita asosiy qoida mavjud.

Qo’shish qoidasi. Agar biror  tanlovni  usulda,  tanlovni  usulda amalga oshirish mumkin bo’lsa va bu yerda  tanlovni ixtiyoriy tanlash usuli  tanlovni ixtiyoriy tanlash usulidan farq qilsa, u holda “ yoki  ” tanlovni amalga oshirish usullari soni  formuladan topiladi.

Ko’paytirish qoidasi. Agar biror  tanlovni  usulda,  tanlovni  usulda amalga oshirish mumkin bo’lsa, u holda “ va  ” tanlovni (yoki ( , ) juftlikni) amalga oshirish usullari soni  formuladan topiladi.
Kombinatorik masalalarni yechishda ko’p qo’llaniladigan tushunchalardan biri o’rin almashtirish tushunchasidir.
Ta’rif. Chekli va  ta elementdan iborat to’plamning barcha elementlarini faqat joylashish tartibini o’zgartirib qism to’plam hosil qilish   elementli o’rin almashtirish deb ataladi.
Berilgan  ta elementdan tashkil topadigan o’rin almashtirishlar soni  bilan belgilanadi.
Teorema.  ta elementdan iborat o’rin almashtirishlar soni  formula bilan hisoblanadi.
Bu yerda  – en faktorial deb o’qiladi va  kabi aniqlanadi. Bunda  deb olinadi. Masalan,  va hokazo. Faktoriallarni hisoblashda  tenglikdan foydalanish qulay bo’ladi. Masalan,  elementli  to’plamdan hosil bo’ladigan o’rin almashtirishlar  bo’lib, ularning soni  bo’ladi.
Kombinatorik tushunchalardan yana biri kombinatsiya tushunchasidir.
Ta’rif. Chekli va  ta elementli to’plamning  ta elementli va kamida bitta element bilan farqlanadigan qism to’plam hosil qilish   elementdan  ta olingan kombinatsiya deyiladi.
Masalan,  ko’rinishdagi  elementli to’plamdan ikkita elemenli kombinatsiyalar  bo’lib, ularning soni 3 tadir. Bu yerda  deb olinadi.

ta elementdan  tadan olingan kombinatsiyalar soni  kabi belgilanadi va uning qiymati  formula yordamida hisoblanadi.
Bu formula orqali kiritilgan  sonlar yordamida quyidagi tenglikni yozish mumkin:



Bu tenglikda  ixtiyoriy natural son bo’lib, u  va  qisqa ko’paytirish formulalarining umumlashmasini ifodalaydi va uni Nyuton binomi deb ataladi. Unga kiruvchi  sonlari binomial koeffitsentlar deb ataladi.
Agar Nyuton binomida  yoki  deb olsak, unda 
tengliklar o’rinli bo’ladi.
Agar formulada  o’rniga  qo’yilsa yoki  yoki  deb olinsa, unda  tengliklar hosil bo’ladi. Bular kombinatsiyalarni hisoblashni osonlashtiradi.
Kombinatorik masalalarni yechishda o’rinlashtirish deb ataluvchi tushunchadan ham foydalaniladi.
Ta’rif. Chekli va  ta elementdan iborat to’plamdan bir-biridan yoki elementlari yoki elementlarining joylashish tartibi bilan farq qiladigan va  ta elementdan iborat qism to’plamlarni hosil qilish   elementdan  tadan o’rinlashtirish deb ataladi.
Berilgan  ta elementdan  tadan o’rinlashtirishlar soni  kabi belgilanadi va uning qiymati


yoki  formula bilan hisoblanadi.
Masalan,  to’plamdan  elementdan  tadan o’rinlashtirishlar  bo’lib, ularning soni  yoki