Биномиальный коэффициент

Биномиальный коэффициент — коэффициент перед членом разложения бинома Ньютона $(1+x{)}^n$$(1+x)^{n}$ по степеням $x$$x$. Коэффициент при $x^k$$x^{k}$ обозначается $(\genfrac{}{}{0ex}{}{n}{k})$$\textstyle {\binom {n}{k}}$ или $C_n^k$$\textstyle C_n^k$ и читается «биномиальный коэффициент из $n$$n$ по $k$$k$» (или «число сочетаний из $n$$n$ по $k$$k$»):

$(1+x{)}^n=(\genfrac{}{}{0ex}{}{n}{0})+(\genfrac{}{}{0ex}{}{n}{1})x+(\genfrac{}{}{0ex}{}{n}{2})x^2+\dots <!--\; \dots \; -->+(\genfrac{}{}{0ex}{}{n}{n})x^n=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})x^k$$(1+x)^{n}={\binom {n}{0}}+{\binom {n}{1}}x+{\binom {n}{2}}x^{2}+\ldots +{\binom {n}{n}}x^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}$

для натуральных степеней $n$$n$.

Биномиальные коэффициенты могут быть также определены для произвольных действительных показателей $n$$n$. В случае произвольного действительного числа $n$$n$ биномиальные коэффициенты определяются как коэффициенты разложения выражения $(1+x{)}^n$$(1+x)^{n}$ в бесконечный степенной ряд:

$(1+x{)}^n=\underset{k=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})x^k$$(1+x)^{n}=\sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}$,

где в случае неотрицательных целых $n$$n$ все коэффициенты $(\genfrac{}{}{0ex}{}{n}{k})$$\textstyle {\binom {n}{k}}$ при $k>n$$k>n$ обращаются в нуль и поэтому данное разложение является конечной суммой.

В комбинаторике биномиальный коэффициент $(\genfrac{}{}{0ex}{}{n}{k})$$\textstyle {\binom {n}{k}}$ для неотрицательных целых чисел $n$$n$ и $k$$k$ интерпретируется как количество сочетаний из $n$$n$ по $k$$k$, то есть как количество всех (нестрогих) подмножеств (выборок) размера $k$$k$ в $n$$n$-элементном множестве.

Биномиальные коэффициенты часто возникают в задачах комбинаторики и теории вероятностей. Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты.

Явные формулыПравить

Вычисляя коэффициенты в разложении $(1+x{)}^n$$(1+x)^{n}$  в степенной ряд, можно получить явные формулы для биномиальных коэффициентов $(\genfrac{}{}{0ex}{}{n}{k})$$\textstyle {\binom {n}{k}}$ .

Для всех действительных чисел $n$$n$  и целых чисел $k$$k$ :

${\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!$$k!$  обозначает факториал числа $k$$k$ .

Для неотрицательных целых $n$$n$  и $k$$k$  также справедливы формулы:

${\binom {n}{k}}={\begin{cases}{\frac {n!}{k!(n-k)!}},&0\leqslant k\leqslant n\\0,&k>n\end{cases}}$ .

Для целых отрицательных показателей коэффициенты разложения бинома $(1+x{)}^{-<!--\; -\; -->n}$$(1+x)^{-n}$  равны:

${\binom {-n}{k}}={\begin{cases}(-1)^{k}\cdot {\frac {(n+k-1)!}{k!(n-1)!}},&k\geqslant 0\\0,&k<0\end{cases}}$ .

Треугольник ПаскаляПравить

 

 

Визуализация биномиального коэффициента до 4 степени

Основная статья: Треугольник Паскаля

Тождество:

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k-<!--\; -\; -->1})+(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k})$${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$ 

позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел $n$$n$ , $k$$k$  в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:

${\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°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, Омару Хайяму).

Если в каждой строке треугольника Паскаля все числа разделить на $2^n$$2^{n}$  (это сумма всех чисел в строке), то все строки при стремлении $n$$n$  к бесконечности примут вид функции нормального распределения.

СвойстваПравить

Производящие функцииПравить

Для фиксированного значения $n$$n$  производящей функцией последовательности биномиальных коэффициентов $(\genfrac{}{}{0ex}{}{n}{0}),(\genfrac{}{}{0ex}{}{n}{1}),(\genfrac{}{}{0ex}{}{n}{2}),\dots <!--\; \dots \; -->$${\tbinom {n}{0}},\;{\tbinom {n}{1}},\;{\tbinom {n}{2}},\dots$  является:

$\underset{k=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})x^k=(1+x{)}^n$$\sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}=(1+x)^{n}$ .

