Біноміальні коефіцієнти розташовані у вигляді трикутника Паскаля . Візуалізація біноміальних коефіцієнтів до 4 степеня Біноміальні коефіцієнти — коефіцієнти в розкладі ( 1 + x ) n {\displaystyle \ (1+x)^{n}} по степенях x {\displaystyle \ x} (так званий біном Ньютона ):
( 1 + x ) n = ( n 0 ) + ( n 1 ) x + ( n 2 ) x 2 + ⋯ + ( n n ) x n = ∑ k = 0 n ( n k ) x k . {\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}.} Біноміальний коефіцієнт є узагальненням кількості невпорядкованих виборів C n k {\displaystyle C_{n}^{k}} , що визначена тільки для невід'ємних цілих чисел n {\displaystyle n} , k {\displaystyle k} , тобто n + 1 ∈ N {\displaystyle \ n+1\in \mathbb {N} } та k + 1 ∈ N . {\displaystyle \ k+1\in \mathbb {N} .} У явному вигляді для 0 ≤ k ≤ n {\displaystyle 0\leq k\leq n} :
( n k ) = C n k = n ! k ! ( n − k ) ! {\displaystyle {n \choose k}=C_{n}^{k}={\frac {n!}{k!\;(n-k)!}}} , де n ! {\displaystyle n!} та k ! {\displaystyle k!} — факторіали чисел n {\displaystyle n} і k {\displaystyle k} .
Обчислюючи коефіцієнти в розкладі ( 1 + x ) n {\displaystyle (1+x)^{n}} у степеневий ряд, можна отримати явні формули для біноміальних коефіцієнтів ( n k ) {\displaystyle \textstyle {\binom {n}{k}}} .
Для всіх дійсних чисел n і цілих чисел k :
( n k ) = { n ( n − 1 ) ( n − 2 ) ⋅ … ⋅ ( n − k + 1 ) k ! , k ⩾ 0 , 0 , k < 0 , {\displaystyle {\binom {n}{k}}={\begin{cases}{\frac {n(n-1)(n-2)\cdot \ldots \cdot (n-k+1)}{k!}},&k\geqslant 0,\\0,&k<0,\end{cases}}} де k ! {\displaystyle k!} позначає факторіал числа k .
Для невід'ємних цілих n і k також справедливі формули:
( n k ) = { n ! k ! ( n − k ) ! , 0 ⩽ k ⩽ n , 0 , k > n . {\displaystyle {\binom {n}{k}}={\begin{cases}{\frac {n!}{k!(n-k)!}},&0\leqslant k\leqslant n,\\0,&k>n.\end{cases}}} Для цілих від'ємних показників коефіцієнти розкладу бінома ( 1 + x ) − n {\displaystyle (1+x)^{-n}} рівні
( − n k ) = { ( − 1 ) k ⋅ ( n + k − 1 ) ! k ! ( n − 1 ) ! , k ⩾ 0 , 0 , k < 0. {\displaystyle {\binom {-n}{k}}={\begin{cases}(-1)^{k}\cdot {\frac {(n+k-1)!}{k!(n-1)!}},&k\geqslant 0,\\0,&k<0.\end{cases}}} Тотожність ( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}} дозволяє розташувати біноміальні коефіцієнти для невід'ємних n {\displaystyle n} , k {\displaystyle k} у вигляді трикутника Паскаля, в якому кожне число рівне сумі двох, що стоять на рядок вище:
n = 0 : 1 n = 1 : 1 1 n = 2 : 1 2 1 n = 3 : 1 3 3 1 n = 4 : 1 4 6 4 1 ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{matrix}n=0:&&&&&1&&&&\\n=1:&&&&1&&1&&&\\n=2:&&&1&&2&&1&&\\n=3:&&1&&3&&3&&1&\\n=4:&1&&4&&6&&4&&1\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\end{matrix}}} Трикутна таблиця, запропонована Паскалем в «Трактаті про арифметичний трикутник» (1654 ), відрізняється від описаної тут поворотом на 45°. Таблиці для зображення біноміальних коефіцієнтів були відомі й раніше.
Для фіксованого значення n твірною функцією послідовності біноміальних коефіцієнтів ( n 0 ) , ( n 1 ) , ( n 2 ) , {\displaystyle {\tbinom {n}{0}},\;{\tbinom {n}{1}},\;{\tbinom {n}{2}},} … є
∑ k = 0 ∞ ( n k ) x k = ( 1 + x ) n . {\displaystyle \sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}=(1+x)^{n}.} Для фіксованого значення k твірною функцією послідовності коефіцієнтів ( 0 k ) , ( 1 k ) , ( 2 k ) , {\displaystyle {\tbinom {0}{k}},\;{\tbinom {1}{k}},\;{\tbinom {2}{k}},} … є
∑ n ( n k ) y n = y k ( 1 − y ) k + 1 {\displaystyle \sum _{n}{\binom {n}{k}}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}} . Двовимірною твірною функцією біноміальних коефіцієнтів ( n k ) {\displaystyle {\tbinom {n}{k}}} для цілих n , k {\displaystyle n,k} є
∑ n , k ( n k ) x k y n = 1 1 − y − x y , {\displaystyle \sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}},} або ∑ n = 0 ∞ ∑ k = 0 n ( n k ) x k y n = 1 1 − y − x y . {\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}.} Із теореми Люка випливає, що:
коефіцієнт ( n k ) {\displaystyle \textstyle {\binom {n}{k}}} непарний ⟺ {\displaystyle \iff } в двійкового запису числа k одиниці не стоять у тих розрядах, де в числі n стоять нулі; коефіцієнт ( n k ) {\displaystyle \textstyle {\binom {n}{k}}} не кратний простому число p ⟺ {\displaystyle \iff } при записі числа k в системі числення з основою p , всі розряди не перевищують відповідних розрядів числа n ; у послідовності біноміальних коефіцієнтів ( n 0 ) , ( n 1 ) , … , ( n n ) {\displaystyle \textstyle {\binom {n}{0}},\;{\binom {n}{1}},\;\ldots ,\;{\binom {n}{n}}} : всі числа не кратні заданому простому p ⟺ {\displaystyle \iff } число n {\displaystyle n} можна подати у вигляді m p k − 1 {\displaystyle mp^{k}-1} , де натуральне число m < p {\displaystyle m<p} ; всі числа, крім першого й останнього, кратні даному простому p ⟺ {\displaystyle \iff } n = p k {\displaystyle n=p^{k}} ; кількість непарних чисел дорівнює степеню двійки, показник якої дорівнює кількості одиниць у двійковому записі числа n ; парних і непарних чисел не може бути порівну; кількість чисел, не кратних простому p , дорівнює ( a 1 + 1 ) ∗ ⋯ ∗ ( a m + 1 ) {\displaystyle (a_{1}+1)*\dots *(a_{m}+1)} , де числа a 1 , … , a m {\displaystyle a_{1},\;\ldots ,a_{m}} — розряди p -кового запису числа n ; а число m = ⌊ log p n ⌋ + 1 , {\displaystyle \textstyle m=\lfloor \log _{p}{n}\rfloor +1,} де ⌊ ⋅ ⌋ {\displaystyle \lfloor \cdot \rfloor } — функція «підлоги» — це довжина даного запису. ( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}} ( n k ) = n n − k ( n − 1 k ) {\displaystyle {n \choose k}={\frac {n}{n-k}}{n-1 \choose k}} ( n 0 ) + ( n 1 ) + ⋯ + ( n n ) = 2 n {\displaystyle {n \choose 0}+{n \choose 1}+\cdots +{n \choose n}=2^{n}} ( n 0 ) + ( n 2 ) + ⋯ + ( n 2 ⌊ n / 2 ⌋ ) = 2 n − 1 {\displaystyle {n \choose 0}+{n \choose 2}+\cdots +{n \choose 2\lfloor n/2\rfloor }=2^{n-1}} ( n 0 ) 2 + ( n 1 ) 2 + ⋯ + ( n n ) 2 = ( 2 n n ) {\displaystyle {n \choose 0}^{2}+{n \choose 1}^{2}+\cdots +{n \choose n}^{2}={2n \choose n}} ∑ k = 0 n ( r m + k ) ( s n − k ) = ( r + s m + n ) {\displaystyle \sum _{k=0}^{n}{r \choose m+k}{s \choose n-k}={r+s \choose m+n}} (згортка Вандермонда ) Біном Ньютона і наслідки [ ред. | ред. код ] ( n 0 ) + ( n 1 ) + … + ( n n ) = 2 n , {\displaystyle {n \choose 0}+{n \choose 1}+\ldots +{n \choose n}=2^{n},} де n ∈ N . {\displaystyle n\in \mathbb {N} .} ∑ i + j = m ( n j ) ( n i ) ( − 1 ) j = { ( n m / 2 ) , якщо m ≡ 0 ( mod 2 ) , 0 , якщо m ≡ 1 ( mod 2 ) . {\displaystyle \sum _{i+j=m}{\binom {n}{j}}{\binom {n}{i}}(-1)^{j}={\begin{cases}{\binom {n}{m/2}},&{\text{якщо}}\ m\equiv 0{\pmod {2}},\\0,&{\text{якщо}}\ m\equiv 1{\pmod {2}}.\end{cases}}} ∑ j = k n ( n j ) ( − 1 ) j = ( − 1 ) k ( n − 1 k − 1 ) . {\displaystyle \sum _{j=k}^{n}{\binom {n}{j}}(-1)^{j}=(-1)^{k}{\binom {n-1}{k-1}}.} ( n 0 ) − ( n 1 ) + … + ( − 1 ) n ( n n ) = 0 , {\displaystyle {n \choose 0}-{n \choose 1}+\ldots +(-1)^{n}{n \choose n}=0,} де n ∈ N . {\displaystyle n\in \mathbb {N} .} Сильніша тотожність: ( n 0 ) + ( n 2 ) + … + ( n 2 ⌊ n / 2 ⌋ ) = 2 n − 1 , {\displaystyle {n \choose 0}+{n \choose 2}+\ldots +{n \choose 2\lfloor n/2\rfloor }=2^{n-1},} де n ∈ N . {\displaystyle n\in \mathbb {N} .} ∑ k = − a a ( − 1 ) k ( 2 a k + a ) 3 = ( 3 a ) ! ( a ! ) 3 , {\displaystyle \sum _{k=-a}^{a}(-1)^{k}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}},} а в загальнішому вигляді
∑ k = − a a ( − 1 ) k ( a + b a + k ) ( b + c b + k ) ( c + a c + 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!}}.} Згортка Вандермонда і наслідки [ ред. | ред. код ] ∑ k ( r m + k ) ( s n − k ) = ( r + s m + n ) {\displaystyle \sum _{k}{r \choose m+k}{s \choose n-k}={r+s \choose m+n}} (згортка Вандермонда ), де m , n ∈ Z , {\displaystyle m,n\in \mathbb {Z} ,} а r , s ∈ R . {\displaystyle r,s\in \mathbb {R} .} Це тотожність виходить обчисленням коефіцієнта при x m + n {\displaystyle x^{m+n}} у розкладі ( 1 + x ) r ( 1 + x ) s {\displaystyle (1+x)^{r}(1+x)^{s}} з урахуванням тотожності ( 1 + x ) r + s = ( 1 + x ) r ( 1 + x ) s . {\displaystyle (1+x)^{r+s}=(1+x)^{r}(1+x)^{s}.} Сума береться за всіма цілими k {\displaystyle k} , для яких ( r m + k ) ( s n − k ) ≠ 0. {\displaystyle \textstyle {r \choose m+k}{s \choose n-k}\neq 0.} Для довільних дійсних r {\displaystyle r} , s {\displaystyle s} число ненульових доданків у сумі буде скінченним.
( n 0 ) ( a a ) − ( n 1 ) ( a + 1 a ) + … + ( − 1 ) n ( n n ) ( a + n a ) = ( − 1 ) n ( a n ) {\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}} . загальніша тотожність: ∑ i = 0 p ( − 1 ) i ( p i ) ∏ m = 1 n ( i + s m s m ) = 0 {\displaystyle \sum _{i=0}^{p}(-1)^{i}{p \choose i}\prod _{m=1}^{n}{i+s_{m} \choose s_{m}}=0} , якщо ∑ m = 1 n s m < p {\displaystyle \sum _{m=1}^{n}{s_{m}}<p} . ( n 0 ) 2 + ( n 1 ) 2 + … + ( n n ) 2 = ( 2 n n ) . {\displaystyle {n \choose 0}^{2}+{n \choose 1}^{2}+\ldots +{n \choose n}^{2}={2n \choose n}.} ∑ k = 1 n ( − 1 ) k − 1 k ( n k ) = ∑ k = 1 n 1 k = H n {\displaystyle \sum _{k=1}^{n}{\frac {(-1)^{k-1}}{k}}{n \choose k}=\sum _{k=1}^{n}{\frac {1}{k}}=H_{n}} — n - е гармонічне число . Мультисекція ряду ( 1 + x ) n {\displaystyle (1+x)^{n}} дає тотожність, що виражає суму біноміальних коефіцієнтів із довільним кроком s і зміщенням t ( 0 ⩽ t < s ) {\displaystyle (0\leqslant t<s)} у вигляді скінченної суми з s доданків: ( n t ) + ( n t + s ) + ( n t + 2 s ) + … = 1 s ∑ j = 0 s − 1 ( 2 cos π j s ) n cos π ( n − 2 t ) j s . {\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}}.} ( n 3 ) = n ( n − 1 ) ( n − 2 ) 2 − ∑ i = 2 n − 1 ( n − i ) ( n − i + 1 ) = = n ( n − 1 ) ( n − 2 ) − ∑ i = 2 n − 1 ( n − i ) ( 2 n − i + 1 ) = = 3 ( n 3 ) − 2 ( n 3 ) ; {\displaystyle {\begin{alignedat}{2}{\binom {n}{3}}&={\frac {n(n-1)(n-2)}{\color {Green}2}}-\sum _{i=2}^{n-1}{(n-i)(n-i+1)}=\\&=n(n-1)(n-2)-\sum _{i=2}^{n-1}{(n-i)({\color {Green}2}n-i+1)}=\\&=3{\binom {n}{3}}-2{\binom {n}{3}};\\\end{alignedat}}} ( n 4 ) = n ( n − 1 ) ( n − 2 ) ( n − 3 ) 2 − ∑ i = 3 n − 1 ( n − i ) ( n ( n − 1 ) − ∑ i 0 = 1 i − 2 i 0 ) = = n ( n − 1 ) ( n − 2 ) ( n − 3 ) − ∑ i = 3 n − 1 ( n − i ) ( 2 n ( n − 1 ) − ∑ i 0 = 1 i − 2 i 0 ) = = 24 ( n 4 ) − 23 ( n 4 ) ; {\displaystyle {\begin{alignedat}{2}{\binom {n}{4}}&={\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)}=\\&=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)}=\\&=24{\binom {n}{4}}-23{\binom {n}{4}};\\\end{alignedat}}} ( n 5 ) = n ( n − 1 ) ( n − 2 ) ( n − 3 ) ( n − 4 ) 2 − − ∑ i = 4 n − 1 ( n − i ) ( n ( n − 1 ) ( n − 2 ) − ∑ i 0 = 1 i − 3 ∑ i 1 = 1 i 0 i 1 ) = = n ( n − 1 ) ( n − 2 ) ( n − 3 ) ( n − 4 ) − − ∑ i = 4 n − 1 ( n − i ) ( 2 n ( n − 1 ) ( n − 2 ) − ∑ i 0 = 1 i − 3 ∑ i 1 = 1 i 0 i 1 ) = = 120 ( n 5 ) − 119 ( n 5 ) . {\displaystyle {\begin{alignedat}{2}{\binom {n}{5}}&={\frac {n(n-1)(n-2)(n-3)(n-4)}{\color {Green}2}}-\\&-\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)}=\\&=n(n-1)(n-2)(n-3)(n-4)-\\&-\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)}=\\&=120{\binom {n}{5}}-119{\binom {n}{5}}.\end{alignedat}}} Звідки випливає:
( n 3 ) = ∑ i = 2 n − 1 ( n − i ) ( 2 n − i + 1 ) 2 = ∑ i = 2 n − 1 ( n − i ) ( 2 A n 1 − ( i − 1 1 ) ) 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}};} ( n 4 ) = ∑ i = 3 n − 1 ( n − i ) ( 2 n ( n − 1 ) − ∑ i 0 = 1 i − 2 i 0 ) 23 = ∑ i = 3 n − 1 ( n − i ) ( 2 A n 2 − ( i − 1 2 ) ) 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}};} ( n 5 ) = ∑ i = 4 n − 1 ( n − i ) ( 2 n ( n − 1 ) ( n − 2 ) − ∑ i 0 = 1 i − 3 ∑ i 1 = 1 i 0 i 1 ) 119 = = ∑ i = 4 n − 1 ( n − i ) ( 2 A n 3 − ( i − 1 3 ) ) 119 ; {\displaystyle {\begin{alignedat}{2}&{\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}}=\\&={\frac {\sum \limits _{i=4}^{n-1}{(n-i)\left(2A_{n}^{3}-{\binom {i-1}{3}}\right)}}{119}};\\\end{alignedat}}} ( n k ) = ∑ i = k − 1 n − 1 ( n − i ) ( 2 A n k − 2 − ( i − 1 k − 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}},} де A n k {\displaystyle A_{n}^{k}} — кількість розміщень із n по k .
Матричні співвідношення [ ред. | ред. код ] Якщо взяти квадратну матрицю, відрахувавши N елементів по катетах трикутника Паскаля і повернувши матрицю на будь-який з чотирьох кутів, то детермінант цих чотирьох матриць дорівнює ±1 за будь-якого N , причому детермінант матриці з вершиною трикутника у верхньому лівому куті дорівнює 1.
У матриці [ ( i + j i ) ] {\displaystyle {\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}} числа на діагоналі i + j = c o n s t {\displaystyle i+j=const} повторюють числа рядків трикутника Паскаля ( i , j = 0 , 1 , … ) {\displaystyle (i,j=0,1,\ldots )} . Її можна розкласти в добуток двох строго діагональних матриць: нижньотрикутної та одержуваної з неї транспонуванням. А саме:
[ ( i + j i ) ] = U U T , {\displaystyle {\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}=UU^{T},} де U = [ ( i j ) ] {\displaystyle U={\begin{bmatrix}{\tbinom {i}{j}}\end{bmatrix}}} . Обернена матриця до U {\displaystyle U} має вигляд:
U − 1 = [ ( − 1 ) i + j ( i j ) ] . {\displaystyle U^{-1}={\begin{bmatrix}(-1)^{i+j}{\binom {i}{j}}\end{bmatrix}}.} Таким чином, матрицю, обернену до [ ( i + j i ) ] {\displaystyle {\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}} , можна розкласти в добуток двох строго діагональних матриць: перша матриця — верхньотрикутна, а друга виходить з першої транспонуванням, що дозволяє дати явний вираз для обернених елементів:
[ ( i + j i ) ] m , n − 1 = ∑ k = 0 p ( − 1 ) m + n ( k m ) ( k n ) {\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}}} , де i , j , m , n = 0..p . Елементи оберненої матриці змінюються за зміни її розміру і, на відміну від матриці [ ( i + j i ) ] {\displaystyle {\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}} , недостатньо приписати новий рядок і стовпець. Стовпець j матриці [ ( i + j i ) ] {\displaystyle {\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}} є многочленом степеня j за аргументом i , отже, перші p стовпців утворюють повний базис у просторі векторів довжини p +1, чиї координати можна інтерполювати многочленом степеня рівного або меншого ніж p -1. Нижній рядок матриці [ ( i + j i ) ] m , n − 1 {\displaystyle {\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{m,n}^{-1}} ортогональний до будь-якого такого вектора.
[ ( i + j i ) ] p , n − 1 = ∑ k = 0 p ( − 1 ) p + n ( k p ) ( k n ) = ( − 1 ) p + n ( p n ) {\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 = 0 p ( − 1 ) p + n ( p n ) P a ( n ) = 0 {\displaystyle \sum _{n=0}^{p}(-1)^{p+n}{\binom {p}{n}}{P}_{a}(n)=0} при a < p {\displaystyle a<p} , де P a ( n ) {\displaystyle {P}_{a}(n)} многочлен степеня a {\displaystyle a} . Якщо довільний вектор довжини p + 1 {\displaystyle p+1} можна інтерполювати многочленом степеня i < p {\displaystyle i<p} , то скалярний добуток з рядками i + 1 , i + 2 , … , p {\displaystyle i+1,i+2,\dots ,p} (нумерація з 0) матриці [ ( i + j i ) ] m , n − 1 {\displaystyle {\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{m,n}^{-1}} дорівнює нулю. Використовуючи тотожність вище і рівність одиниці скалярного добутку нижнього рядка матриці [ ( i + j i ) ] m , n − 1 {\displaystyle {\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{m,n}^{-1}} на останній стовпець матриці [ ( i + j i ) ] {\displaystyle {\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}} , маємо:
∑ n = 0 p ( − 1 ) p + n ( p n ) n p = p ! . {\displaystyle \sum _{n=0}^{p}(-1)^{p+n}{\binom {p}{n}}{n}^{p}=p!.} Для показника, більшого від p , можна задати рекурентну формулу:
∑ n = 0 p ( − 1 ) p + n ( p n ) n p + a = p ! P 2 a ( p ) = f a ( p ) , {\displaystyle \sum _{n=0}^{p}(-1)^{p+n}{\binom {p}{n}}{n}^{p+a}=p!{P}_{2a}(p)={f}_{a}(p),} де многочлен
P 2 a + 2 ( p ) = ∑ x = 1 p x P 2 a ( x ) ; a ⩾ 0 ; P 0 ( p ) = 1. {\displaystyle {P}_{2a+2}(p)=\sum _{x=1}^{p}x{P}_{2a}(x);\quad a\geqslant 0;\quad {P}_{0}(p)=1.} Для доведення спершу доводиться тотожність:
f a ( p + 1 ) = ∑ x = 0 a ( p + 1 ) x + 1 f a − x ( p ) . {\displaystyle {f}_{a}(p+1)=\sum _{x=0}^{a}{(p+1)}^{x+1}{f}_{a-x}(p).} Якщо потрібно знайти формулу не для всіх показників степеня, то
P 2 a ( p ) = p 2 a ( p + a a ) Q a − 1 ( p ) ; a > 0. {\displaystyle {P}_{2a}(p)={\frac {p}{{2}^{a}}}{\binom {p+a}{a}}{Q}_{a-1}(p);\quad a>0.} Старший коефіцієнт Q a − 1 ( p ) {\displaystyle {Q}_{a-1}(p)} дорівнює 1, щоб знайти інші коефіцієнти, знадобиться a − 1 {\displaystyle a-1} значень:
Q a − 1 ( p ) = p ( p + 1 ) T a − 3 ( p ) {\displaystyle {Q}_{a-1}(p)=p(p+1){T}_{a-3}(p)} для a ≡ 1 ( mod 2 ) ; a ⩾ 3. {\displaystyle a\equiv 1{\pmod {2}};a\geqslant 3.} Цілозначні многочлени [ ред. | ред. код ] Біноміальні коефіцієнти ( x 0 ) = 1 , ( x 1 ) = x , ( x 2 ) = x 2 2 − x 2 , {\displaystyle {\tbinom {x}{0}}=1,{\tbinom {x}{1}}=x,{\tbinom {x}{2}}={\tfrac {x^{2}}{2}}-{\tfrac {x}{2}},} … є цілозначними многочленами від x {\displaystyle x} , тобто, набувають цілих значень за цілих значень x , {\displaystyle x,} — це неважко зрозуміти, наприклад, за трикутником Паскаля. Більш того, вони утворюють базис цілозначних многочленів, у якому всі цілозначні многочлени виражаються як лінійні комбінації з цілими коефіцієнтами[2] .
Разом з тим, стандартний базис 1 , x , x 2 , {\displaystyle 1,x,x^{2},} … не дозволяє виразити всіх цілочисельних многочленів, якщо використовувати тільки цілі коефіцієнти, оскільки вже ( x 2 ) = x 2 2 − x 2 {\displaystyle {\tbinom {x}{2}}={\tfrac {x^{2}}{2}}-{\tfrac {x}{2}}} має дробові коефіцієнти при степенях x {\displaystyle x} .
Цей результат узагальнюється на многочлени багатьох змінних. А саме, якщо многочлен R ( x 1 , … , x m ) {\displaystyle R(x_{1},\dots ,x_{m})} степеня k {\displaystyle k} має дійсні коефіцієнти і набуває цілих значень за цілих значень змінних, то
R ( x 1 , … , x m ) = P ( ( x 1 1 ) , … , ( x 1 k ) , … , ( x m 1 ) , … , ( x m k ) ) , {\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),} де P {\displaystyle P} — многочлен із цілими коефіцієнтами.[3]
Асимптотика і оцінки [ ред. | ред. код ] ( 2 n n ) ∼ 2 2 n π n {\displaystyle {2n \choose n}\sim {\frac {2^{2n}}{\sqrt {\pi n}}}} ∑ k = 0 m ( n k ) ≤ n ( n / 2 − m ) 2 2 n − 3 {\displaystyle \sum _{k=0}^{m}{n \choose k}\leq {\frac {n}{(n/2-m)^{2}}}2^{n-3}} при m ≤ n / 2 {\displaystyle m\leq n/2} (нерівність Чебишева ) ∑ k = 0 m ( n k ) ≤ 2 n H ( m / n ) {\displaystyle \sum _{k=0}^{m}{n \choose k}\leq 2^{nH(m/n)}} (ентропійна оцінка ), де H ( x ) = − x log 2 x − ( 1 − x ) log 2 ( 1 − x ) {\displaystyle H(x)=-x\log _{2}x-(1-x)\log _{2}(1-x)} — ентропія . ∑ k = 0 n / 2 − λ ( n k ) ≤ 2 n e − 2 λ 2 / n {\displaystyle \sum _{k=0}^{n/2-\lambda }{n \choose k}\leq 2^{n}e^{-2\lambda ^{2}/n}} (нерівність Чернова ) Алгоритми обчислення [ ред. | ред. код ] Біноміальні коефіцієнти можуть бути обчислені за допомогою тотожності ( n k ) = ( n − 1 k ) + ( n − 1 k − 1 ) {\displaystyle {n \choose k}={n-1 \choose k}+{n-1 \choose k-1}} , якщо на кожному кроці зберігати значення ( n k ) {\displaystyle {n \choose k}} для k = 0 , 1 , … , n {\displaystyle k=0,1,\dots ,n} . Цей алгоритм особливо ефективний, якщо необхідно отримати всі значення ( n k ) {\displaystyle {n \choose k}} при фіксованому n {\displaystyle n} . Алгоритм потребує O ( n ) {\displaystyle \ O(n)} пам'яті ( O ( n 2 ) {\displaystyle \ O(n^{2})} для обчислення всієї таблиці) і O ( n 2 ) {\displaystyle \ O(n^{2})} часу. Інший спосіб ґрунтується на тотожності ( n k ) = n n − k ( n − 1 k ) {\displaystyle {n \choose k}={\frac {n}{n-k}}{n-1 \choose k}} . Він дозволяє обчислити значення ( n k ) {\displaystyle {n \choose k}} при фіксованому k {\displaystyle k} . Алгоритм потребує O ( 1 ) {\displaystyle \ O(1)} пам'яті і O ( k ) {\displaystyle \ O(k)} часу. Оскільки для n + 1 ∈ N : n ! = Γ ( n + 1 ) {\displaystyle \ n+1\in \mathbb {N} :\ n!=\Gamma (n+1)} , то значення біноміального коефіцієнта можна визначити для усіх комплексних чисел n ∈ C {\displaystyle \ n\in \mathbb {C} } та k ∈ C {\displaystyle \ k\in \mathbb {C} } :
( n k ) = Γ ( n + 1 ) Γ ( k + 1 ) Γ ( n − k + 1 ) {\displaystyle {n \choose k}={\frac {\Gamma (n+1)}{\Gamma (k+1)\Gamma (n-k+1)}}} Явні формули для обчислення біноміальних коефіцієнтів для цілих чисел n {\displaystyle \ n} та k {\displaystyle \ k} :
( n k ) = n ! k ! ( n − k ) ! {\displaystyle {n \choose k}={\frac {n!}{k!\;(n-k)!}}} для 0 ≤ k ≤ n {\displaystyle 0\leq k\leq n} ; ( n k ) = 0 {\displaystyle {n \choose k}=0} для k < 0 {\displaystyle \ k<0} або 0 ≤ n < k {\displaystyle 0\leq n<k} ; ( n k ) = ( − 1 ) k ( − n + k − 1 k ) {\displaystyle {n \choose k}=(-1)^{k}{-n+k-1 \choose k}} для n < 0 ≤ k {\displaystyle n<0\leq k} . Біноміальні коефіцієнти часто зустрічаються в комбінаторних задачах і теорії імовірностей .
Узагальненням біноміального коефіцієнта є поліноміальний коефіцієнт .
#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. (укр.) Література та бібліографія
Тематичні сайти Словники та енциклопедії Довідкові видання Нормативний контроль