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 kelmaydigan nechta so’z hosil qilish mumkin?
Yechilishi. Topoogiya so’zi 10 ta harfdan iborat so’z bo’lib, bu so’zda 3 ta o harfi bor, qolgan harflar turlicha. Topologiya so’zidagi harflar joylashishi kerak bo’lgan o’rinlarni raqamlaymiz. Bunda qulay bo’lishi uchun 10 sonini a raqamiga almashtiramiz. Topologiya so’zidagi harflar 1,2,3,4,5,6,7,8,9,a o’rinlarga joylashadi. Har bir turli variantni quyidagi usul bilan uch xonali sonlar ko’rinishida ifodalaymiz: agar o harflari 1,2,3 o’rinlarda joylashgan bo’lsa, 123 soni hosil bo’ladi, agar o harflari 5,7,9 o’rinlarga joylashgan bo’lsa, 579 soni hosil bo’ladi. Biz masala shartiga ko’ra yuqorida bayon qilingan usul bilan hosil qilish mumkin bo’lgan, raqamlari ketma-ket kelgan sonlar bo’lmaydigan uch xonali sonlar nechta ekanligini hisoblashimiz kerak. Dastlab birinchi raqami 1 bo’lgan sonlar sonini hisoblaymiz.
135, 136, 137, 138, 139, 13a
146, 147, 148, 149, 14a
157, 158, 159, 15a
168, 169, 16a
179, 17a
18a
Birinchi raqami 2 bo’lgan sonlar sonini hisoblaymiz.
246, 247, 248, 249, 24a
257, 258, 259, 25a
268, 269, 26a
279, 27a
28a
Yuqoridagilarga ko’ra, raqamlari ketma-ket kelgan sonlar bo’lmaydigan barcha sonlar sonini hisoblash uchun quyidagi ifodani hosil qilamiz.
=
Hosil bo’lgan yig’indining qiymati 56 ga teng. Bu 56 ta variantning har birida qolgan 7 ta harfni 7ta o’ringa 7 usul bilan joylashtirish mumkin. Bundan izlanayotgan usullar soni 56*7 =282240 ta ekanligi kelib chiqadi.
Endi yuqorida keltirib chiqarilgan usuldan umumiyroq bo’lgan masalani yechishda foydalanamiz.
2-masala. n ta harfdan iborat so’zning uchta harfi bir xil, qolgan harflari turlicha. Ikkita bir xil harf yonma-yon kelmaydigan qilib nechta turli so’z hosil qilish mumkin?
Yechilishi. 1-masala yechimida keltirilgan usuldan foydalanib, quyidagi yig’indini hosil qilamiz:

=

Qolgan n-3 ta turli harflarni har bir holatda (n-3) usul bilan qolgan o’rinlarga joylashtirish mumkin. Bundan masala shartida bayon qilingan usul bilan hosil qilish mumkin bo’lgan so’zlar soni quyidagiga tengligi kelib chiqadi:

3-masala. n ta harfdan iborat so’zning to’rtta harfi bir xil, qolganlari turli harflar. Ikkita bir xil harf yonma-yon kelmaydigan nechta so’z hosil qilish mumkin?
Yechilishi. Agar bir xil harflardan uchtasini 1,3,5-o’rinlarga joylashtirsak, bir xil harflarning to’rtinchisini 6 ta o’ringa joylashtira olmaymiz. To’rtinchi harfni joylashtirish uchun n-6 ta o’rin qoladi. Shuning uchun bir xil harflarning biri birinchi o’ringa joylashtirilganda bizga kerakli variantlar soni
ga teng.
Bir xil harflarning biri ikkinchi o’rinda bo’lganda, bir xil harflarni joylashtirish uchun bitta o’rin ya’ni birinchi o’rin yo’qoladi. Yuqoridagi ishni n ta xona uchun amalga oshirgan bo’lsak, bu holatda n-1 xona uchun amalga oshirish yetarli.

Hosil qilish mumkin bo’lgan barcha so’zlar sonini hisoblash uchun quyidagi yig’indiga ega bo’lamiz:
=
Bu holatlarning har birida qolgan n-4 ta turli harfni qolgan o’rinlarga (n-4)! usul bilan joylashtirish mumkin. Bunga ko’ra izlanayotgan so’zlar soni
ga tengligi kelib chiqadi.
2-masalada n 4 dan, 3-masalada 7 dan kichik bo’lishi mumkin emas, aks holda bir xil harflarni yonma-yon kelmaydigan qilib joylashtirishning imkoniyati yo’q.
Yuqoridagi masalalarning yechimlaridan quyidagilar kelib chiqadi:
1) bir xil harflar soni 5 ta bo’lganda, ularni ikkita bir xil harf yonma-yon kelmaydigan qilib joylashtirilgan variantlari soni quyidagiga teng:

2) ayrim yig’indilar uchun quyidagi tengliklarni yoza olamiz

Endi n ta harfli so’zning m ta harfi bir xil bo’ganda bir xil harflar yonma-yon kelmaydigan qilib hosil qilish mumkin bo’lgan so’zlar soni

ga teng bo’lishini matematik induksiya prinsipi yordamida isbotlaymiz. m=3 bo’lgan holatda formulaning o’rinli ekanligini yuqorida ko’rdik. m=k holat uchun

formulani to’g’ri deb hisoblaymiz va m=k+1 holat uchun

formulaning to’g’ri ekanligini isbotlaymiz.
Faraz qilaylik, bir xil harflardan biri hosil qilinishi kerak bo’lgan so’zning birinchi harfi, u holda qolgan k ta harfni masala shartiga ko’ra n-2 ta o’ringa joylashtirishimiz kerak. Buni

usul yordamida amalga oshirishimiz mumkin. Agar birinchi o’rinda turgan harfni bir pozitsiya o’ngga kochirsak, u holda qolgan k ta harfni


ta usul bilan n-3 ta o’ringa joylashtirishimiz mumkin. Barcha hosil qilish mumkin bo’lgan variantlar sonini topish uchun quyidagi yig’indini hosil qilamiz:
=


=

= =
=
=
=
=…=
Da’vo isbotlandi.