Takrorlanuvchi o‘rin almashtirishlar

|
Takrorlanuvchi o‘rin almashtirishlar
|
bet | 7/7 | Sana | 18.11.2023 | Hajmi | 358,28 Kb. | | #101151 |
Bog'liq 2-mustaqil ish(diskret tuzilmalar)Takrorlanuvchi o‘rin almashtirishlar.
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.
AB1 B2 ...Bm
Shunday bo„lishi kerakki N(B1)=k1 , N(B2)=k2 , ... , N(Bm)=km bo„lib, k1, k2 ,..., km berilgan sonlar uchun
ki 0, k1 k2 ...km n
shartlar bajariladi. B1,B2,...,Bm to„plamlar umumiy elementlarga ega emas.
A to„plamning k1 elementli B1 to„plam ostisini Сnk1 usulda tanlash mumkin, n-k1 qolgan elementlardan k2 elementli B2 to„plam ostisini Сnk2k1 usulda tanlash mumkin va hokazo. Turli xil B1,B2,...,Bm to„plamlarni tanlash usullari ko„paytirish qoidasiga ko„ra
Сnk1 *Сnk2k1 *Cnk3k1k2 *...*Cnkmk1k2...km1
n ! * (nk1) ! * (nk1 k2) ! *....* (nk1 k2 ....km1)
k1 !*(nk1) ! k2 !*(nk1 k2) ! k3 ! *(nk1 -k2 -k3) ! km !*(nk1 -k2 -...-km)!
n !
k1 !* k2 !* ...* km!
Demak quyidagi teorema isbotlandi.
Teorema. Aytaylik k1, k2 ,..., km - butun manfiymas sonlar bo„lib, k1 k2 ...km n va A to„plam n ta elementdan iborat bo„lsin. A ni
elementlari mos ravishda k1, k2 ,..., km ta bo„lgan B1,B2,...,Bm m ta to„plam ostilar yigindisi ko„rinishida ifodalash usullari soni
n !
Сn(k1,...,km)
k1 !* k2 !* ...* km!
ta bo„ladi.
Сn(k1,...,km) sonlar polinomial koeffitsiyentlar deyiladi.
Misol 1. “Matematika” so„zidagi harflardan nechta so„z yasash mumkin?
K1=2 (“m”- harfi), k2 =2 (“a” – harfi), k3 =2 (“t” – harfi), k4=1 (“e” – harfi), k5=1 (“i”harfi), k6=1 (“k”- harfi), n=10 (so„zdagi harflar soni)
С10(2,3,2,1,1,1) 151200
!
Misol 2. “Dada” so„zidagi harflardan nechta so„z yasash mukin?
С4(2,2) 6
!
Dada, daad, ddaa, adda, adad, aadd.
Teorema. Elementlarining k1 tasi 1- tipda, k2 tasi 2-tipda, va hokazo km tasi m-tipda bo„lgan n elementli to„plamning barcha o‘rin almashtirishlar soni n !
Сn(k1,...,km) k1 !* k2 !* ...* km!
ta bo„ladi.
Shu o„rinda eslatib o„tamiz BMI, magistrlik dissertatsiyasi yoki ilmiy ishingizda ko„p miqdordagi takrorlanuvchi o„rin almashtirishlarni hisoblashga to„g„ri kelsa, unda Excel
dasturlar paketidagi МУЛЬТИНОМ komandasidan foydalanish mumkin: Masalan
С 10(1,2,4,3)
ekanligi ni tezlik bilan
hisobla
sh hech qanday
qiyinchilik tug„dirmaydi.
Takrorlanuvchi guruhlashlar.
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
fnk Cnnk11 Cnkk1
ta bo„ladi.
x1 x2 ...xn k ko„rinishdagi tenglama butun manfiymas yechimlari soni ham
fnk ta bo„ladi.
Maktab kursidan ma'lumki, (а +b)2= а2+2аb+b2,
(а+b)3=а3+3а2b+3аb2+b3.
Bu formulalarni umumlashtirib (а+b)n qavsni qanday ochish mumkin degan savol tug‟ilishi tabiiy.
Bu savolga quyidagi teorema javob beradi:
Teorema (Binomial teorema). Quyidagi tenglik o'rinli
(ab)n Cn0 *an *b0 Cn1 *an1 *b1 ...Cnk *ank *bk ...Cnn *a0 *bn
n k *ank *bk
Cn
k0
bu yerda Сnk sonlarga binomial koeffitsiyentlar, tenglamaga esa N’yuton binomi deyiladi.
Formulaning bunday nomlanishi tarixiy haqiqat emas, chunki N‟yutondan oldin bu formulani O‟rta Osiyolik mutafakkir Umar Xayyom (1046-1131), G'iyosiddin Jamshid al-Koshiy o‟zlarining ishlarida qo‟llashgan.
N‟yutonning xizmati shundaki, formulani butun bo'lmagan n uchun umumlashtirgan.
Isboti. ( a+b ) yig‟indini ketma-ket n marta ko‟paytiramiz. U holda har bir hadi d1,d2,…dn ko‟rinishga ega bo‟lamiz, bunda di a yoki b ga teng, i=1,2…. Barcha
qo‟shiluvchilarni В0,В1,…Вn bo‟lgan ( n+1) ta guruhlarga ajratamiz, Вk guruhda b
ko‟paytuvchi k marta, a esa n-k marta uchraydi. Вk dagi ko‟paytuvchilar soni Скn ga
tengligi tushunarli albatta. Har Вk dagi ko‟paytuvchilarning har biri аn-к bк ga teng, bunday hadlar soni Сnk ga teng, shu sababli
n
(ab)n Cnk ank bk (1)
k0 teorema isbotlandi. Binomial koeffitsientlarning quyidagi muhim xossasini eslatib o‟tamiz
Сnk1 Сnk Сnk1 (2)
Bu xossa 3-ma'ruzada isbotlangan.
(2) tenglik binomial koeffitsientlarni uchburchakli jadval ko‟rinishida ketma-ket yozish mumkinligini ko‟rsatadi.
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
. . . . . . . . . . . . . . . . . . . . .
Bu jadval Paskal uchburchagi deb ataladi.
Paskal uchburchagining n - satridagi sonlar (а+b)n yoyilmasining koeffisienti 1 sonlardan boshqa har bir koeffitsient oldingi satrda turgan 2 ta mos koeffisientlar yig‟indisiga teng.
Polinomial teorema. a1 a2 ...akn ifoda, bo'lishi mumkin bo'lgan
barcha quyidagi ko'rinishdagi qo'shiluvchilar yig'indisidan iborat bo'lib,
n! r1 *a2r2 *...*akrk (2)
*a1
r1!*r2!*...*rk!
Bu erda r1 r2 ...rk n, ya'ni
a1 a2 ...ak n r10,...,rk r1!*r2!*...n! *rk!*a1r1 *a2r2 *...*akrk
0
r1r2...rk n (3)
ga teng bo'ladi.
k=r bo‟lganda (3) tenglik quyidagi ko‟rinishga keladi:
(a1 a2 )n = n r1!(nn! r)! a1nr a2r
r 0
Demak, xususiy holda N‟yuton binomi formulasiga ega bo‟lamiz.
|
| |