Для фиксированного значения $k$$k$  производящая функция последовательности коэффициентов $(\genfrac{}{}{0ex}{}{0}{k}),(\genfrac{}{}{0ex}{}{1}{k}),(\genfrac{}{}{0ex}{}{2}{k}),\dots <!--\; \dots \; -->$${\tbinom {0}{k}},\;{\tbinom {1}{k}},\;{\tbinom {2}{k}},\dots$  равна:

$\underset{n}{\sum <!--\; \sum \; -->}(\genfrac{}{}{0ex}{}{n}{k})y^n=\frac{y^k}{(1-<!--\; -\; -->y{)}^{k+1}}$$\sum _{n}{\binom {n}{k}}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}$ .

Двумерной производящей функцией биномиальных коэффициентов $(\genfrac{}{}{0ex}{}{n}{k})$$\tbinom{n}{k}$  для целых $n,k$$n,k$  является:

$\underset{n,k}{\sum <!--\; \sum \; -->}(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^n=\frac{1}{1-<!--\; -\; -->y-<!--\; -\; -->xy}$$\sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}$ , или $\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^n=\frac{1}{1-<!--\; -\; -->y-<!--\; -\; -->xy}$$\sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}$ .

ДелимостьПравить

Из теоремы Люка следует, что:

• коэффициент $(\genfrac{}{}{0ex}{}{n}{k})$$\textstyle {\binom {n}{k}}$  нечётен $⟺<!--\; ⟺\; -->$$\iff$  в двоичной записи числа $k$$k$  единицы не стоят в тех разрядах, где в числе $n$$n$  стоят нули;
• коэффициент $(\genfrac{}{}{0ex}{}{n}{k})$$\textstyle {\binom {n}{k}}$  некратен простому числу $p$$p$  $⟺<!--\; ⟺\; -->$$\iff$  в $p$$p$ -ичной записи числа $k$$k$  все разряды не превосходят соответствующих разрядов числа $n$$n$ ;
• в последовательности биномиальных коэффициентов $(\genfrac{}{}{0ex}{}{n}{0}),(\genfrac{}{}{0ex}{}{n}{1}),\dots <!--\; \dots \; -->,(\genfrac{}{}{0ex}{}{n}{n})$$\textstyle {\binom {n}{0}},\;{\binom {n}{1}},\;\ldots ,\;{\binom {n}{n}}$ :
  • все числа не кратны заданному простому $p$$p$  $⟺<!--\; ⟺\; -->$$\iff$  число $n$$n$  представимо в виде $m{p}^k-<!--\; -\; -->1$$mp^{k}-1$ , где натуральное число $m<p$ ;
  • все числа, кроме первого и последнего, кратны заданному простому $p$$p$  $⟺<!--\; ⟺\; -->$$\iff$  $n=p^k$$n=p^{k}$ ;
  • количество нечётных чисел равно степени двойки, показатель которой равен количеству единиц в двоичной записи числа $n$$n$ ;
  • чётных и нечётных чисел не может быть поровну;
  • количество чисел, не кратных простому $p$$p$ , равно $(a_1+1)\cdots <!--\; \cdots \; -->(a_m+1)$$(a_{1}+1)\cdots (a_{m}+1)$ , где числа $a_1,\dots <!--\; \dots \; -->,a_m$$a_{1},\;\ldots ,a_{m}$  — разряды $p$$p$ -ичной записи числа $n$$n$ ; а число $m=\lfloor <!--\; \lfloor \; -->{\log }_p<!--\; \; -->n\rfloor <!--\; \rfloor \; -->+1$$\textstyle m=\lfloor \log _{p}{n}\rfloor +1$ , где $\lfloor <!--\; \lfloor \; -->\cdot <!--\; \cdot \; -->\rfloor <!--\; \rfloor \; -->$$\lfloor\cdot\rfloor$  — функция «пол», — это длина данной записи.

Основные тождестваПравить

