1. Binomial koeffitsientlar Multiplikatsion formulalar

Nyuton binomi.Binomial koeffietsientlarning hossalari.Hosil qiluvchi funksiyalar va ularning kombinatorika masalalarini yechishga tatbiqi

Reja:

1.Binomial koeffitsientlar

2.Multiplikatsion formulalar

3.Faktorial formulalar

Binomial koeffitsientlarni shakllantirish uchun tartibga solish mumkin Paskal uchburchagi, unda har bir yozuv yuqoridagi ikkitaning yig'indisi.

Ikkinchi kuchga qadar binomial kengayishni vizualizatsiya qilish

Yilda matematika, binomial koeffitsientlar ijobiydir butun sonlar kabi sodir bo'ladi koeffitsientlar ichida binomiya teoremasi. Odatda binomial koeffitsient butun juftlik bilan indekslanadi n ≥ k ≥ 0 va yozilgan Bu koeffitsient xk muddat polinom kengayishi ning binomial kuch (1 + x)n, va u formula bilan berilgan

Masalan, ning to'rtinchi kuchi 1 + x bu

va binomial koeffitsient ning koeffitsienti x2 muddat.

Raqamlarni tartibga solish uchun ketma-ket qatorlarda deb nomlangan uchburchak qatorni beradi Paskal uchburchagi, qoniqarli takrorlanish munosabati

Binomial koeffitsientlar matematikaning ko'plab sohalarida va ayniqsa, uchraydi kombinatorika. Belgisi odatda "deb o'qiladin tanlang k"chunki bor (tartibsiz) kichik to'plamni tanlash usullari k sobit to'plamidan elementlar n elementlar. Masalan, bor dan 2 ta elementni tanlash usullari ya'ni va

Binomial koeffitsientlarni umumlashtirish mumkin har qanday murakkab raqam uchun z va tamsayı k ≥ 0, va ularning ko'plab xususiyatlari ushbu umumiy shaklda saqlanib qolishda davom etmoqda.

Andreas fon Ettingshausen notani kiritdi 1826 yilda,[1] raqamlar bir necha asrlar ilgari ma'lum bo'lgan bo'lsa-da (qarang Paskal uchburchagi). Binomial koeffitsientlarning eng qadimgi batafsil muhokamasi X asr sharhida Halayudha, qadimiy Sanskritcha matn, Pingala"s Chandḥśāstra. Taxminan 1150 yilda hind matematikasi Bxaskaracharya o'z kitobida binomial koeffitsientlar ekspozitsiyasini bergan Livatī.[2]

Shu bilan bir qatorda yozuvlar kiradi C(n, k), nCk, nCk, Ckn, Cnkva Cn,k bularning barchasida C degan ma'noni anglatadi kombinatsiyalar yoki tanlov. Ko'pgina kalkulyatorlarda C yozuv chunki ular uni bitta qatorli displeyda namoyish etishlari mumkin. Ushbu shaklda binomial koeffitsientlar osongina taqqoslanadi k- ning o'zgarishi nsifatida yozilgan P(n, k), va boshqalar

