Kombinatorika va ehtimollar nazariyasida raqamlash usuli

Kombinatorika va ehtimollar nazariyasida raqamlash usuli.
1-masala. Topologiya so’zidagi harflar o’rnini almashtirib, ikkita o harfi yonma-yon turmaydigan nechta so’z hosil qilish mumkin?
Yechilishi. Topologiya so’zi 10 harfdan iborat. Faraz qilaylik, harflar bir qatorga qo’yilgan 1 dan 10 gacha raqamlangan o’rindiqlarga joylashtirilgan. Masala shartiga ko’ra, uchta o harfidan ixtiyoriy ikkitasi yonma-yon turmaydigan, ya’ni ixtiyoriy ikkita o harfi joylashgan o’rindiqlar raqamlari ketma-ket kelgan sonlar bo’lmaydigan holda hosil qilish mumkin bo’lgan barcha so’zlar sonini topishimiz kerak. Qulaylik uchun 10 sonini A harfi orqali ifodalaymiz. O harflaridan biri 1-o’rindiqda ,ikkinchi o harfi 3-o’rindiqda , uchinchi o harfi 5-o’rindiqda bo’lsin. Bu holatni 135 kabi ifodalaymiz.O harflaridan biri 1-o’rindiqda bo’lganda quyidagi variantlar bo’lishi mumkin:
135, 136, 137, 138, 139, 13A
146, 147, 148, 149, 14A
157, 158, 159, 15A
168, 169, 16A
179, 17A
18A Jami 6+5+4+3+2+1.
Endi o harflaridan biri 2-o’rindiqda bo’lgan holatlarni ko’ramiz.
246, 247, 248, 249, 24A
257,258,259, 25A
268, 269, 26A
279, 27A
28A Jami 5+4+3+2+1.
Yuqoridagi ikkita holatda 6+5+4+3+2+1 va 5+4+3+2+1 yig’indilarga duch keldik. Mulohaza yuritishni shu tarzda davom ettirib, yoma-yon turgan ikkita raqami ketma-ket kelgan sonlar bo’lmaydigan barcha variantlar sonini hisoblash uchun quyidagi yig’indini hosil qilamiz:
(6+5+4+3+2+1)+(5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1=56.
Endi shu 56 ta variantning ixtiyoriy bittasini ko’rib chiqamiz. Masalan 135. Bu holatda o harflari 1,3,5 o’rindiqlarda O __ O __ O __ __ __ __ __ 2,4,6,7,8,9,10 o’rindiqlar bo’sh, ularga t,p,l,g,i,y,a harflarini 7!=5040 usul bilan joylashtirish mumkin. Bundan hosil qilish mumkin bo’lgan barcha so’zlar soni 56*7!=56*5040=282 240 ta ekanligi kelib chiqadi.
Shu yerda yechim oxiriga yetdi. Endi masalani yechishning 2-usulini ko’rib chiqamiz. Bu usul 1-usulda qo’llanilgan g’oyaga teskari g’oyaga asoslangan bo’lib, bu holat yechimni to’g’ri yoki noto’g’ri ekanligini baholash imkonini beradi.
2-usul. Ikkita o harfi yonma-yon kelganda hosil qilish mumkin bo’lgan barcha barcha so’zlar sonini hisoblaymiz. O harflaridan ikkitasi 1-2 o’rindiqlarda bo’lganda quyidagi holatlar yuzaga kelishi mumkin:
123, 124, 125, 126, 127, 128, 129, 12A
O harflaridan ikkitasi 2-3 o’rindiqlarda bo’lganda
234, 235,236, 237, 238, 239 23A
3-4 o’rindiqlarda bo’lganda
134,(bu yerda 234 varianti kiritilmaydi, chunki bu variant avvalgi holatda ko’rilgan), 345, 345, 347, 348, 349, 34A
4-5 o’rindiqlarda bo’lganda
145, 245, 456, 457, 458, 459, 45A
Faqat 1-holatda, ya’ni ikkita o harfi 1-2 o’rindiqlarda bo’lgan holatda 8 ta, qolgan holatlarning har birida 7 tadan. Chiqarilgan xulosalarga qat’iy ishonch hosil qilish uchun 9-A , ya’ni ikkita o harfi 9 va 10-o’rinlarda bo’lgan holatni qaraymiz.
19A, 29A, 39A, 49A, 59A, 69A, 79A (bu holatda 89A varianti qaralmaydi, chunki bu variant 8-9 holatda hisobga olingan)
1-2, 2-3, 3-4, 4-5, 5-6, 6-7, 7-8, 8-9, 9-A kabi holatlar 9 ta, ularning bittasida 8 ta, qolganlarining har birida 7 tadan variant mavjud. Barcha variantlar soni 8+8*7=64. Bu variantlarning ixtiyoriy bittasini ko’rib chiqamiz, masalan, 145. Bu yerda 1,4,5 o’rindiqlarda o harflari, qolgan o’rindiqlarda t,p,l,g,i,y,a harflari joylashgan. O harflari qo’zg’almaydi qolgan 7 ta harfni 7!=5040 usul bilan joylarini almashtirib, 5040 ta turli so’z hosil qilish mumkin. Yuqorida keltirib chiqarilgan 64 ta holatning har birida 5040 tadan turli so’zlarni hosil qilish mumkin. Barcha hosil qilish mumkin bo’lgan so’zlar soni 64*5040=322 560 ta. Endi topologiya so’zidagi harflar o’rinlarini almashtirib nechta turli so’z hosil qilish mumkinligini hisoblaymiz. Takrorlanishlar mumkin bo’lgan holatda guruhlashlar sonini hisoblash formulasiga ko’ra izlanayotgan son ga teng. Ikkita o harfi yonma-yon turmaydigan holatda hosil qilish mumkin bo’lgan barcha so’zlar soni
604 800-322 560=282 240 ga teng.
Masalani ikkita bir-birini to’ldiruvchi usullar yordamida ishlab, bir xil natijani keltirib chiqardik, bu holat yechimda keltirilgan mulohazalarning to’g’ri ekanligini ko’rsatadi.
2-masala. 2 ta satr, 10 ta ustunga ega bo’lgan jadval berilgan. Ali 1-satrga , Vali 2-satrga yozadi. Ali 1-satrga 6 ta 1, 4ta 0 , Vali 2-satrga 8 ta 1, 2 ta 0 yozishi mumkin. Nechta holatda bir ustunning ikkita elementi ham 0 bo’lishi mumkin?
Yechilishi.1-usul. Faraz qilaylik, Ali 7,8,9,10-ustunlarga, Vali 6,7 ustunlarga 0 yozdi. Bu jadvalda quyidagicha aks etadi:

1	1	1	1	1	1	0	0	0	0
1	1	1	1	1	0	0	1	1	1

Yoki Ali 3,5,7,9, Vali 1,5-ustunlarga 0 raqamini yozdi:

1	1	0	1	0	1	0	1	0	1
0	1	1	1	0	1	1	1	1	1

Ali 6 ta 1, 4ta 0 ni 1-satrga usul bilan, Vali 8 ta 1, 2 ta 0 ni 2-satrga usul bilan yozishi mumkin. Jadvalning barcha turli ko’rinishlari soni 210*45=9450 ta. Agar turli ko’rinishdagi barcha jadvallar bir qatorga joylashtirilsa, 94500 ta ustunga, 2 ta satrga ega bo’lgan jadval hosil bo’ladi. Shu ustunlarning nechtasida ikkita element 0 bo’lishini aniqlashimiz kerak. Ali 0 larni 1,2,3,4 ustunlarga yozgan bo’lsin. Vali hosil qilishi mumkin bo’lgan 45 xil ko’rinishdagi satrlarnung har birining yuqorisiga Ali 0 larni 1,2,3,4 ustunlarga yozgan satrni yozib chiqamiz. Faraz qilaylik, bu satrlarning birida 1,2 ustunlarga 0 raqami yozilgan bo’lsin. Bu holatni 12 kabi tasvirlaymiz. Hisoblash qulay bo’lishi uchun 10 sonining o’rniga A harfidan foydalanamiz, masalan 0 lar 9,10 ustunlarga yozilgan bo’lsa buni 9A kabi ifodalaymiz. Bu 45 xil ko’rinishdagi satrlarda ikkita 0 raqami quyidagi o’rinlarda bo’lishi mumkin:

12,13,14,15,16,17,18,19,1A,23,24,25,26,27,28,29,2A,34,35,36,37,38,39,3A,45,46,47, 48,49,4A,56,57,58,59,5A,67,68,69,6A,78,79,7A,89,8A,9A .
Yuqoridagi satrning 1,2,3,4 ustunlarida 0 raqami turganligi uchun, yuqoridagi sonli ketma-ketlikda necha marta 1,2,3,4 raqamlari borligini sanaymiz va bu raqamlar 36 ta ekanligini ko’ramiz.
Faraz qilaylik, Ali 0 raqamlarini 2,4,7,9-ustunlarga yozgan bo’lsin. Yuqorida yozilgan sonli qatorda 2,4,7,9 raqamlari 36 marta uchraydi. Ali to’rtta 0 ni qaysi ustunlarga yozsa ham, har bir 45 talikda ikkita elementi ham 0 bo’lgan ustunlar 36 ta bo’ladi. Bundan izlanayotgan son 210*36=7560 ta ekanligi kelib chiqadi.
2-usul. Faraz qilaylik, Ali bilan Vali nishonga qarata o’q otmoqda o’qning nishonga tegishi 1, nishonga tegmasligi 0. Masala shartiga ko’ra Alining o’qni nishonga tekkizish ehtimoli 0,6 ga, Valiniki 0,8 ga teng. Ikkalasining ham o’qni nishonga tekkiza olmasligi ikkita elementi ham 0 bo’lgan ustun ko’rinishida ifodalanadi. Demak, Ali bilan Valining o’qni nishonga tekkiza olmaslik ehtimolini topishimiz kerak. Bu ehtimollik 0,4*0,2=0,08 ga teng.
Masalani 1-usulda ishlash jarayonida Ali bilan Vali jadvalni 9450 usulda to’ldirishi mumkinligini aniqlagan edik. Agar bunday turli xil ko’rinishdagi jadvallar yonma-yon yozilsa, 94500 ta ustundan iborat jadval hosil bo’ladi. Yuqorida hisoblaganimizga ko’ra barcha ustunlarning 0,08 qismida ikkita elementi 0 ga teng. Bunday ustunlar soni 94500*0,08=7560
3-masala. Kemaga qarata uchta to’pdan o’q uzilmoqda.1-to’pning nishonga tekkizish ehtimoli 0,6 ga, ikkinchisiniki 0,7ga , uchinchisiniki 0,5 ga teng. Agar bitta o’q nishonga tegsa, kemaning cho’kish ehtimoli 0,5ga, ikkita o’q tegsa 0,8ga, uchta o’q tegsa 1 ga teng.