• $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k-<!--\; -\; -->1})+(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k})$${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$ .
• $(\genfrac{}{}{0ex}{}{n}{k})=(-<!--\; -\; -->1{)}^k(\genfrac{}{}{0ex}{}{-<!--\; -\; -->n+k-<!--\; -\; -->1}{k})$${\binom {n}{k}}=(-1)^{k}{\binom {-n+k-1}{k}}$ .
• $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{n-<!--\; -\; -->k})$${n \choose k}={n \choose n-k}$  (правило симметрии).
• $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n}{k}(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k-<!--\; -\; -->1})$${n \choose k}={\frac {n}{k}}{n-1 \choose k-1}$  (вынесение за скобки).
• $(\genfrac{}{}{0ex}{}{n}{m})(\genfrac{}{}{0ex}{}{m}{n-<!--\; -\; -->k})=(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{k}{n-<!--\; -\; -->m})$${n \choose {\color {Green}m}}{{\color {Green}m} \choose n-{\color {Green}k}}={n \choose {\color {Green}k}}{{\color {Green}k} \choose n-{\color {Green}m}}$  (замена индексов).
• $(n-<!--\; -\; -->k)(\genfrac{}{}{0ex}{}{n}{k})=n(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k})$$(n-k){n \choose k}=n{n-1 \choose k}$ .

Бином Ньютона и следствияПравить

• $(\genfrac{}{}{0ex}{}{n}{0})+(\genfrac{}{}{0ex}{}{n}{1})+\dots <!--\; \dots \; -->+(\genfrac{}{}{0ex}{}{n}{n})=2^n$${n \choose 0}+{n \choose 1}+\ldots +{n \choose n}=2^{n}$ , где $n\in <!--\; \in \; -->\mathbb{N}$$n\in \mathbb {N}$ .
• $\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}}$ 
• $\underset{j=k}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{j})(-<!--\; -\; -->1{)}^j=(-<!--\; -\; -->1{)}^k(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k-<!--\; -\; -->1})$$\sum_{j=k}^{n} \binom{n}{j} (-1)^j = (-1)^k \binom{n-1}{k-1}$ .
• $(\genfrac{}{}{0ex}{}{n}{0})-<!--\; -\; -->(\genfrac{}{}{0ex}{}{n}{1})+\dots <!--\; \dots \; -->+(-<!--\; -\; -->1{)}^n(\genfrac{}{}{0ex}{}{n}{n})=0$${n \choose 0}-{n \choose 1}+\ldots +(-1)^{n}{n \choose n}=0$ , где $n\in <!--\; \in \; -->\mathbb{N}$$n\in \mathbb {N}$ .
• Более сильное тождество: $(\genfrac{}{}{0ex}{}{n}{0})+(\genfrac{}{}{0ex}{}{n}{2})+\dots <!--\; \dots \; -->+(\genfrac{}{}{0ex}{}{n}{2\lfloor <!--\; \lfloor \; -->n/2\rfloor <!--\; \rfloor \; -->})=2^{n-<!--\; -\; -->1}$${n \choose 0}+{n \choose 2}+\ldots +{n \choose 2\lfloor n/2\rfloor }=2^{n-1}$ , где $n\in <!--\; \in \; -->\mathbb{N}$$n\in \mathbb {N}$ .
• $\underset{k=-<!--\; -\; -->a}{\overset{a}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^k{(\genfrac{}{}{0ex}{}{2a}{k+a})}^3=\frac{(3a)!}{(a!{)}^3}$$\sum _{{k=-a}}^{{a}}(-1)^{{k}}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}}$ ,

а более общем виде

$\underset{k=-<!--\; -\; -->a}{\overset{a}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^k(\genfrac{}{}{0ex}{}{a+b}{a+k})(\genfrac{}{}{0ex}{}{b+c}{b+k})(\genfrac{}{}{0ex}{}{c+a}{c+k})=\frac{(a+b+c)!}{a!b!c!}$$\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!}}$ .

Свёртка Вандермонда и следствияПравить

Свёртка Вандермонда:

$\underset{k}{\sum <!--\; \sum \; -->}(\genfrac{}{}{0ex}{}{r}{m+k})(\genfrac{}{}{0ex}{}{s}{n-<!--\; -\; -->k})=(\genfrac{}{}{0ex}{}{r+s}{m+n})$$\sum _{k}{r \choose m+k}{s \choose n-k}={r+s \choose m+n}$ ,

