Muhammad Al-Xorazmiy nomidagi Toshkent axborot texnalogiyalari universiteti Farg’ona filiali
DISKRET-TUZULMALARI
FANIDAN REFERAT
Fakultet: Kompiyuter-injinering
Yunalish: At-Servis
Guruh: 681-23
Bajardi: Mirzoaliev Azizjon
Qabul qildi: Nasridinov O
Farg’ona 2024
Mavzu: Kombinatorikaning asosiy qoidalari.
Takroriy bo'lmagan o'rinlashtirish, o'rin almashtirish va guruhlashlar
Reja:
1. Kombinatorikaning asosiy qoidalari.
2. Takroriy bulmagan urinishlar.
3. O’rin almashtirishlar va guruhlashlar.
4. Takrorlanmaydigan joylashtirishlar.
Kirish. Kombinatorika-diskret matematikaning bulimlaridan biri bulib, ehtimollar nazariyasi, matematik mntiq, sonlar nazariyasi, hisoblash texnikasi va kibernetikada kup qullanillgani uchun muhim ahamiyatga ega buldi. Insoniyat juda ko’p qo’llanilgani ushun muhim ahamiyatga ega bo’ldi. Insoniyat juda ko’p marotaba ayrim predmetlarni barcha joylashtirish usullari sonini sanab chiqish yoki biror bir harakatni amalga oshirishdagi barcha mavjud usullar sonini aniqlash kabi masalalarga duch keladi.
Masalan: 50 kishini kassadagi navbatga necha xil usulda joylashtirish mumkin? Futbol bo’yicha jahon chempiyonatida necha xil usulda oltin, kumush, bronza medallarini taqsimlash mumkin. Bunday tipdagi masalalar kombinator masalalar deyiladi.
Kombinatorika masalalarini yechish asosiy ikki turga bo’linadi:
a. qism to’plamlarni tanlashga ko’ra;
b. elementlar tartibga ko’ra.
Qism to`plamlarni tanlash usuli tanlanma tushunchasi bilan bog`liq.
Ta`rif 1. elementli to`plamdan elementli qism to`plam ajratib olish tanlanma deyiladi, bunda - tanlanma hajmi deyiladi.
Ajratilgan qism to‘plamning har bir elementi bilan 1 dan n gacha bo`lgan sonlar o`rtasida bir qiymatli moslik o`rnatilgan bo‘lsa, to‘plam tartiblangan tanlanma, aksincha tartiblanmagan deyiladi.
Agar to‘plam elementlaridan biror bir ro‘yxat tuzib, keyin har bir elementga ro‘yxatda turgan joy raqami mos qo‘yilsa, har qanday chekli to‘plamni tartiblash mumkin. Bundan ko`rinadiki, bittadan ortiq elementi bo`lgan to‘plamni bir nechta usul bilan tartiblash mumkin. Agar tartiblangan to`plamlar elementlari bilan farq qilsa, yoki ularning tartibi bilan farq qilsa, ular turlicha deb hisoblanadi.
Kombinatorikaning asosiy masalalaridan biri bu turli shartlarga ko`ra chekli to’plamda elementlar sonini aniqlash masalasidir.
To’plam elementlari sonini topish kombinatorikaning ikkita yangi printsipi: yig’indi va ko’paytma qoidalari asosida amalga oshiriladi.
Yig`indi qoidasi
Ta`rif. Agar to`plamdan qism to`plamni usul bilan tanlash mumkin bo`lsa, undan farqli boshqa qism to`plamni usulda tanlash
mumkin bo`lsa va bunda va larni bir vaqtda tanlash mumkin bo`lmasa, u holda to`plamdan tanlanmani usulda olish mumkin.
Agar bo’lsa, u holda va to’plamlar kesishmaydigan to’plamlar deyiladi.
Xususiy holda, agar barcha lar uchun bo’lsa, u holda to’plam to’plamning o’zaro kesishmaydigan qism to’plamlari yoki oddiygina qilib bo’laklari deyiladi. Demak, yig’indi qoidasida va lar to’plamning bo’laklaridir.
Misol. 212-19 guruh talabalari 16 nafar yigit va 8 nafar qizlardan iborat bo’lib, ular orasidan bir kishini ajratib olish kerak bo`lsa, ularning soni qo’shiladi va 16+8=24 talaba orasidan tanlab olinadi.
Ko`paytma qoidasi
Ta`rif. Agar to`plamdan tanlanmani usulda va har bir usulda mos tanlanmani usulda amalgam oshirish mumkin bo`lsa, u holda va tanlanmani ko`rsatilgan tartibda usulda amalga oshirish mumkin. To’plamlar nazariyasi nuqtai nazaridan qaraydigan bo’lsak, bu qoida to’plamlarning Dekart ko’paytmasi tushunchasiga mos keladi. Kombinator hisoblashlarda ko‘p qo‘llaniladigan juda muhim qoidani o‘rnataylik.
1-masala. Samarqanddan Toshkentga samolyot, avtobus, poyezdda yetib borish mumkin; Toshkentdan Chirchiqqa esa avtobus yoki elektrichkada borish mumkin. Samarqand - Toshkent – Chirchiq yo‘nalishi bo‘yicha necha xil usulda sayoxat uyushtirish mumkin.
Y echilishi: Tushunarliki Samarqanddan Chirchiqqacha borish usullari ga teng, chunki Samarqanddan Toshkentgacha 3 xil borish usullariga, Toshkentdan Chiqchiqqacha 2 xil borish usullari mos keladi. Ushbu mulohazalar quyidagi kombinatorikaning asosiy qoidasi deb nomlanadigan sodda tasdiqni isbotlaydi. Kombinatorikaning 1-qoidasi: Agar qandaydir A tanlashni m usul bilan, bu usullarning har biriga biror bir boshqa B tanlashni n usulda amalga oshirish mumkin bo‘lsa, u holda A va B tanlashni (ko‘rsatilgan tartibda) usulda amalga oshirish mumkin.
2-masala. Futbol bo‘yicha mamlakat chempionatida 18 ta komanda qatnashadi. Necha xil usulda oltin va kumush medallar taqsimlanishi mumkin?
Yechilishi: Oltin medalni 18 ta komandadan biri egallashi mumkin. Oltin medal sohibi aniqlangandan keyin, kumush medalni qolgan 17 ta komandani biri egallashi mumkin. Demak oltin va kumush medallarni xil usulda taqsimlash mumkin. Endi kombinatorikaning asosiy qoidasini (ko‘paytirish formulasini) umumiy holda keltiramiz. Aytaylik birin-ketin k ta harakatni amalga oshirish talab qilngan bo‘lsin. Agar birinchi harakatni - n1 usulda, ikkinchi harakatni - n2 usulda, va hokazo k – harakatni - nk usulda amalga oshirish mumkin bo‘lsa, u holda barcha k ta harakatni usulda amalga oshirish mumkin bo‘ladi. Misol 1. Ikkinchi bosqich talabalari III semestrda 12 ta fanni o`rganishadi. Seshanba kuniga 3 ta turli fanni nechta usulda dars jadvaliga joylash mumkin? Bu misolda 12 ta fanni takrorlamasdan 3 tasini joylashtirish kerak. Buning uchun birinchi fanni 12 usulda, ikkinchi fanni 11 usulda va uchinchi fanni 10 ta usulda tanlash mumkin. Ko`paytirish qoidasiga asosan.
Demak, 3 ta turli fanni 1320 usulda joylash mumkin ekan.
Diskret struktura fanidan talabalar o`rtasida bo`ladigan olimpiadaning mamlakat bosqichida 16 nafar talaba qatnashmoqda. Necha xil usulda I, II va III o`rinlar taqsimlanishi mumkin?
Yechilishi: I o`rinni 16 talabadan biri egallashi mumkin. I o`rin sohibi aniqlangandan keyin, II o`rinni qolgan 15 talabadan biri egallaydi va nihoyat III o`rin qolgan 14 talabadan biriga nasib qiladi. Demak I, II va III o`rin g`oliblarini xil usulda aniqlash mumkin.
Misol 3. 5 soniga bo`linadigan 4 xonali sonlar nechta?
Yechilishi: Masalada takrorlanuvchi joylashtirish haqida so`z bormoqda. Birinchi xonaga to`plamning 10 ta elementidan bittasini tanlash mumkin, lekin 0 ni birinchi xonaga qo`yish mumkin emas, aks holda son 3 xonali bo`lib qoladi. Bo`linish belgisiga ko`ra son 5 ga bo`linishi uchun 0 yoki 5 bilan tugashi kerak.
Demak, 1- xona raqami uchun 9 ta tanlash mavjud;
2- va 3- xona raqamlari uchun esa 10 ta tanlash usuli bor;
4- xona, ya`ni oxirgi raqam uchun 0 yoki 5 raqamlari bo`lib, 2 ta tanlash mavjud. U holda ko`paytirish qoidasidan foydalansak, ta 5 ga bo`linadigan 4 xonali son borligini aniqlaymiz. Agar biror m murakkab son berilgan bo’lsa, uning bo‘luvchilar sonini topish uchun oldin tub sonlar ko’paytmasi shakliga keltiriladi: bunda p1, p2,...., pn – tub sonlar, daraja ko’rsatkichlari bo’lib, m murakkab sonning bo‘luvchilari soniga teng bo’ladi. soni nechta turli bo‘luvchilarga ega?
Yechilishi: ta umumiy bo‘luvchiga ega; son esa ta bo‘luvchiga ega.
Misol. 48 sonining bo’luvchilari sonini topish uchun ni topamiz.
U holda 48 ning bo‘luvchilari soni ekanligi topiladi. Guruhlash, joylashtirish va o‘rin almashtirishlar
Ta`rif. Agar tanlangan qism to`plamda elementlar tartibi ahamiyatsiz bo`lsa, u holda tanlanmalarga guruhlash deyiladi va
ko`rinishida belgilanadi. C – inglizcha “combination”, ya`ni “guruhlash” so`zining bosh harfidan olingan. Tanlanmalarda elementlar takrorlanishi va takrorlanmasligi mumkin. Ta`rif 5. Agar tartiblangan tanlanmalarda elementlar o`zaro turlicha bo`lsa, u holda takrorlanmaydigan joylashtirish deyiladi va kabi belgilanadi.
Ta`rif 6. tadan ta tartiblangan tanlanmaga o`rin almashtirish deyiladi va kabi belgilanadi. O`rin almashtirish joylashtirishning xususiy xoli hisoblanadi.
P inglizcha “permutation” – “o`rin almashtirish” so`zining bosh harfidan olingan.
Misol. to`plamning 3 ta elementdan 2 tadan barcha tartiblangan va tartiblanmagan, takrorlanmaydigan tanlanmalarini ko`rsating.
1) =6 ta takrorlanmaydigan joylashtirish;
2) ta takrorlanmaydigan guruhlash.
Takrorlanmaydigan guruhlashlar
Bizga tartiblanmagan takrorlanmaydigan ta elementi bo`lgan to‘plam berilgan bo`lsin. bilan ni taqqoslaymiz. Bilamizki, ta elementni ta usulda tartiblash mumkin, ya` ni bo`ladi. Bundan kelib chiqadi.
Misol 1. Har uchtasi bir to’g’ri chiziqda yotmagan n ta nuqta berilgan. Nuqtalarni ikkitalab tutashtirish natijasida nechta kesma o’tkazish mumkin?
Yechilishi: Masala shartiga ko’ra chizmada qavariq n burchak hosil bo’ladi. U holda 1-nuqta (n-1) ta nuqta bilan, 2-nuqta (n-2) ta nuqta bilan va h.k., (n-1) – nuqta 1 ta nuqta bilan tutashtiriladi. Bunda hosil bo’lgan to’g’ri chiziqlar soni
ga teng bo’ladi.
Misol 2. Restoranida 7 ta asosiy taomdan 3 tasini tanlash imkoniyati berilsa, nechta usulda buyurtma qilish mumkin?
Yechilishi: Bu misolda takrorlanmaydigan 7 ta elementdan 3 tadan guruhlashni topish kerak:
Misol 3. Sportloto lotareya o’yinida 36 ta natural sondan 6 tasini topgan kishi asosiy yutuqqa ega bo’ladi. Asosiy yutuqni olish imkoniyati qanday?
Yechilishi: Yutuq raqamlar oltitaligi 36 tadan 6 ta takrorlanmaydigan guruhlashga teng:
Misolning javobidan ko’rinadiki, asosiy yutiqni olish imkoniyati judayam kam, ya’ni 1 947 792 tadan 1 taga teng.
5, 4, va 3 ta raqamni topgan kishilarga ham yutuq beriladi, lekin bu yutuq shu kishilar o’rtasida teng taqsimlanadi. Bu holda 2 xil guruhlash mavjud, biri omadli tanlov va ikkinchisi omadsiz tanlov. U holda 3 ta raqamni topgan yutuq egalari imkoniyati:
Yutuqli bo’lish ehtimoli ga teng.
Teorema. ta elementi bo`lgan to‘plamning barcha tartiblanmagan elementli qism to‘plamlari soni
ga teng.
Guruhlashning xossalari
10.
20.
30.
Ushbu xossalarni isbotlash uchun kombinatsiyalarni faktorial ko’rinishida yozib chiqish va hisoblash yetarli.
Teorema. elementli to‘plamning barcha qism to‘plamari soni ga teng va quyidagi tenglik o‘rinli:
Haqiqatdan ham, - elementli to‘plamning barcha elementli to‘plam ostilari soni bo‘lgani uchun, tushunarliki barcha to‘plam ostilar soni
yig‘indiga teng bo‘lib, ularning yig‘indisi ga teng bo‘ladi.
Misol. 30 ta talabadan 20 tasi o‘g‘il bolalar, tavakkaliga jurnaldagi ro’yhat bo‘yicha 5 talaba chaqirildi, ularning ichida ko‘pi bilan 3 tasi o‘g‘il bola bo‘ladigan qilib necha xil usulda tanlash mumkin?
Yechilishi: Masala shartida berilgan to‘plamni sodda to‘plamlar
yig‘indisi shaklida yozib olamiz:
A={0 tasi o‘g‘il bola, 5 tasi qiz bola}
B={1 tasi o‘g‘il bola, 4 tasi qiz bola }
C={2 tasi o‘g‘il bola, 3 tasi qiz bola }
D={3 tasi o‘g‘il bola, 2 tasi qiz bola }
{Ko‘pi bilan 3 tasi o‘g‘il bola}=A B C D kesishmaydigan to‘plamlar yig‘indisining quvvati, ushbu to‘plamlar quvvatlari yig‘indisiga teng bo‘ladi:
n({ko‘pi bilan 3 tasi o‘g‘il bola})=n(A B C D)=n(A)+n(B)+n(C)+n(D)=
= + + + = +
Demak, 30 ta talabadan ko‘pi bilan 3 tasi o‘g‘il bola bo‘ladigan 26.478.900 tanlash usuli mavjud.
Takrorlanmaydigan joylashtirishlar
Avvalo barcha mumkin bo`lgan joylashtirishlarni topib olamiz. Bu masalani yechish uchun ko`paytma qoidasidan foydalanamiz.
ta elementi bo`lgan to‘plamda birinchi elementni tanlash uchun ta imkoniyat bor, ikkinchi elementni tanlash uchun esa ta imkoniyat qoladi. Joylashtirish takrorlanmaydigan bo`lgani uchun tanlab olingan element keyingi tanlanmalarda ishtirok etmaydi. Shuning uchun - elementni tanlash uchun imkoniyat qoladi. U holda barcha takrorlanmaydigan joylashtirishlar soniga teng bo`ladi.
Bu formulani boshqacha ko`rinishda yozish mumkin:
Bu yerda “!” belgisi faktorial deb o`qiladi. 1 dan gacha bo`lgan barcha natural sonlar ko`paytmasi ga teng. Faktorialni hisoblashda 0!=1 va 1!=1 deb qabul qilingan. Teorema. elementga ega bo`lgan to`plamning elementli tartiblangan takrorlanmaydigan qism to`plamlari soniga teng.
Misol 1. 7 kishidan iborat nazorat guruhini 4 nafar a`zosi bo`lgan nechta kichik guruhlarga ajratish mumkin?
Izlanayotgan usullar soni 7 ta elementdan 4 tadan joylashtirishlar soniga teng, ya`ni
Misol 2. Talaba 3 ta imtixonni bir hafta davomida topshirishi kerak. Bu harakatni necha xil usulda amalga oshirish mumkin?
Javob:
Shu o‘rinda eslatib o‘tamiz, tadqiqotlarda joylashtirishlar sonini hisoblashga to‘g‘ri kelsa, unda Excel dasturlar paketidagi ПЕРЕСТ komandasidan foydalanish mumkin,
masalan =859541760 ni hisoblang:
Berilgan to‘plamning o‘rin almashtirishlari soni
Avval aytganimizdek, o`rin almashtirish joylashtirishning xususiy xolidan iborat, shuning uchun ham o`rin almashtirishni ta elementdan dan joylashtirish deb qarash mumkin:
Bu son n elementli qism to’plamni tartiblash usullari soniga teng bo’ladi.
Misol 1. 2.1. paragrafdagi 26 kishini kassada navbatga necha xil usulda joylashtirish mumkin degan savolga endi javob berish mumkin:
Misol 2. Uchta elementdan iborat A={a, b, c} to‘plamning elementlaridan tuzilgan o‘rin almashtirishlar soni 6 ga teng:
(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a).
Teorema. elementga ega bo`lgan to`plamning barcha o`rin almashtirishlari soni ga teng.
Misol 3. Javonga 5 ta kitobni necha xil usulda joylashtirish mumkin.
Misol 4. {1, 2, 3, ... , 2n} to‘plam elementlarini juft sonlari juft o‘rinlarda keladigan qilib necha xil usulda tartiblashtirish mumkin?
Yechilishi:
Juft sonlarni juft nomerli o‘rinlarga (bunday joylar n ta) n! ta usulda qo‘yib chiqish mumkin, bu usullarning har biriga toq sonlarni toq nomerli o‘rinlarga n! ta usulda qo‘yib chiqish mos keladi. Shuning uchun ham ko‘paytirish qoidasiga ko‘ra barcha o‘rniga qo‘yishlar soniga teng bo‘ladi.
Misol 5. n ta elementdan berilgan ikkita elementi yonma-yon turmaydigan nechta o‘rin almashtirish bajarish mumkin.
Yechilishi:
a va b elementlar berilgan bo‘lsin. Bu elementlar yonma-yon turgan o‘rin almashtirishlar sonini aniqlaymiz.
Birinchi hol a element b elementdan oldin kelishi mumkin, bunda a birinchi o‘rinda, ikkinchi o‘rinda, va hokazo (n-1)- o‘rinda turishi mumkin.
Ikkinchi hol b element a elementdan oldin kelishi mumkin, bunday holatlar ham (n-1) ta bo‘ladi. Shunday qilib, a va b elementlar yonma-yon keladigan holatlar soni ta bo‘ladi. Bu usullarning har biriga qolgan (n-2) ta elementning (n-2)! ta o‘rin almashtirishi mos keladi. Demak, a va b elementlar yonma - yon keladigan barcha o‘rin
almashtirishlar soni ta bo‘ladi. Shuning uchun ham yonma-yon turmaydigan o‘rin almashtirishlar soni ga teng bo`ladi.
.Kombinatorikaning 1-qoidasi.
Kombinatorikaning 1-qoidasi: Agar qandaydir A tanlashni m usul bilan, bu usullarning har biriga biror bir boshqa B tanlashni n usulda amalga oshirish mumkin bo‘lsa, u holda A va B tanlashni (ko‘rsatilgan tartibda) usulda amalga oshirish mumkin.
6.2.Kombinatorikaning 2-qoidasi.
Kombinatorikaning 2-qoidasi: Aytaylik birin-ketin k ta harakatni amalga oshirish talab qilngan bo‘lsin. Agar birinchi harakatni - n1 usulda, ikkinchi harakatni - n2 usulda, va hokazo k – harakatni - nk usulda amalga oshirish mumkin bo‘lsa, u holda barcha k ta harakatni
usulda amalga oshirish mumkin bo‘ladi. p1, p2,...., pn – turli sodda sonlar, qandaydir natural sonlar bo‘lgan quyida berilgan songa teng umumiy bo‘luvchiga ega;
3.Tartiblangan va tartiblanmagan tanlashlar. 1-usul. Tuziladigan son 4 xonali son bo‘lishi uchun birinchi raqami 1,2,3,4,5,6 olti xil bo‘lishga haqqi bor (0 bo‘lishga haqqi yo‘q, faraz qilaylik 5 chiqdi deylik), ikkinchi raqam ham olti xil bo‘lishga haqqi bor bular: 0 va 1,2,3,4,6 raqamlarning qaysidir biri (faraz qilaylik 2 chiqdi deylik), uchinchi raqam esa besh xil bo‘lishga haqqi bor, bular 0,1,3,4,6 raqamlarning qaysidir biri (faraz qilaylik 1 chiqdi deylik), to‘rtinchi raqam esa to‘rt xil bo‘lishga haqqi bor, bular 0,3,4,6. Kombinatorikaning ikkinchi asosiy qoidasiga ko‘ra barcha tanlanishlar soni har bir raqamni tanlashlar sonlarining ko‘paytmalariga teng. Shunday qilib yuqoridagi shartlarni bajaruvchi 4 xonali sonlar 6*6*5*4=720 ta bo‘ladi.
2-usul. Faraz qilaylik 4 ta g‘ildirak berilgan bo‘lib bu g‘ildiraklarning har biriga 0 dan 6 gacha bo‘lgan raqamlar yozilgan bo‘lsin. Birinchi g‘ildirakdan 0 raqamini o‘chiramiz, chunki birinchi g‘ildirakda 0 raqami chiqib qolsa tuzilgan son to‘rt xonali bo‘lmay qoladi. Shunda birinchi g‘ildirak olti xil bo‘ishga haqqi bor. Ikkinchi g‘ildirakda 0 raqami qo‘shiladi, lekin birinchi gildirakda tushgan qaysidir 0 dan farqli raqam o‘chirib qo‘yiladi. Uchinchi g‘ildirakdan esa birinchi va ikkinchi g‘ildirakda tushgan raqamlar o‘chiriladi, keyin aylantiramiz u holda uchinchi g‘ildirakda 5 xil imkoniyat qoladi. To‘rtinchi g‘ildirakdan birinchi, ikkinchi, uchinchi g‘ildirakda tushgan raqamlar o‘chiriladi, u holda to‘rti g‘ildirak aylantirilganda uning uchun 4 xil imkoniyat qoladi. Shunday qilib Kombinatorikaning ikkinchi asosiy qoidasiga ko‘ra raqamlari 0,1,2,3,4,5,6 raqamlardan iborat va turli xil raqamlardan iborat to‘rt xonali sonlar har bir g‘ildirakda chiqishi mumkin bo‘lgan imkoniyatlari ko‘paytmasiga teng. Shunday qilib yuqoridagi shartni bajaruvchi to‘rt xonali sonlar 6*6*5*4=720 ta bo‘ladi.
6.4.Kombinatorika elementlari: O’rinlashtirish, o’rin almashtirishva guruhlashlar soni.
Teorema. n ta elementdan iborat A to‘plam uchun Faqat elementlar tartibi bilan farq qiladigan turli tartiblashtirilgan turli to‘plamlar ushbu to‘plamninig o‘rin almashtirishi deyiladi va Pn= n! bo‘ladi.
Teorema. n ta elementdan iborat to‘plamning tartiblashtirilgan k – elementli to‘plam ostilari soniga teng bo‘ladi. n elementli to‘plamning tartiblashtirilgan k-elementli to‘plam ostilari n ta elementdan k tadan joylashtirish deyiladi. n – elementli to‘plamning barcha k – elementli to‘plam ostilar soni teng bo‘ladi. n – elementli to‘plamning ixtiyoriy k – elementli to‘plam ostilari n – elementdan k tadan guruhlash deb nomlanadi. Ayrim hollarda guruhlash so‘zining o‘rniga kombinatsiya n elementdan k tadan termini ham ishlatiladi. N ta elementdan iborat A to‘plamni m ta qism to‘plamlar yig‘indisi ko‘rinishida necha xil usulda yoyish mumkin degan savol qo‘yamiz. Shunday bo‘lishi kerakki N(B1)=k1 , N(B2)=k2 , ... , N(Bm)=km bo‘lib, k1, k2 ,..., km berilgan sonlar uchun shartlar bajariladi. to‘plamlar umumiy elementlarga ega emas. A to‘plamning k1 elementli B1 to‘plam ostisini usulda tanlash mumkin, n-k1 qolgan elementlardan k2 elementli B2 to‘plam ostisini usulda tanlash mumkin va hokazo. Turli xil to‘plamlarni tanlash usullari ko‘paytirish qoidasiga ko‘ra Demak quyidagi teorema isbotlandi.
Teorema. Aytaylik k1, k2 ,..., km - butun manfiymas sonlar bo‘lib, va A to‘plam n ta elementdan iborat bo‘lsin. A ni elementlari mos ravishda k1, k2 ,..., km ta bo‘lgan m ta to‘plam ostilar yigindisi ko‘rinishida ifodalash usullari soni bo‘ladi. sonlar polinomial koeffitsiyentlar deyiladi.
3. Guruhlash qoidalari. Misollar.
Ta’rif. Har bir elementi n ta xildan biri bolishi mumkin k ta elementli guruxlarga n ta elementdan k ta elementli takrorlanuvchi guruhlashlar deb aytiladi. Teorema. N ta elementdan k ta elementli takrorlanuvchi guruhlashlar soni bo‘ladi. ko‘rinishdagi tenglama butun manfiymas yechimlari soni ham ta bo‘ladi. 6.6. Nyuton binomi. Binomial koeffitsiyentlarning xossalari. Мактаб курсидан маълумки (а +b)2= а2+2аb+b2, (а+b)3=а3+3а2b+3аb2+b3. Бу формулаларни умумлаштириб (а+b)n кавсни кандай очиш мумкин деган савол туғулиши табиийдир. Бу саволга қуйидаги теорема жавоб беради: Teorema (Binomial teorema) Quyidagi tenglik o‘rinli bu yerda sonlarga binomial koeffitsiyentlar, tenglamaga esa Nyuton binomi deyiladi. Ushbu nom tarixiy haqiqat emas, chunki Nyutondan oldin ushbu formulani Umar Xayyom (1046-1131), G‘iyos ad-Din Jamshid al-Koshi bilishgan. Nyutonning xizmati ushbu formulani butun bo‘lmagan n uchun umumlashtirgan.
Исботи. ( а+b ) йиғиндини кетма-кет n марта кўпайтирамиз. У холда хар бир хади d1,d2,…dn кўринишига эга бўламиз, бунда di а ёки в га тенг, i=1,2.. Барча қўшилувчиларни В0,В1,…Вn бўлган ( n+1) та гурухларга ажратамиз, Вk гурухда в кўпайтувчи к марта, а эса n-k марта учрайди. Вк даги кўпайтувчилар сони Скn га тенглиги тушунарли албатта. Хар Вk даги кўпайтирувчиларнинг хар бири аn-к вк га тенг, бундай хадлар сони га тенг , шу сабабли
(а+b)n=∑ ak bn-k k=0 теорема исботланди. Биномиал коэффициентларнинг қуйидаги мухим хоссасини эслатиб ўтамиз
(2) Бу хосса 3-маърузада исботланган.
(2) тенглик биномиал коэффициентларни уч бурчакли жадвал кўринишида кетма-кет ёзиш мумкинлигини кўрсатади.
1 1 n=1
1 2 1 n=2
1 3 3 1 n=3
1 4 6 4 1 n=4
1 5 10 10 5 1 n=5
1 6 15 20 15 6 1 n=6
1 7 21 35 35 21 7 1 n=7
. . . . . . . . . . . . . . . . . . . . .
Бу жадвал Паскал учбурчаги деб аталади.
Паскал учбурчагининг n – сатридаги сонлар (а+b)n ёйилмасининг коэффициент 1 сонлардан бошқа хар бир коэффициент олдинги сатрда турган 2 та мос коэффициентлар йиғиндисига тенг. Polinomial teorema. ifoda, bo‘lishi mumkin bo‘lgan barcha quyidagi ko‘rinishdagi qo‘shiluvchilar yig‘indisidan iborat bo‘lib Bu erda , ya’niga teng bo‘ladi. k=2 бўлганда (3) тенглик қуйидаги кўринишга келади : Демак, хусусий холда Ньютон биноми формуласига эга бўламиз.
Foydalanilgan adabiyotlar: http://fayllar.org
|
