Біноміальні коефіцієнти — коефіцієнти в розкладі по степенях (так званий біном Ньютона):
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpOW1MMlkyTDFCaGMyTmhiQ1V5TjNOZmRISnBZVzVuYkdWZk5TNXpkbWN2TWpBd2NIZ3RVR0Z6WTJGc0pUSTNjMTkwY21saGJtZHNaVjgxTG5OMlp5NXdibWM9LnBuZw==.png)
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODBMelEzTDBKcGJtOXRhV0ZzWDNSb1pXOXlaVzFmZG1semRXRnNhWE5oZEdsdmJpNXpkbWN2TWpJNWNIZ3RRbWx1YjIxcFlXeGZkR2hsYjNKbGJWOTJhWE4xWVd4cGMyRjBhVzl1TG5OMlp5NXdibWM9LnBuZw==.png)
Біноміальний коефіцієнт є узагальненням кількості невпорядкованих виборів , що визначена тільки для невід'ємних цілих чисел , , тобто та У явному вигляді для :
- ,
де та — факторіали чисел і .
Явні формули
Обчислюючи коефіцієнти в розкладі у степеневий ряд, можна отримати явні формули для біноміальних коефіцієнтів
.
Для всіх дійсних чисел n і цілих чисел k:
де позначає факторіал числа k.
Для невід'ємних цілих n і k також справедливі формули:
Для цілих від'ємних показників коефіцієнти розкладу бінома рівні
Трикутник Паскаля
Тотожність дозволяє розташувати біноміальні коефіцієнти для невід'ємних
,
у вигляді трикутника Паскаля, в якому кожне число рівне сумі двох, що стоять на рядок вище:
Трикутна таблиця, запропонована Паскалем в «Трактаті про арифметичний трикутник» (1654), відрізняється від описаної тут поворотом на 45°. Таблиці для зображення біноміальних коефіцієнтів були відомі й раніше.
Властивості
Твірні функції
Для фіксованого значення n твірною функцією послідовності біноміальних коефіцієнтів … є
Для фіксованого значення k твірною функцією послідовності коефіцієнтів … є
.
Двовимірною твірною функцією біноміальних коефіцієнтів для цілих
є
або
Подільність
Із теореми Люка випливає, що:
- коефіцієнт
непарний
в двійкового запису числа k одиниці не стоять у тих розрядах, де в числі n стоять нулі;
- коефіцієнт
не кратний простому число p
при записі числа k в системі числення з основою p, всі розряди не перевищують відповідних розрядів числа n;
- у послідовності біноміальних коефіцієнтів
:
- всі числа не кратні заданому простому p
число
можна подати у вигляді
, де натуральне число
;
- всі числа, крім першого й останнього, кратні даному простому p
;
- кількість непарних чисел дорівнює степеню двійки, показник якої дорівнює кількості одиниць у двійковому записі числа n;
- парних і непарних чисел не може бути порівну;
- кількість чисел, не кратних простому p, дорівнює
, де числа
— розряди p-кового запису числа n; а число
де
— функція «підлоги» — це довжина даного запису.
- всі числа не кратні заданому простому p
Тотожності
(згортка Вандермонда)
Біном Ньютона і наслідки
де
де
- Сильніша тотожність:
де
а в загальнішому вигляді
Згортка Вандермонда і наслідки
(згортка Вандермонда), де
а
Це тотожність виходить обчисленням коефіцієнта при у розкладі
з урахуванням тотожності
Сума береться за всіма цілими
, для яких
Для довільних дійсних
,
число ненульових доданків у сумі буде скінченним.
.
- загальніша тотожність:
, якщо
.
Інші тотожності
— n- е гармонічне число.
- Мультисекція ряду
дає тотожність, що виражає суму біноміальних коефіцієнтів із довільним кроком s і зміщенням t
у вигляді скінченної суми з s доданків:
- Виконуються рівності:
Звідки випливає:
де — кількість розміщень із n по k.
Матричні співвідношення
Якщо взяти квадратну матрицю, відрахувавши N елементів по катетах трикутника Паскаля і повернувши матрицю на будь-який з чотирьох кутів, то детермінант цих чотирьох матриць дорівнює ±1 за будь-якого N, причому детермінант матриці з вершиною трикутника у верхньому лівому куті дорівнює 1.
У матриці числа на діагоналі
повторюють числа рядків трикутника Паскаля
. Її можна розкласти в добуток двох строго діагональних матриць: нижньотрикутної та одержуваної з неї транспонуванням. А саме:
де . Обернена матриця до
має вигляд:
Таким чином, матрицю, обернену до , можна розкласти в добуток двох строго діагональних матриць: перша матриця — верхньотрикутна, а друга виходить з першої транспонуванням, що дозволяє дати явний вираз для обернених елементів:
, де i, j, m, n = 0..p.
Елементи оберненої матриці змінюються за зміни її розміру і, на відміну від матриці , недостатньо приписати новий рядок і стовпець. Стовпець j матриці
є многочленом степеня j за аргументом i, отже, перші p стовпців утворюють повний базис у просторі векторів довжини p+1, чиї координати можна інтерполювати многочленом степеня рівного або меншого ніж p-1. Нижній рядок матриці
ортогональний до будь-якого такого вектора.
при
, де
многочлен степеня
.
Якщо довільний вектор довжини можна інтерполювати многочленом степеня
, то скалярний добуток з рядками
(нумерація з 0) матриці
дорівнює нулю. Використовуючи тотожність вище і рівність одиниці скалярного добутку нижнього рядка матриці
на останній стовпець матриці
, маємо:
Для показника, більшого від p, можна задати рекурентну формулу:
де многочлен
Для доведення спершу доводиться тотожність:
Якщо потрібно знайти формулу не для всіх показників степеня, то
Старший коефіцієнт дорівнює 1, щоб знайти інші коефіцієнти, знадобиться
значень:
для
Цілозначні многочлени
Біноміальні коефіцієнти … є цілозначними многочленами від
, тобто, набувають цілих значень за цілих значень
— це неважко зрозуміти, наприклад, за трикутником Паскаля. Більш того, вони утворюють базис цілозначних многочленів, у якому всі цілозначні многочлени виражаються як лінійні комбінації з цілими коефіцієнтами.
Разом з тим, стандартний базис … не дозволяє виразити всіх цілочисельних многочленів, якщо використовувати тільки цілі коефіцієнти, оскільки вже
має дробові коефіцієнти при степенях
.
Цей результат узагальнюється на многочлени багатьох змінних. А саме, якщо многочлен степеня
має дійсні коефіцієнти і набуває цілих значень за цілих значень змінних, то
де — многочлен із цілими коефіцієнтами.
Асимптотика і оцінки
при
(нерівність Чебишева)
(), де
— ентропія.
(нерівність Чернова)
Алгоритми обчислення
- Біноміальні коефіцієнти можуть бути обчислені за допомогою тотожності
, якщо на кожному кроці зберігати значення
для
. Цей алгоритм особливо ефективний, якщо необхідно отримати всі значення
при фіксованому
. Алгоритм потребує
пам'яті (
для обчислення всієї таблиці) і
часу.
- Інший спосіб ґрунтується на тотожності
. Він дозволяє обчислити значення
при фіксованому
. Алгоритм потребує
пам'яті і
часу.
Узагальнення
Оскільки для , то значення біноміального коефіцієнта можна визначити для усіх комплексних чисел
та
:
Явні формули для обчислення біноміальних коефіцієнтів для цілих чисел та
:
для
;
для
або
;
для
.
Біноміальні коефіцієнти часто зустрічаються в комбінаторних задачах і теорії імовірностей.
Узагальненням біноміального коефіцієнта є поліноміальний коефіцієнт.
Генерація на C++
#include <iostream> #include <string> using namespace std; void C(int n, int m, int startAt = 1, string s = "") { for (int i = startAt; i <= n - m + 1; i++) { if (1 == m) cout << s + (char)(i+'0') << endl; else C(n, m - 1, i + 1, s + (char)(i+'0')); } } int main() { C(7, 3); return 0; }
Див. також
Примітки
Джерела
- Завало С. Т. (1972). Елементи аналізу. Алгебра многочленів. Київ: Радянська школа. с. 462. (укр.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Binomialni koeficiyenti koeficiyenti v rozkladi 1 x n displaystyle 1 x n po stepenyah x displaystyle x tak zvanij binom Nyutona Binomialni koeficiyenti roztashovani u viglyadi trikutnika Paskalya Vizualizaciya binomialnih koeficiyentiv do 4 stepenya 1 x n n0 n1 x n2 x2 nn xn k 0n nk xk displaystyle 1 x n n choose 0 n choose 1 x n choose 2 x 2 cdots n choose n x n sum k 0 n n choose k x k Binomialnij koeficiyent ye uzagalnennyam kilkosti nevporyadkovanih viboriv Cnk displaystyle C n k sho viznachena tilki dlya nevid yemnih cilih chisel n displaystyle n k displaystyle k tobto n 1 N displaystyle n 1 in mathbb N ta k 1 N displaystyle k 1 in mathbb N U yavnomu viglyadi dlya 0 k n displaystyle 0 leq k leq n nk Cnk n k n k displaystyle n choose k C n k frac n k n k de n displaystyle n ta k displaystyle k faktoriali chisel n displaystyle n i k displaystyle k Yavni formuliObchislyuyuchi koeficiyenti v rozkladi 1 x n displaystyle 1 x n u stepenevij ryad mozhna otrimati yavni formuli dlya binomialnih koeficiyentiv nk displaystyle textstyle binom n k Dlya vsih dijsnih chisel n i cilih chisel k nk n n 1 n 2 n k 1 k k 0 0 k lt 0 displaystyle binom n k begin cases frac n n 1 n 2 cdot ldots cdot n k 1 k amp k geqslant 0 0 amp k lt 0 end cases de k displaystyle k poznachaye faktorial chisla k Dlya nevid yemnih cilih n i k takozh spravedlivi formuli nk n k n k 0 k n 0 k gt n displaystyle binom n k begin cases frac n k n k amp 0 leqslant k leqslant n 0 amp k gt n end cases Dlya cilih vid yemnih pokaznikiv koeficiyenti rozkladu binoma 1 x n displaystyle 1 x n rivni nk 1 k n k 1 k n 1 k 0 0 k lt 0 displaystyle binom n k begin cases 1 k cdot frac n k 1 k n 1 amp k geqslant 0 0 amp k lt 0 end cases Trikutnik PaskalyaDokladnishe Trikutnik Paskalya Totozhnist nk n 1k 1 n 1k displaystyle n choose k n 1 choose k 1 n 1 choose k dozvolyaye roztashuvati binomialni koeficiyenti dlya nevid yemnih n displaystyle n k displaystyle k u viglyadi trikutnika Paskalya v yakomu kozhne chislo rivne sumi dvoh sho stoyat na ryadok vishe n 0 1n 1 11n 2 121n 3 1331n 4 14641 displaystyle begin matrix n 0 amp amp amp amp amp 1 amp amp amp amp n 1 amp amp amp amp 1 amp amp 1 amp amp amp n 2 amp amp amp 1 amp amp 2 amp amp 1 amp amp n 3 amp amp 1 amp amp 3 amp amp 3 amp amp 1 amp n 4 amp 1 amp amp 4 amp amp 6 amp amp 4 amp amp 1 vdots amp amp vdots amp amp vdots amp amp vdots amp amp vdots amp end matrix Trikutna tablicya zaproponovana Paskalem v Traktati pro arifmetichnij trikutnik 1654 vidriznyayetsya vid opisanoyi tut povorotom na 45 Tablici dlya zobrazhennya binomialnih koeficiyentiv buli vidomi j ranishe VlastivostiTvirni funkciyi Dlya fiksovanogo znachennya n tvirnoyu funkciyeyu poslidovnosti binomialnih koeficiyentiv n0 n1 n2 displaystyle tbinom n 0 tbinom n 1 tbinom n 2 ye k 0 nk xk 1 x n displaystyle sum k 0 infty binom n k x k 1 x n Dlya fiksovanogo znachennya k tvirnoyu funkciyeyu poslidovnosti koeficiyentiv 0k 1k 2k displaystyle tbinom 0 k tbinom 1 k tbinom 2 k ye n nk yn yk 1 y k 1 displaystyle sum n binom n k y n frac y k 1 y k 1 Dvovimirnoyu tvirnoyu funkciyeyu binomialnih koeficiyentiv nk displaystyle tbinom n k dlya cilih n k displaystyle n k ye n k nk xkyn 11 y xy displaystyle sum n k binom n k x k y n frac 1 1 y xy abo n 0 k 0n nk xkyn 11 y xy displaystyle sum n 0 infty sum k 0 n binom n k x k y n frac 1 1 y xy Podilnist Iz teoremi Lyuka viplivaye sho koeficiyent nk displaystyle textstyle binom n k neparnij displaystyle iff v dvijkovogo zapisu chisla k odinici ne stoyat u tih rozryadah de v chisli n stoyat nuli koeficiyent nk displaystyle textstyle binom n k ne kratnij prostomu chislo p displaystyle iff pri zapisi chisla k v sistemi chislennya z osnovoyu p vsi rozryadi ne perevishuyut vidpovidnih rozryadiv chisla n u poslidovnosti binomialnih koeficiyentiv n0 n1 nn displaystyle textstyle binom n 0 binom n 1 ldots binom n n vsi chisla ne kratni zadanomu prostomu p displaystyle iff chislo n displaystyle n mozhna podati u viglyadi mpk 1 displaystyle mp k 1 de naturalne chislo m lt p displaystyle m lt p vsi chisla krim pershogo j ostannogo kratni danomu prostomu p displaystyle iff n pk displaystyle n p k kilkist neparnih chisel dorivnyuye stepenyu dvijki pokaznik yakoyi dorivnyuye kilkosti odinic u dvijkovomu zapisi chisla n parnih i neparnih chisel ne mozhe buti porivnu kilkist chisel ne kratnih prostomu p dorivnyuye a1 1 am 1 displaystyle a 1 1 dots a m 1 de chisla a1 am displaystyle a 1 ldots a m rozryadi p kovogo zapisu chisla n a chislo m logp n 1 displaystyle textstyle m lfloor log p n rfloor 1 de displaystyle lfloor cdot rfloor funkciya pidlogi ce dovzhina danogo zapisu Totozhnosti nk n 1k 1 n 1k displaystyle n choose k n 1 choose k 1 n 1 choose k nk nn k n 1k displaystyle n choose k frac n n k n 1 choose k n0 n1 nn 2n displaystyle n choose 0 n choose 1 cdots n choose n 2 n n0 n2 n2 n 2 2n 1 displaystyle n choose 0 n choose 2 cdots n choose 2 lfloor n 2 rfloor 2 n 1 n0 2 n1 2 nn 2 2nn displaystyle n choose 0 2 n choose 1 2 cdots n choose n 2 2n choose n k 0n rm k sn k r sm n displaystyle sum k 0 n r choose m k s choose n k r s choose m n zgortka Vandermonda Binom Nyutona i naslidki n0 n1 nn 2n displaystyle n choose 0 n choose 1 ldots n choose n 2 n de n N displaystyle n in mathbb N i j m nj ni 1 j nm 2 yaksho m 0 mod2 0 yaksho m 1 mod2 displaystyle sum i j m binom n j binom n i 1 j begin cases binom n m 2 amp text yaksho m equiv 0 pmod 2 0 amp text yaksho m equiv 1 pmod 2 end cases j kn nj 1 j 1 k n 1k 1 displaystyle sum j k n binom n j 1 j 1 k binom n 1 k 1 n0 n1 1 n nn 0 displaystyle n choose 0 n choose 1 ldots 1 n n choose n 0 de n N displaystyle n in mathbb N Silnisha totozhnist n0 n2 n2 n 2 2n 1 displaystyle n choose 0 n choose 2 ldots n choose 2 lfloor n 2 rfloor 2 n 1 de n N displaystyle n in mathbb N k aa 1 k 2ak a 3 3a a 3 displaystyle sum k a a 1 k 2a choose k a 3 frac 3a a 3 a v zagalnishomu viglyadi k aa 1 k a ba k b cb k c ac k a b c a b c displaystyle sum k a a 1 k a b choose a k b c choose b k c a choose c k frac a b c a b c Zgortka Vandermonda i naslidki k rm k sn k r sm n displaystyle sum k r choose m k s choose n k r s choose m n zgortka Vandermonda de m n Z displaystyle m n in mathbb Z a r s R displaystyle r s in mathbb R Ce totozhnist vihodit obchislennyam koeficiyenta pri xm n displaystyle x m n u rozkladi 1 x r 1 x s displaystyle 1 x r 1 x s z urahuvannyam totozhnosti 1 x r s 1 x r 1 x s displaystyle 1 x r s 1 x r 1 x s Suma beretsya za vsima cilimi k displaystyle k dlya yakih rm k sn k 0 displaystyle textstyle r choose m k s choose n k neq 0 Dlya dovilnih dijsnih r displaystyle r s displaystyle s chislo nenulovih dodankiv u sumi bude skinchennim n0 aa n1 a 1a 1 n nn a na 1 n an displaystyle n choose 0 a choose a n choose 1 a 1 choose a ldots 1 n n choose n a n choose a 1 n a choose n zagalnisha totozhnist i 0p 1 i pi m 1n i smsm 0 displaystyle sum i 0 p 1 i p choose i prod m 1 n i s m choose s m 0 yaksho m 1nsm lt p displaystyle sum m 1 n s m lt p n0 2 n1 2 nn 2 2nn displaystyle n choose 0 2 n choose 1 2 ldots n choose n 2 2n choose n Inshi totozhnosti k 1n 1 k 1k nk k 1n1k Hn displaystyle sum k 1 n frac 1 k 1 k n choose k sum k 1 n frac 1 k H n n e garmonichne chislo Multisekciya ryadu 1 x n displaystyle 1 x n daye totozhnist sho virazhaye sumu binomialnih koeficiyentiv iz dovilnim krokom s i zmishennyam t 0 t lt s displaystyle 0 leqslant t lt s u viglyadi skinchennoyi sumi z s dodankiv nt nt s nt 2s 1s j 0s 1 2cos pjs ncos p n 2t js displaystyle binom n t binom n t s binom n t 2s ldots frac 1 s sum j 0 s 1 left 2 cos frac pi j s right n cos frac pi n 2t j s Vikonuyutsya rivnosti n3 n n 1 n 2 2 i 2n 1 n i n i 1 n n 1 n 2 i 2n 1 n i 2n i 1 3 n3 2 n3 displaystyle begin alignedat 2 binom n 3 amp frac n n 1 n 2 color Green 2 sum i 2 n 1 n i n i 1 amp n n 1 n 2 sum i 2 n 1 n i color Green 2 n i 1 amp 3 binom n 3 2 binom n 3 end alignedat n4 n n 1 n 2 n 3 2 i 3n 1 n i n n 1 i0 1i 2i0 n n 1 n 2 n 3 i 3n 1 n i 2n n 1 i0 1i 2i0 24 n4 23 n4 displaystyle begin alignedat 2 binom n 4 amp frac n n 1 n 2 n 3 color Green 2 sum i 3 n 1 n i left n n 1 sum i 0 1 i 2 i 0 right amp n n 1 n 2 n 3 sum i 3 n 1 n i left color Green 2 n n 1 sum i 0 1 i 2 i 0 right amp 24 binom n 4 23 binom n 4 end alignedat n5 n n 1 n 2 n 3 n 4 2 i 4n 1 n i n n 1 n 2 i0 1i 3 i1 1i0i1 n n 1 n 2 n 3 n 4 i 4n 1 n i 2n n 1 n 2 i0 1i 3 i1 1i0i1 120 n5 119 n5 displaystyle begin alignedat 2 binom n 5 amp frac n n 1 n 2 n 3 n 4 color Green 2 amp sum i 4 n 1 n i left n n 1 n 2 sum i 0 1 i 3 sum i 1 1 i 0 i 1 right amp n n 1 n 2 n 3 n 4 amp sum i 4 n 1 n i left color Green 2 n n 1 n 2 sum i 0 1 i 3 sum i 1 1 i 0 i 1 right amp 120 binom n 5 119 binom n 5 end alignedat Zvidki viplivaye n3 i 2n 1 n i 2n i 1 2 i 2n 1 n i 2An1 i 11 2 displaystyle binom n 3 frac sum limits i 2 n 1 n i 2n i 1 2 frac sum limits i 2 n 1 n i left 2A n 1 binom i 1 1 right 2 n4 i 3n 1 n i 2n n 1 i0 1i 2i0 23 i 3n 1 n i 2An2 i 12 23 displaystyle binom n 4 frac sum limits i 3 n 1 n i left 2n n 1 sum limits i 0 1 i 2 i 0 right 23 frac sum limits i 3 n 1 n i left 2A n 2 binom i 1 2 right 23 n5 i 4n 1 n i 2n n 1 n 2 i0 1i 3 i1 1i0i1 119 i 4n 1 n i 2An3 i 13 119 displaystyle begin alignedat 2 amp binom n 5 frac sum limits i 4 n 1 n i left 2n n 1 n 2 sum limits i 0 1 i 3 sum limits i 1 1 i 0 i 1 right 119 amp frac sum limits i 4 n 1 n i left 2A n 3 binom i 1 3 right 119 end alignedat nk i k 1n 1 n i 2Ank 2 i 1k 2 k 1 displaystyle binom n k frac sum limits i k 1 n 1 n i left 2A n k 2 binom i 1 k 2 right k 1 de Ank displaystyle A n k kilkist rozmishen iz n po k Matrichni spivvidnoshennya Yaksho vzyati kvadratnu matricyu vidrahuvavshi N elementiv po katetah trikutnika Paskalya i povernuvshi matricyu na bud yakij z chotiroh kutiv to determinant cih chotiroh matric dorivnyuye 1 za bud yakogo N prichomu determinant matrici z vershinoyu trikutnika u verhnomu livomu kuti dorivnyuye 1 U matrici i ji displaystyle begin bmatrix tbinom i j i end bmatrix chisla na diagonali i j const displaystyle i j const povtoryuyut chisla ryadkiv trikutnika Paskalya i j 0 1 displaystyle i j 0 1 ldots Yiyi mozhna rozklasti v dobutok dvoh strogo diagonalnih matric nizhnotrikutnoyi ta oderzhuvanoyi z neyi transponuvannyam A same i ji UUT displaystyle begin bmatrix binom i j i end bmatrix UU T de U ij displaystyle U begin bmatrix tbinom i j end bmatrix Obernena matricya do U displaystyle U maye viglyad U 1 1 i j ij displaystyle U 1 begin bmatrix 1 i j binom i j end bmatrix Takim chinom matricyu obernenu do i ji displaystyle begin bmatrix tbinom i j i end bmatrix mozhna rozklasti v dobutok dvoh strogo diagonalnih matric persha matricya verhnotrikutna a druga vihodit z pershoyi transponuvannyam sho dozvolyaye dati yavnij viraz dlya obernenih elementiv i ji m n 1 k 0p 1 m n km kn displaystyle begin bmatrix binom i j i end bmatrix m n 1 sum k 0 p 1 m n binom k m binom k n de i j m n 0 p Elementi obernenoyi matrici zminyuyutsya za zmini yiyi rozmiru i na vidminu vid matrici i ji displaystyle begin bmatrix tbinom i j i end bmatrix nedostatno pripisati novij ryadok i stovpec Stovpec j matrici i ji displaystyle begin bmatrix tbinom i j i end bmatrix ye mnogochlenom stepenya j za argumentom i otzhe pershi p stovpciv utvoryuyut povnij bazis u prostori vektoriv dovzhini p 1 chiyi koordinati mozhna interpolyuvati mnogochlenom stepenya rivnogo abo menshogo nizh p 1 Nizhnij ryadok matrici i ji m n 1 displaystyle begin bmatrix binom i j i end bmatrix m n 1 ortogonalnij do bud yakogo takogo vektora i ji p n 1 k 0p 1 p n kp kn 1 p n pn displaystyle begin bmatrix binom i j i end bmatrix p n 1 sum k 0 p 1 p n binom k p binom k n 1 p n binom p n n 0p 1 p n pn Pa n 0 displaystyle sum n 0 p 1 p n binom p n P a n 0 pri a lt p displaystyle a lt p de Pa n displaystyle P a n mnogochlen stepenya a displaystyle a Yaksho dovilnij vektor dovzhini p 1 displaystyle p 1 mozhna interpolyuvati mnogochlenom stepenya i lt p displaystyle i lt p to skalyarnij dobutok z ryadkami i 1 i 2 p displaystyle i 1 i 2 dots p numeraciya z 0 matrici i ji m n 1 displaystyle begin bmatrix binom i j i end bmatrix m n 1 dorivnyuye nulyu Vikoristovuyuchi totozhnist vishe i rivnist odinici skalyarnogo dobutku nizhnogo ryadka matrici i ji m n 1 displaystyle begin bmatrix binom i j i end bmatrix m n 1 na ostannij stovpec matrici i ji displaystyle begin bmatrix tbinom i j i end bmatrix mayemo n 0p 1 p n pn np p displaystyle sum n 0 p 1 p n binom p n n p p Dlya pokaznika bilshogo vid p mozhna zadati rekurentnu formulu n 0p 1 p n pn np a p P2a p fa p displaystyle sum n 0 p 1 p n binom p n n p a p P 2a p f a p de mnogochlen P2a 2 p x 1pxP2a x a 0 P0 p 1 displaystyle P 2a 2 p sum x 1 p x P 2a x quad a geqslant 0 quad P 0 p 1 Dlya dovedennya spershu dovoditsya totozhnist fa p 1 x 0a p 1 x 1fa x p displaystyle f a p 1 sum x 0 a p 1 x 1 f a x p Yaksho potribno znajti formulu ne dlya vsih pokaznikiv stepenya to P2a p p2a p aa Qa 1 p a gt 0 displaystyle P 2a p frac p 2 a binom p a a Q a 1 p quad a gt 0 Starshij koeficiyent Qa 1 p displaystyle Q a 1 p dorivnyuye 1 shob znajti inshi koeficiyenti znadobitsya a 1 displaystyle a 1 znachen Qa 1 p p p 1 Ta 3 p displaystyle Q a 1 p p p 1 T a 3 p dlya a 1 mod2 a 3 displaystyle a equiv 1 pmod 2 a geqslant 3 Ciloznachni mnogochleni Binomialni koeficiyenti x0 1 x1 x x2 x22 x2 displaystyle tbinom x 0 1 tbinom x 1 x tbinom x 2 tfrac x 2 2 tfrac x 2 ye ciloznachnimi mnogochlenami vid x displaystyle x tobto nabuvayut cilih znachen za cilih znachen x displaystyle x ce nevazhko zrozumiti napriklad za trikutnikom Paskalya Bilsh togo voni utvoryuyut bazis ciloznachnih mnogochleniv u yakomu vsi ciloznachni mnogochleni virazhayutsya yak linijni kombinaciyi z cilimi koeficiyentami Razom z tim standartnij bazis 1 x x2 displaystyle 1 x x 2 ne dozvolyaye viraziti vsih cilochiselnih mnogochleniv yaksho vikoristovuvati tilki cili koeficiyenti oskilki vzhe x2 x22 x2 displaystyle tbinom x 2 tfrac x 2 2 tfrac x 2 maye drobovi koeficiyenti pri stepenyah x displaystyle x Cej rezultat uzagalnyuyetsya na mnogochleni bagatoh zminnih A same yaksho mnogochlen R x1 xm displaystyle R x 1 dots x m stepenya k displaystyle k maye dijsni koeficiyenti i nabuvaye cilih znachen za cilih znachen zminnih to R x1 xm P x11 x1k xm1 xmk displaystyle R x 1 dots x m P left binom x 1 1 dots binom x 1 k dots binom x m 1 dots binom x m k right de P displaystyle P mnogochlen iz cilimi koeficiyentami Asimptotika i ocinki 2nn 22npn displaystyle 2n choose n sim frac 2 2n sqrt pi n k 0m nk n n 2 m 22n 3 displaystyle sum k 0 m n choose k leq frac n n 2 m 2 2 n 3 pri m n 2 displaystyle m leq n 2 nerivnist Chebisheva k 0m nk 2nH m n displaystyle sum k 0 m n choose k leq 2 nH m n de H x xlog2 x 1 x log2 1 x displaystyle H x x log 2 x 1 x log 2 1 x entropiya k 0n 2 l nk 2ne 2l2 n displaystyle sum k 0 n 2 lambda n choose k leq 2 n e 2 lambda 2 n nerivnist Chernova Algoritmi obchislennyaBinomialni koeficiyenti mozhut buti obchisleni za dopomogoyu totozhnosti nk n 1k n 1k 1 displaystyle n choose k n 1 choose k n 1 choose k 1 yaksho na kozhnomu kroci zberigati znachennya nk displaystyle n choose k dlya k 0 1 n displaystyle k 0 1 dots n Cej algoritm osoblivo efektivnij yaksho neobhidno otrimati vsi znachennya nk displaystyle n choose k pri fiksovanomu n displaystyle n Algoritm potrebuye O n displaystyle O n pam yati O n2 displaystyle O n 2 dlya obchislennya vsiyeyi tablici i O n2 displaystyle O n 2 chasu Inshij sposib gruntuyetsya na totozhnosti nk nn k n 1k displaystyle n choose k frac n n k n 1 choose k Vin dozvolyaye obchisliti znachennya nk displaystyle n choose k pri fiksovanomu k displaystyle k Algoritm potrebuye O 1 displaystyle O 1 pam yati i O k displaystyle O k chasu UzagalnennyaOskilki dlya n 1 N n G n 1 displaystyle n 1 in mathbb N n Gamma n 1 to znachennya binomialnogo koeficiyenta mozhna viznachiti dlya usih kompleksnih chisel n C displaystyle n in mathbb C ta k C displaystyle k in mathbb C nk G n 1 G k 1 G n k 1 displaystyle n choose k frac Gamma n 1 Gamma k 1 Gamma n k 1 Yavni formuli dlya obchislennya binomialnih koeficiyentiv dlya cilih chisel n displaystyle n ta k displaystyle k nk n k n k displaystyle n choose k frac n k n k dlya 0 k n displaystyle 0 leq k leq n nk 0 displaystyle n choose k 0 dlya k lt 0 displaystyle k lt 0 abo 0 n lt k displaystyle 0 leq n lt k nk 1 k n k 1k displaystyle n choose k 1 k n k 1 choose k dlya n lt 0 k displaystyle n lt 0 leq k Binomialni koeficiyenti chasto zustrichayutsya v kombinatornih zadachah i teoriyi imovirnostej Uzagalnennyam binomialnogo koeficiyenta ye polinomialnij koeficiyent Generaciya na C include lt iostream gt include lt string gt using namespace std void C int n int m int startAt 1 string s for int i startAt i lt n m 1 i if 1 m cout lt lt s char i 0 lt lt endl else C n m 1 i 1 s char i 0 int main C 7 3 return 0 Div takozhBinom Gaussovi binomialni koeficiyenti Centralnij binomialnij koeficiyent Funkciya fuscPrimitki habr com 30 listopada 2020 Arhiv originalu za 25 zhovtnya 2021 Procitovano 27 bereznya 2021 Prasolov V V Glava 12 Celoznachnye mnogochleny 1 M MCNMO 1999 2001 2003 z dzherela 21 sichnya 2022 Yu Matiyasevich Desyataya problema Gilberta Nauka 1993 S 20 185 194 DzherelaZavalo S T 1972 Elementi analizu Algebra mnogochleniv Kiyiv Radyanska shkola s 462 ukr