где $m,n\in <!--\; \in \; -->\mathbb{Z},$$m,n\in \mathbb {Z} ,$  а $r,s\in <!--\; \in \; -->\mathbb{R}$$r,s\in \mathbb {R}$ . Это тождество получается вычислением коэффициента при $x^{m+n}$$x^{m+n}$  в разложении $(1+x{)}^r(1+x{)}^s$$(1+x)^{r}(1+x)^{s}$  с учётом тождества $(1+x{)}^{r+s}=(1+x{)}^r(1+x{)}^s$$(1+x)^{r+s}=(1+x)^{r}(1+x)^{s}$ . Сумма берётся по всем целым $k$$k$ , для которых $(\genfrac{}{}{0ex}{}{r}{m+k})(\genfrac{}{}{0ex}{}{s}{n-<!--\; -\; -->k})\ne <!--\; \ne \; -->0$$\textstyle {r \choose m+k}{s \choose n-k}\neq 0$ . Для произвольных действительных $r$$r$ , $s$$s$  число ненулевых слагаемых в сумме будет конечно.

Следствие свёртки Вандермонда:

$(\genfrac{}{}{0ex}{}{n}{0})(\genfrac{}{}{0ex}{}{a}{a})-<!--\; -\; -->(\genfrac{}{}{0ex}{}{n}{1})(\genfrac{}{}{0ex}{}{a+1}{a})+\dots <!--\; \dots \; -->+(-<!--\; -\; -->1{)}^n(\genfrac{}{}{0ex}{}{n}{n})(\genfrac{}{}{0ex}{}{a+n}{a})=(-<!--\; -\; -->1{)}^n(\genfrac{}{}{0ex}{}{a}{n})$${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}$ .

Более общее тождество:

$\underset{i=0}{\overset{p}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^i(\genfrac{}{}{0ex}{}{p}{i})\underset{m=1}{\overset{n}{\prod <!--\; \prod \; -->}}(\genfrac{}{}{0ex}{}{i+s_m}{s_m})=0$$\sum _{{i=0}}^{{p}}(-1)^{i}{p \choose i}\prod _{{m=1}}^{{n}}{i+s_{m} \choose s_{m}}=0$ , если $\sum _{{m=1}}^{n}{s_{m}}<p$ .

Ещё одним следствием свёртки является следующее тождество: ${(\genfrac{}{}{0ex}{}{n}{0})}^2+{(\genfrac{}{}{0ex}{}{n}{1})}^2+\dots <!--\; \dots \; -->+{(\genfrac{}{}{0ex}{}{n}{n})}^2=(\genfrac{}{}{0ex}{}{2n}{n})$${n \choose 0}^{2}+{n \choose 1}^{2}+\ldots +{n \choose n}^{2}={2n \choose n}$ .

Другие тождестваПравить

• $\frac{4}{n}\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}{k}^2(\genfrac{}{}{0ex}{}{2n}{n+k})=2^{2n}$${\frac {4}{n}}\sum _{k=1}^{n}k^{2}{\binom {2n}{n+k}}=2^{2n}$ , где $n$$n$  — натуральное число.
• $\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{(-<!--\; -\; -->1{)}^{k-<!--\; -\; -->1}}{k}(\genfrac{}{}{0ex}{}{n}{k})=\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{1}{k}=H_n$$\sum _{k=1}^{n}{\frac {(-1)^{k-1}}{k}}{n \choose k}=\sum _{k=1}^{n}{\frac {1}{k}}=H_{n}$  — $n$$n$ -е гармоническое число.
• Мультисекция ряда $(1+x{)}^n$$(1+x)^{n}$  даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом $s$$s$  и смещением $t$$t$  $(0\leqslant t<s)$  в виде конечной суммы из $s$$s$  слагаемых:

$(\genfrac{}{}{0ex}{}{n}{t})+(\genfrac{}{}{0ex}{}{n}{t+s})+(\genfrac{}{}{0ex}{}{n}{t+2s})+\dots <!--\; \dots \; -->=\frac{1}{s}\underset{j=0}{\overset{s-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{\left(2\cos <!--\; \; -->\frac{\mathrm{\pi <!--\; \pi \; -->}j}{s}\right)}^n\cos <!--\; \; -->\frac{\mathrm{\pi <!--\; \pi \; -->}(n-<!--\; -\; -->2t)j}{s}$${\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}}$ .

Также имеют место равенства:

${\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}}$ 

${\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}}$ 

${\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}}$ 

Откуда следует:

$(\genfrac{}{}{0ex}{}{n}{3})=\frac{\underset{i=2}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(n-<!--\; -\; -->i)(2n-<!--\; -\; -->i+1)}{2}=\frac{\underset{i=2}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(n-<!--\; -\; -->i)\left(2A_n^1-<!--\; -\; -->(\genfrac{}{}{0ex}{}{i-<!--\; -\; -->1}{1})\right)}{2};$${\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}};$ 

