Guliston davlat universiteti

2.3-§. Ayrim kombinatorik masalalarni yechishda traektoriya metodining tadbiqlari.

3.1-misol: (Shaxmat shaharchasi )

m n oʻlchamli toʻgʻri burchakli toʻrni qaraymiz .Bu toʻr m n toʻgʻri burchakli kvartallardan iborat boʻlib , u n-1 ta “gorizontal” va m-1 ta “vertikal koʻchalar ” ga boʻlingan.(3-rasm).
Chap quyi burchaklardan va ((0;0) nuqtalar ) oʻng yuqori burchakka ((m;n) nuqtaga) olib boruvchi turli qisqa yoʻlning soni qanday ?
Yechish (0;0) nuqtadan (m;n) nuqtagacha har bir qisqa yoʻl m+n kesmalardan iborat boʻlib , jumladan ularning m tasi gorizontal, n tasi vertikal kesmalar boʻladi.
Turli yoʻllar faqat gorizontal va vertical kesmalarning oʻrni almashishi bilangina farqlanadi . Shuning uchun ham umumiy yoʻllar soni n+m kesmalardan n ta vertical kesmalarni tanlash usuliga bogʻliq boʻladi va bu ajratib olishlar soni ya’ni .
Xuddi shunday bu tanlash usullarini m ta gorizontal olishimiz mumkin , ya’ni
.
Quyidagi tenglikning oʻrinli ekanligini kombinatsiyalar sonini faktariallar orqali ham ifodalash mumkin .
= .
Shunday qilib (0;0) nuqtadan (m;n) nuqtagacha qisqa yoʻllarning soni
=
ga teng .
3.1-teorema: (3.1)
tenglama oʻrinlidir.
Isbot: O(0;0) nuqtadan A(k;n-k) nuqtaga qisqacha yoʻl soni ga teng.(4-rasm)
Barcha bunday yoʻllarni ikki gruppaga boʻlish mukin :
A (k-1;n-1) nuqta orqali oʻtuvchi yoʻllar (ular soni ga teng) va nuqta orqali oʻtuvchi yoʻllar (ular soni ga teng ).
Bundan
tenglik oʻrinli ekanligi kelib chiqadi.
3.2-misol: Bizta chipta sotish bilan bogʻliq boʻlgan masalaning yechimini isbotlangan teorema yordamida keltiramiz. Tushnarli boʻlishi uchun masala shartini keltiramiz:
A nomzod saylovda a ovoz toʻpladi, B nomzod b ovoz toʻpladi ( a>b) saylovchilar ketma- ket ovoz berdilar .
Hamma vaqt A nomzod berilgan ovozlar boʻyicha B nomzoddan oldinda boʻlishini ta’minlovchi ovoz berish hollari nechita?
Yechish:Masalaning berilishidan koʻrinadiki, masalani yechish O nuqtadan (m+n;n-m) nuqtaga
y=-(p+1)
Toʻgʻri chiziq bilan kesishmaydigan traektoriyalar sonini hisoblashga olib kelinadi.2.2-teoremaga asosan y=-(p+1) toʻgʻri chiziq bilan kesishadigan traektoriyalar soni (0;-2(p+1)) nuqtadan (n+m;n-m) nuqtaga traektoriyalar soniga, ya’ni

ga teng boʻladi.
Demak , izlanayotgan traektoriyalar soni

ga teng boʻladi.
2.bobning xulosasi: Bu bobda asosan biz traektoriyalar metodi deb ataluvchi usul haqida tushunchalar berib, u bilan bogʻliq boʻlgan teoremalar keltirildi. Ayrim kombinatorik munosabatlarni shu usul bilan keltirildi. Bu usulning muhim tomoni ,uning koʻrgazmaligidir.Bitiruv malakaviy ishida keltirilgan ma’lumotlardan akademik litsey va kollejlarda algebra va analiz darsini oʻtish jarayonida va oliy oʻquv yurtlarida algebra , ehtimollar nazariyasi va matematik statistika fanlarini oʻqitishda foydalanish mumkin. Bu bobda uchta paragraf bor. 1- traektoriyalar usuli haqida .2-traektoriyalar usuli yordamida ayrim kombinatorik munosabatlarni isbotlash. 3- Ayrim kombinatorik masalalarni yechishda tadbiqlari.

0

m

(m;0)

n

(0;n)


B

D

0

y










XULOSA
Bitiruv malakaviy ishida ayrim kombinatorik munosabatlar, ularning isbotlari hamda bu munosabatlarni traektoriya metodi yordamida koʻrgazmali isboti haqida ma’lumotlar berilgan.
Bitiruv malakaviy ishining birinchi qismi bu ayrim muhim kombinatorik munosabatlar va tushunchalar haqida. Bu qismda toʻplamning toʻplam ostilari ta’rifi, shu mavzuga doir teoremalar, har- xil misollarning yechimi keltirilgan.Bundan tashqari 2 ta natija ham bor. Bu bitiruv malakaviy ishining asosiy boshlangʻich masalalaridan hisoblanadi.
Bitiruv malakaviy ishining ikkinchi qismi bu Tartiblangan toʻplamlar. Oʻrin almashtirish va joylashtirish.Bu qismda tartiblangan toʻplamlar haqida ta’rif, teoremalar keltirilgan.Hamma shu mavzuga doir misollar yechimlari bilan keltirilgan.
1 bobning 3 qismi Takrorlanadigan oʻrin almashtirishlar. Bu qismda ham teoremalar isboti, misollar yechimlari bilan keltirilgan.
2 bobda ham 3 ta paragraf mavjud boʻlib, 1-qismi traektoriyalar usuli haqida.2- qismi traektoriyalar usuli yordamida ayrim kominatorik munosabatlarni isbotlash.3- qismi.Ayrim kombinatorik masalalarni yechishda traektoriya metodining tadbiqlari.
Koʻpgina kombinatorika topshiriqlar uchun shunday geometrik talqinni koʻrsatish mumkinki, aniq xossaga ega boʻlgan yoʻllarning (traektoriyaning) sonini hisoblashga oid masalaga keltiriladi. Bu metoddan ayrim binomial ayniyatlarni isbotida foydalanish mumkin. Bu metodning ustunligi favqulodda koʻrgazmalilik hisoblanadi.
Traektoriya metodi atamasini B.V .Gnedenko kiritgan.1951-1954 yillarda B.V.Gnedenko va uning shogirdlari V.S.Korolyuk,V.S.Mixalevich bu metodni matematik statistikaning ayrim muhim masalalarni yechishda qoʻllaganlar.
Ishning asosiy qismi shu kombinatorik masalalarning traektoriya metodi yordamida isbotini, ya’ni geometriktalqini berishdan iborat.