Uchun natural sonlar (0 qo'shilishi uchun olingan) n va k, binomial koeffitsient deb belgilash mumkin koeffitsient ning monomial Xk ning kengayishida (1 + X)n. Xuddi shu koeffitsient ham paydo bo'ladi (agar k ≤ n) ichida binomiya formulasi

(har qanday element uchun amal qiladi x, y a komutativ uzuk), bu "binomial koeffitsient" nomini tushuntiradi.

Ushbu raqamning yana bir paydo bo'lishi kombinatorikada bo'lib, u tartibni inobatga olmasdan yo'llarning sonini beradi k ob'ektlar orasidan tanlanishi mumkin n ob'ektlar; rasmiy ravishda, soni k-element pastki to'plamlari (yoki k-kombinatsiyalar) ning n- elementlar to'plami. Ushbu raqamni hisoblash uchun quyidagi formulalardan mustaqil ravishda, birinchi ta'riflardan biriga teng deb qarash mumkin: agar har birida n kuch omillari (1 + X)n biri vaqtincha vaqtni belgilaydi X indeks bilan men (1dan boshlab ishlaydi n), keyin har bir kichik to'plam k indekslar kengayishdan keyin o'z hissasini qo'shadi Xkva natijada ushbu monomialning koeffitsienti bunday kichik to'plamlarning soni bo'ladi. Bu, ayniqsa, buni ko'rsatadi har qanday natural sonlar uchun natural son n va k. Binomial koeffitsientlarning ko'plab boshqa kombinatsion talqinlari mavjud (masalan, javob binomial koeffitsient ifodasi bilan berilgan muammolarni hisoblash), masalan, hosil bo'lgan so'zlar soni n bitlar (0 yoki 1 raqamlari), ularning yig'indisi k tomonidan berilgan , yozish usullari soni qaerda har biri amen manfiy bo'lmagan butun son tomonidan berilgan . Ushbu talqinlarning aksariyati hisoblashga teng ekanligi osongina ko'rinadi k-birlashmalar.

Binomial koeffitsientlar

Qiymatini hisoblash uchun bir necha usul mavjud aslida binomial quvvatni kengaytirmasdan yoki hisoblamasdan k-birlashmalar.

Formula {1, 2, 3, ..., to'plamni ko'rib chiqishdan kelib chiqadi n} va alohida hisoblash (a) the k- ma'lum bir elementni o'z ichiga olgan element guruhlari, aytaylik "men", har bir guruhda (beri"men"allaqachon har bir guruhda bitta joyni to'ldirish uchun tanlangan, biz faqat tanlashimiz kerak k - qolganlardan 1 ta n - 1) va (b) barcha k"o'z ichiga olmaydigan guruhlar"men"; bu mumkin bo'lgan barcha narsalarni sanab beradi k-birlashmalari n elementlar. Shuningdek, bu hissalarni kuzatib borishdan kelib chiqadi Xk yilda (1 + X)n−1(1 + X). Nol bo'lgani kabi Xn+1 yoki X−1 yilda (1 + X)n, ta'rifni qo'shish uchun yuqoridagi chegaralardan tashqariga chiqarishi mumkin = 0 bo'lganda ham k > n yoki k <0. Keyinchalik bu rekursiv formulaning tuzilishiga imkon beradi Paskal uchburchagi, nollar yoki ahamiyatsiz koeffitsientlar bo'ladigan oq bo'shliqlar bilan o'ralgan.

Multiplikatsion formula

Ayrim binomial koeffitsientlarni hisoblashning yanada samarali usuli formulada keltirilgan

bu erda birinchi kasrning numeratori a sifatida ifodalanadi tushayotgan faktorial kuchBinomiy koeffitsientlarning kombinatorial talqini uchun ushbu formulani eng oson anglash mumkin. Nomerator ketma-ketlikni tanlash yo'llarini beradi k to'plamidan tanlash tartibini saqlab qolgan alohida ob'ektlar n ob'ektlar. Mahrum qiluvchi bir xil aniqlaydigan aniq ketma-ketliklar sonini hisoblaydi k-tartibga e'tibor berilmaganda kombinatsiya.

Binomial koeffitsientning nisbatan simmetriyasi tufayli k va n − k, mahsulotning yuqori chegarasini yuqorisidan kichikiga o'rnatish orqali hisoblash optimallashtirilishi mumkin k va n − k.

Faktorial formulalar

Va nihoyat, hisoblash uchun yaroqsiz bo'lsa-da, ko'pincha dalillarda va chiqindilarda ishlatiladigan ixcham shakl mavjud, bu tanishlardan takroriy foydalanishni ta'minlaydi faktorial funktsiyasi:

qayerda n! ning faktorialligini bildiradi n. Ushbu formula yuqoridagi multiplikativ formuladan numerator va maxrajni ko'paytirish orqali kelib chiqadi (n − k)!; Natijada u raqamlovchi va maxrajga xos bo'lgan ko'plab omillarni o'z ichiga oladi. Bu aniq hisoblash uchun kamroq amaliy (agar shunday bo'lsa) k kichik va n katta), umumiy omillar bekor qilinmasa (xususan, faktorial qiymatlar juda tez o'sib borishi sababli). Formulada multiplikativ formuladan unchalik aniq bo'lmagan simmetriya mavjud (garchi bu ta'riflardan bo'lsa ham)

bu yanada samarali multiplikativ hisoblash tartibiga olib keladi. Dan foydalanish tushayotgan faktorial yozuvlar,

Umumlashtirish va binomial qatorga ulanish

Multiplikatsion formula binomial koeffitsientlarning ta'rifini kengaytirishga imkon beradi[3] almashtirish bilan n o'zboshimchalik bilan raqam bilan a (salbiy, haqiqiy, murakkab) yoki hatto har qanday element komutativ uzuk unda barcha musbat tamsayılar teskari bo'ladi:

Ushbu ta'rif bilan binomial formulaning umumlashtirilishi mavjud (o'zgaruvchilardan biri 1 ga o'rnatilgan bo'lsa), bu hali ham binomial koeffitsientlar:

Ushbu formula barcha murakkab sonlar uchun amal qiladi a va X bilan |X| <1. Shuningdek, uni identifikator sifatida talqin qilish mumkin rasmiy quvvat seriyalari yilda X, bu erda u haqiqatan ham doimiy koeffitsienti 1 ga teng bo'lgan quvvat seriyasining ixtiyoriy kuchlarini ta'riflashi mumkin; Gap shundaki, ushbu ta'rif bilan biz kutgan barcha identifikatorlar mavjud eksponentatsiya, ayniqsa

Agar a manfiy bo'lmagan butun son n, keyin barcha shartlar k > n nolga teng, va cheksiz qator cheklangan yig'indiga aylanadi va shu bilan binomial formulani tiklaydi. Biroq, ning boshqa qiymatlari uchun amanfiy tamsayılar va ratsional sonlarni o'z ichiga olgan qator haqiqatan ham cheksizdir.

Paskal uchburchagining vertikal holda joylashtirilgan 1000-qatori, koeffitsientlarning o'nli raqamlari kulrang ko'lamda tasvirlangan, o'ng tomonga yo'naltirilgan. Rasmning chap chegarasi taxminan binomial koeffitsientlar logarifmasi grafigiga to'g'ri keladi va ularning hosil bo'lishini aks ettiradi log-konkav ketma-ketligi.

Asosiy maqolalar: Paskal uchburchagi va Paskalning qoidasi

Paskalning qoidasi bu muhim takrorlanish munosabati

tomonidan isbotlash uchun ishlatilishi mumkin matematik induksiya bu butun son uchun natural son n ≥ 0 va butun son k, darhol aniq bo'lmagan haqiqat formula (1). Paskal uchburchagining chap va o'ng tomonidagi yozuvlar (bo'shliqlar shaklida ko'rsatilgan) barchasi nolga teng.

Paskalning qoidasi ham sabab bo'ladi Paskal uchburchagi:

0: 1

1: 1 1

2: 1 2 1

3: 1 3 3 1

4: 1 4 6 4 1

5: 1 5 10 10 5 1

6: 1 6 15 20 15 6 1

7: 1  7  21 35 35 21 7  1 

8: 1  8  28 56 70 56 28 8  1 

Qator raqami n raqamlarni o'z ichiga oladi uchun k = 0, ..., n. Dastlab 1-ni eng tashqi holatiga qo'yib, so'ngra har bir ichki pozitsiyani to'g'ridan-to'g'ri yuqoridagi ikkita sonning yig'indisi bilan to'ldirish orqali quriladi. Ushbu usul binomial koeffitsientlarni fraksiyalar yoki ko'paytmalarga ehtiyoj sezmasdan tezda hisoblash imkonini beradi. Masalan, uchburchakning 5-qatoriga qarab, buni tezda o'qish mumkin

Binomial koeffitsientlar muhim ahamiyatga ega kombinatorika, chunki ular tez-tez hisoblashning muayyan muammolari uchun tayyor formulalarni taqdim etadi:

Lar bor tanlash usullari k to'plamidan elementlar n elementlar. Qarang Kombinatsiya.

Lar bor tanlash usullari k to'plamidan elementlar n takrorlashga ruxsat berilsa, elementlar. Qarang Multiset.

Lar bor torlar o'z ichiga olgan k birlari va n nollar.

Lar bor dan iborat torlar k birlari va n ikkitasi qo'shni bo'lmasligi uchun nollar.[4]

The Kataloniya raqamlari bor

The binomial taqsimot yilda statistika bu

Binomial koeffitsientlar polinomlar sifatida

Har qanday salbiy bo'lmagan butun son uchun k, ifoda soddalashtirilishi va bo'linadigan polinom sifatida belgilanishi mumkin k!:

bu taqdim etadi a polinom yilda t bilan oqilona koeffitsientlar.

Shunday qilib, uni har qanday haqiqiy yoki murakkab sonda baholash mumkin t binomial koeffitsientlarni bunday birinchi argumentlar bilan aniqlash. Ushbu "umumlashtirilgan binomial koeffitsientlar" Nyutonning umumlashtirilgan binomial teoremasi.

Har biriga k, polinom noyob daraja sifatida tavsiflanishi mumkin k polinom p(t) qoniqarli p(0) = p(1) = ... = p(k - 1) = 0 va p(k) = 1.

Uning koeffitsientlari jihatidan ifodalanadi Birinchi turdagi raqamlar:

Binomial koeffitsientlar polinomlar makonining asosi sifatida

Har qanday narsadan ham ko'proq maydon ning xarakterli 0 (ya'ni o'z ichiga olgan har qanday maydon ratsional sonlar), har bir polinom p(t) eng ko'p daraja d chiziqli birikma sifatida noyob tarzda ifodalanadi