$(\genfrac{}{}{0ex}{}{n}{4})=\frac{\underset{i=3}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(n-<!--\; -\; -->i)\left(2n(n-<!--\; -\; -->1)-<!--\; -\; -->\underset{i_0=1}{\overset{i-<!--\; -\; -->2}{\sum <!--\; \sum \; -->}}{i}_0\right)}{23}=\frac{\underset{i=3}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(n-<!--\; -\; -->i)\left(2A_n^2-<!--\; -\; -->(\genfrac{}{}{0ex}{}{i-<!--\; -\; -->1}{2})\right)}{23};$${\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}};$ 

${\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}}$ 

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{\underset{i=k-<!--\; -\; -->1}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}(n-<!--\; -\; -->i)\left(2A_n^{k-<!--\; -\; -->2}-<!--\; -\; -->(\genfrac{}{}{0ex}{}{i-<!--\; -\; -->1}{k-<!--\; -\; -->2})\right)}{k!-<!--\; -\; -->1}$${\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$$A_{n}^{k}$  — количество размещений из $n$$n$  по $k$$k$ .

Матричные соотношенияПравить

Если взять квадратную матрицу, отсчитав $N$$N$  элементов по катетам треугольника Паскаля и повернув матрицу на любой из четырёх углов, то детерминант этих четырёх матриц равен ±1 при любом $N$$N$ , причём детерминант матрицы с вершиной треугольника в верхнем левом углу равен 1.

В матрице $\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i+j}{i})\end{array}\right]$${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$  числа на диагонали $i+j=\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}$$i+j=\mathrm {Const}$  повторяют числа строк треугольника Паскаля ($i,j=0,1,\dots <!--\; \dots \; -->$$i,j=0,1,\dots$ ). Её можно разложить в произведение двух строго диагональных матриц: нижнетреугольной и получаемой из неё транспонированием:

$\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i+j}{i})\end{array}\right]=U{U}^T$${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}=UU^{T}$ ,

где $U=\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i}{j})\end{array}\right]$$U={\begin{bmatrix}{\tbinom {i}{j}}\end{bmatrix}}$ . Обратная матрица к $U$$U$  имеет вид:

$U^{-<!--\; -\; -->1}=\left[\begin{array}{c}(-<!--\; -\; -->1{)}^{i+j}(\genfrac{}{}{0ex}{}{i}{j})\end{array}\right]$$U^{-1}={\begin{bmatrix}(-1)^{i+j}{\binom {i}{j}}\end{bmatrix}}$ .

Таким образом, можно разложить обратную матрицу к $\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i+j}{i})\end{array}\right]$${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$  в произведение двух строго диагональных матриц: первая матрица — верхнетреугольная, а вторая получается из первой путём транспонирования, что позволяет дать явное выражение для обратных элементов:

${\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i+j}{i})\end{array}\right]}_{m,n}^{-<!--\; -\; -->1}=\underset{k=0}{\overset{p}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^{m+n}(\genfrac{}{}{0ex}{}{k}{m})(\genfrac{}{}{0ex}{}{k}{n})$${\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$$i$ , $j$$j$ , $m$$m$ , $n=0\dots <!--\; \dots \; -->p$$n=0\dots p$ .

Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы $\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i+j}{i})\end{array}\right]$${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$ , недостаточно приписать новую строку и столбец. Столбец $j$$j$  матрицы $\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i+j}{i})\end{array}\right]$${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$  есть многочлен степени $j$$j$  по аргументу $i$$i$ , следовательно, первые p столбцов образуют полный базис в пространстве векторов длины $p$$p$ +1, чьи координаты могут быть интерполированы многочленом равной или меньшей степени $p-<!--\; -\; -->1$$p-1$ . Нижняя строка матрицы ${\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i+j}{i})\end{array}\right]}_{m,n}^{-<!--\; -\; -->1}$${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{{m,n}}^{{-1}}$  ортогональна любому такому вектору.

${\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i+j}{i})\end{array}\right]}_{p,n}^{-<!--\; -\; -->1}=\underset{k=0}{\overset{p}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^{p+n}(\genfrac{}{}{0ex}{}{k}{p})(\genfrac{}{}{0ex}{}{k}{n})=(-<!--\; -\; -->1{)}^{p+n}(\genfrac{}{}{0ex}{}{p}{n})$${\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}}$ 

$\underset{n=0}{\overset{p}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^{p+n}(\genfrac{}{}{0ex}{}{p}{n})P_a(n)=0$$\sum _{{n=0}}^{{p}}(-1)^{{p+n}}{\binom {p}{n}}{P}_{{a}}(n)=0$  при $a<p$ , где $P_a(n)$${P}_{{a}}(n)$  многочлен степени $a$$a$ .

Если произвольный вектор длины $p+1$$p+1$  можно интерполировать многочленом степени $i<p$ , то скалярное произведение со строками $i+1,i+2,\dots <!--\; \dots \; -->,p$$i+1,i+2,\dots ,p$  (нумерация с 0) матрицы ${\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i+j}{i})\end{array}\right]}_{m,n}^{-<!--\; -\; -->1}$${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{{m,n}}^{{-1}}$  равно нулю. Используя тождество выше и равенство единицы скалярного произведения нижней строки матрицы ${\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i+j}{i})\end{array}\right]}_{m,n}^{-<!--\; -\; -->1}$${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{{m,n}}^{{-1}}$  на последний столбец матрицы $\left[\begin{array}{c}(\genfrac{}{}{0ex}{}{i+j}{i})\end{array}\right]$${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$ , получаем:

$\underset{n=0}{\overset{p}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^{p+n}(\genfrac{}{}{0ex}{}{p}{n})n^p=p!$$\sum _{n=0}^{p}(-1)^{p+n}{\binom {p}{n}}{n}^{p}=p!$ .

Для показателя большего $p$$p$  можно задать рекуррентную формулу:

$\underset{n=0}{\overset{p}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^{p+n}(\genfrac{}{}{0ex}{}{p}{n})n^{p+a}=p!P_{2a}(p)=f_a(p)$$\sum _{n=0}^{p}(-1)^{p+n}{\binom {p}{n}}{n}^{p+a}=p!{P}_{2a}(p)={f}_{a}(p)$ ,

где многочлен

$P_{2a+2}(p)=\underset{x=1}{\overset{p}{\sum <!--\; \sum \; -->}}x{P}_{2a}(x);a⩾<!--\; ⩾\; -->0;P_0(p)=1$${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)=\underset{x=0}{\overset{a}{\sum <!--\; \sum \; -->}}{(p+1)}^{x+1}{f}_{a-<!--\; -\; -->x}(p)$${f}_{a}(p+1)=\sum _{x=0}^{a}{(p+1)}^{x+1}{f}_{a-x}(p)$ .

Если требуется найти формулу не для всех показателей степени, то:

$P_{2a}(p)=\frac{p}{2^a}(\genfrac{}{}{0ex}{}{p+a}{a})Q_{a-<!--\; -\; -->1}(p);a>0$${P}_{2a}(p)={\frac {p}{{2}^{a}}}{\binom {p+a}{a}}{Q}_{a-1}(p);\quad a>0$ .

Старший коэффициент $Q_{a-<!--\; -\; -->1}(p)$${Q}_{{a-1}}(p)$  равен 1, потребуется a-1 значений, чтобы найти другие коэффициенты:

$Q_{a-<!--\; -\; -->1}(p)=p(p+1)T_{a-<!--\; -\; -->3}(p)$${Q}_{{a-1}}(p)=p(p+1){T}_{{a-3}}(p)$  для $a\equiv <!--\; \equiv \; -->1(\mathrm{mod}2);a⩾<!--\; ⩾\; -->3$$a\equiv 1{\pmod {2}};a\geqslant 3$ .

Асимптотика и оценкиПравить

• $(\genfrac{}{}{0ex}{}{2n}{n})\sim <!--\; \sim \; -->\frac{2^{2n}}{\sqrt{\mathrm{\pi <!--\; \pi \; -->}n}}$${\binom {2n}{n}}\sim {\frac {2^{2n}}{\sqrt {\pi n}}}$ .
• $\underset{k=0}{\overset{m}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})⩽<!--\; ⩽\; -->\frac{n}{(n/2-<!--\; -\; -->m{)}^2}{2}^{n-<!--\; -\; -->3}$$\sum _{{k=0}}^{{m}}{\binom {n}{k}}\leqslant {\frac {n}{(n/2-m)^{2}}}2^{{n-3}}$  при $m<{\frac {n}{2}}$  (неравенство Чебышёва).
• $\underset{k=0}{\overset{m}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})⩽<!--\; ⩽\; -->2^{nH(\frac{m}{n})}$$\sum \limits _{{k=0}}^{{m}}{\binom {n}{k}}\leqslant 2^{{nH({\frac {m}{n}})}}$ , при $m\le <!--\; \le \; -->\frac{n}{2}$$m\leq {\frac {n}{2}}$  (энтропийная оценка), где $H(x)=-<!--\; -\; -->x{\log }_2<!--\; \; -->x-<!--\; -\; -->(1-<!--\; -\; -->x){\log }_2<!--\; \; -->(1-<!--\; -\; -->x)$$H(x)=-x\log _{2}x-(1-x)\log _{2}(1-x)$  — энтропия.
• $\underset{k=0}{\overset{n/2-<!--\; -\; -->\mathrm{\lambda <!--\; \lambda \; -->}}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{k})⩽<!--\; ⩽\; -->2^n{e}^{-<!--\; -\; -->2{\mathrm{\lambda <!--\; \lambda \; -->}}^2/n}$$\sum _{{k=0}}^{{n/2-\lambda }}{\binom {n}{k}}\leqslant 2^{n}e^{{-2\lambda ^{2}/n}}$  (неравенство Чернова).

Непосредственно из формулы Стирлинга следует, что для $\mathrm{\alpha <!--\; \alpha \; -->}\in <!--\; \in \; -->(0;1)$$\alpha \in (0;1)$  верно $C_n^{\mathrm{\alpha <!--\; \alpha \; -->}n}\sim <!--\; \sim \; -->\sqrt{\frac{1}{2\mathrm{\pi <!--\; \pi \; -->}\mathrm{\alpha <!--\; \alpha \; -->}(1-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->})n}}{\left(\frac{1}{\mathrm{\alpha <!--\; \alpha \; -->}}\right)}^{\mathrm{\alpha <!--\; \alpha \; -->}n}{\left(\frac{1}{1-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->}}\right)}^{(1-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->})n}={\left(\frac{1}{{\mathrm{\alpha <!--\; \alpha \; -->}}^{\mathrm{\alpha <!--\; \alpha \; -->}}{(1-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->})}^{(1-<!--\; -\; -->\mathrm{\alpha <!--\; \alpha \; -->})}}+o(1)\right)}^n$$C_{n}^{{\alpha n}}\sim {\sqrt {{\frac {1}{2\pi \alpha (1-\alpha )n}}}}\left({{\frac {1}{\alpha }}}\right)^{{\alpha n}}\left({{\frac {1}{1-\alpha }}}\right)^{{(1-\alpha )n}}=\left({{\frac {1}{\alpha ^{\alpha }{(1-\alpha )}^{{(1-\alpha )}}}}+o(1)}\right)^{{n}}$ .

Целозначные полиномыПравить

Основная статья: Целозначный многочлен

Биномиальные коэффициенты $(\genfrac{}{}{0ex}{}{x}{0})=1,(\genfrac{}{}{0ex}{}{x}{1})=x,(\genfrac{}{}{0ex}{}{x}{2})=\frac{x^2}{2}-<!--\; -\; -->\frac{x}{2}$${\tbinom {x}{0}}=1,{\tbinom {x}{1}}=x,{\tbinom {x}{2}}={\tfrac {x^{2}}{2}}-{\tfrac {x}{2}}$ , … являются целозначными полиномами от $x$$x$ , то есть принимают целые значения при целых значениях $x$$x$ , — это нетрудно понять, например, по треугольнику Паскаля. Более того, они образуют базис целозначных полиномов, в котором все целозначные полиномы выражаются как линейные комбинации с целыми коэффициентами.

В то же время стандартный базис $1,x,x^2$$1,x,x^{2}$ , … не позволяет выразить все целочисленные полиномы, если использовать только целые коэффициенты, так как уже $(\genfrac{}{}{0ex}{}{x}{2})=\frac{x^2}{2}-<!--\; -\; -->\frac{x}{2}$${\tbinom {x}{2}}={\tfrac {x^{2}}{2}}-{\tfrac {x}{2}}$  имеет дробные коэффициенты при степенях $x$$x$ .

Этот результат обобщается на полиномы многих переменных. А именно, если полином $R(x_1,\dots <!--\; \dots \; -->,x_m)$$R(x_1, \dots, x_m)$  степени $k$$k$  имеет вещественные коэффициенты и принимает целые значения при целых значениях переменных, то

$R(x_1,\dots <!--\; \dots \; -->,x_m)=P\left((\genfrac{}{}{0ex}{}{x_1}{1}),\dots <!--\; \dots \; -->,(\genfrac{}{}{0ex}{}{x_1}{k}),\dots <!--\; \dots \; -->,(\genfrac{}{}{0ex}{}{x_m}{1}),\dots <!--\; \dots \; -->,(\genfrac{}{}{0ex}{}{x_m}{k})\right)$$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$$P$  — полином с целыми коэффициентами.

Алгоритмы вычисленияПравить

Биномиальные коэффициенты можно вычислить с помощью рекуррентной формулы $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k})+(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k-<!--\; -\; -->1})$${\tbinom {n}{k}}={\tbinom {n-1}{k}}+{\tbinom {n-1}{k-1}}$ , если на каждом шаге $n$$n$  хранить значения $(\genfrac{}{}{0ex}{}{n}{k})$$\tbinom{n}{k}$  при $k=\stackrel{¯<!--\; ¯\; -->}{0,1,\dots <!--\; \dots \; -->,n}$$k={\overline {0,1,\;\ldots ,n}}$ . Этот алгоритм особенно эффективен, если нужно получить все значения $(\genfrac{}{}{0ex}{}{n}{k})$$\tbinom{n}{k}$  при фиксированном $n$$n$ . Алгоритм требует $O(n)$$O(n)$  памяти ($O(n^2)$$O(n^{2})$  при вычислении всей таблицы биномиальных коэффициентов) и $O(n^2)$$O(n^{2})$  времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени), где $O$$O$  — «$o$$o$ » большое.

При фиксированном значении $k$$k$  биномиальные коэффициенты могут быть вычислены по рекуррентной формуле $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n}{n-<!--\; -\; -->k}\cdot <!--\; \cdot \; -->(\genfrac{}{}{0ex}{}{n-<!--\; -\; -->1}{k})$${\tbinom {n}{k}}={\tfrac {n}{n-k}}\cdot {\tbinom {n-1}{k}}$  с начальным значением $(\genfrac{}{}{0ex}{}{k}{k})=1$${\tbinom {k}{k}}=1$ . Для вычисления значения $(\genfrac{}{}{0ex}{}{n}{k})$$\tbinom{n}{k}$  этот метод требует $O(1)$$O(1)$  памяти и $O(n)$$O(n)$  времени.

Если требуется вычислить коэффициенты $(\genfrac{}{}{0ex}{}{n}{k})$$\tbinom{n}{k}$  при фиксированном значении $n$$n$ , можно воспользоваться формулой $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n-<!--\; -\; -->k+1}{k}\cdot <!--\; \cdot \; -->(\genfrac{}{}{0ex}{}{n}{k-<!--\; -\; -->1})$${\tbinom {n}{k}}={\tfrac {n-k+1}{k}}\cdot {\tbinom {n}{k-1}}$  при начальном условии $(\genfrac{}{}{0ex}{}{n}{0})=1$${\tbinom {n}{0}}=1$ . При каждом шаге итерации числитель уменьшается на $1$$1$  (начальное значение равно $n$$n$ ), а знаменатель соответственно увеличивается на $1$$1$  (начальное значение — $1$$1$ ). Для вычисления значения $(\genfrac{}{}{0ex}{}{n}{k})$$\tbinom{n}{k}$  этот метод требует $O(1)$$O(1)$  памяти и $O(k)$$O(k)$  времени.

ЛитератураПравить

• Биномиальные коэффициенты // Энциклопедический словарь Брокгауза и Ефрона : в 86 т. (82 т. и 4 доп.). — СПб., 1890—1907.
• Фукс Д., Фукс М. Арифметика биномиальных коэффициентов // Квант. — 1970. — № 6. — С. 17—25.
• Кузьмин О. В. Треугольник и пирамида Паскаля: свойства и обобщения // Соросовский Образовательный Журнал. — 2000. — Т. 6, № 5. — С. 101—109.
• Ландо С. К. Теневое исчисление // VIII летняя школа «Современная математика». — Дубна, 2008.
• Винберг Э. Б. Удивительные арифметические свойства биномиальных коэффициентов // Математическое просвещение. — 2008. — Вып. 12. — С. 33–42.
• Дональд Кнут, Роналд Грэхем, Орен Паташник. Конкретная математика. Математические основы информатики = Concrete Mathematics. A Foundation for Computer Science. — 2-е. — М.: Мир; Бином. Лаборатория знаний; «Вильямс», 1998—2009. — 703, 784 с. — ISBN 95-94774-560-7, 78-5-8459-1588-7.