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

В математике биномиальные коэффициенты — это коэффициенты в разложении бинома Ньютона $(1+x)^{n}$$(1+x)^{n}$ по степеням x. Коэффициент при $x^{k}$$x^{k}$ обозначается $\textstyle {\binom {n}{k}}$$\textstyle {\binom {n}{k}}$ или $\textstyle C_{n}^{k}$$\textstyle C_n^k$ и читается «биномиальный коэффициент из n по k» (или «це из n по 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},$$(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},$

(1)

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

$(1+x)^{n}=\sum _{k=0}^{\infty }{\binom {n}{k}}x^{k},$$(1+x)^{n}=\sum _{k=0}^{\infty }{\binom {n}{k}}x^{k},$

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

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

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

Явные формулы

Значение биномиального коэффициента $\textstyle {\binom {n}{k}}$$\textstyle {\binom {n}{k}}$ определено для всех действительных чисел n и целых чисел 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}}$${\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.

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

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

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

Тождество

${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$

позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел n, 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}}$${\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}$ (сумма всех чисел в строке), в пределе стремятся к функции нормального распределения.

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

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

Свойства

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

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

$\sum _{k}{\binom {n}{k}}x^{k}=(1+x)^{n}.$$\sum _{k}{\binom {n}{k}}x^{k}=(1+x)^{n}.$

Для фиксированного значения k производящей функцией последовательности биномиальных коэффициентов ${\tbinom {0}{k}},\;{\tbinom {1}{k}},\;{\tbinom {2}{k}},\;\ldots$${\tbinom {0}{k}},\;{\tbinom {1}{k}},\;{\tbinom {2}{k}},\;\ldots$ является:

$\sum _{n}{\binom {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}}}}.$

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

$\sum _{n,k}{\binom {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}}.$

Делимость

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

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

Основные тождества

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

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

• ${n \choose 0}+{n \choose 1}+\ldots +{n \choose n}=2^{n}.$${n \choose 0}+{n \choose 1}+\ldots +{n \choose n}=2^{n}.$
• $\sum _{i+j=m}{\binom {n}{j}}{\binom {n}{i}}(-1)^{j}={\begin{cases}(-1)^{m/2}{\binom {n}{m/2}}&{\text{if}}\ m\equiv 0{\pmod {2}},\\0&{\text{if}}\ m\equiv 1{\pmod {2}}.\end{cases}}$$\sum _{{i+j=m}}{\binom {n}{j}}{\binom {n}{i}}(-1)^{j}={\begin{cases}(-1)^{{m/2}}{\binom {n}{m/2}}&{\text{if}}\ m\equiv 0{\pmod {2}},\\0&{\text{if}}\ m\equiv 1{\pmod {2}}.\end{cases}}$
• $\sum _{j=k}^{n}{\binom {n}{j}}(-1)^{j}=(-1)^{k}{\binom {n-1}{k-1}}.$$\sum _{{j=k}}^{{n}}{\binom {n}{j}}(-1)^{j}=(-1)^{k}{\binom {n-1}{k-1}}.$
• ${n \choose 0}-{n \choose 1}+\ldots +(-1)^{n}{n \choose n}=0.$${n \choose 0}-{n \choose 1}+\ldots +(-1)^{n}{n \choose n}=0.$ Это тождество можно усилить:
• ${n \choose 0}+{n \choose 2}+\ldots +{n \choose 2\lfloor n/2\rfloor }=2^{n-1}.$${n \choose 0}+{n \choose 2}+\ldots +{n \choose 2\lfloor n/2\rfloor }=2^{{n-1}}.$
• $\sum _{k=-a}^{a}(-1)^{k}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}}$$\sum _{{k=-a}}^{{a}}(-1)^{{k}}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}}$

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

$\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!}}\,,$$\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!}}\,,$

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

• $\sum _{k=-\infty }^{+\infty }{r \choose m+k}{s \choose n-k}={r+s \choose m+n}$$\sum _{{k=-\infty }}^{{+\infty }}{r \choose m+k}{s \choose n-k}={r+s \choose m+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}$${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}$.
• $\sum _{i=0}^{p}(-1)^{i}{p \choose i}\prod _{m=1}^{n}{i+s_{m} \choose 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$$\sum _{{m=1}}^{n}{s_{m}}<p$, — более общий вид тождества выше.
• ${n \choose 0}^{2}+{n \choose 1}^{2}+\ldots +{n \choose n}^{2}={2n \choose n}.$${n \choose 0}^{2}+{n \choose 1}^{2}+\ldots +{n \choose n}^{2}={2n \choose n}.$

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

• $\sum _{k=1}^{m}{\frac {(-1)^{k-1}}{k}}{m \choose k}=\sum _{k=1}^{m}{\frac {1}{k}}=H_{m}$$\sum _{{k=1}}^{m}{\frac {(-1)^{{k-1}}}{k}}{m \choose k}=\sum _{{k=1}}^{m}{\frac {1}{k}}=H_{m}$ — m-ое гармоническое число.
• Мультисекция ряда $(1+x)^{n}$$(1+x)^{n}$ даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом s и смещением t $(0\leqslant t<s)$$(0\leqslant t<s)$ в виде замкнутой суммы из 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}}.$${\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 элементов по катетам треугольника Паскаля и повернув матрицу на любой из четырёх углов, то детерминант этих четырёх матриц равен ±1 при любом N, причём детерминант матрицы с вершиной треугольника в верхнем левом углу равен 1.

В матрице ${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$ числа на диагонали i + j = const повторяют числа строк треугольника Паскаля (i, j = 0,1,…). Её можно разложить в произведение двух строго диагональных матриц: нижнетреугольной и получаемой из неё транспонированием. А именно:

${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}=UU^{T},$${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}=UU^{T},$

где $U={\begin{bmatrix}{\tbinom {i}{j}}\end{bmatrix}}$$U={\begin{bmatrix}{\tbinom {i}{j}}\end{bmatrix}}$. Обратная матрица к U имеет вид:

$U^{-1}={\begin{bmatrix}(-1)^{i+j}{\binom {i}{j}}\end{bmatrix}}.$$U^{{-1}}={\begin{bmatrix}(-1)^{{i+j}}{\binom {i}{j}}\end{bmatrix}}.$

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

${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{m,n}^{-1}=\sum _{k=0}^{p}(-1)^{m+n}{\binom {k}{m}}{\binom {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, j , m, n = 0..p.

Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы ${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$, недостаточно приписать новую строку и столбец. Столбец j матрицы ${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$ есть многочлен степени j по аргументу i, следовательно, первые p столбцов образуют полный базис в пространстве векторов длины p+1, чьи координаты могут быть интерполированы многочленом равной или меньшей степени p-1. Нижняя строка матрицы ${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{m,n}^{-1}$${\begin{bmatrix}{\binom {i+j}{i}}\end{bmatrix}}_{{m,n}}^{{-1}}$ ортогональна любому такому вектору.

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

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

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

$\sum _{n=0}^{p}(-1)^{p+n}{\binom {p}{n}}{n}^{p}=p!.$$\sum _{{n=0}}^{{p}}(-1)^{{p+n}}{\binom {p}{n}}{n}^{{p}}=p!.$

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

$\sum _{n=0}^{p}(-1)^{p+n}{\binom {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)=\sum _{x=1}^{p}x{P}_{2a}(x);\quad a\geqslant 0;\quad {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)=\sum _{x=0}^{a}{(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}}}{\binom {p+a}{a}}{Q}_{a-1}(p);\quad 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 1{\pmod {2}};a\geqslant 3.$$a\equiv 1{\pmod {2}};a\geqslant 3.$

Асимптотика и оценки

• ${\binom {2n}{n}}\sim {\frac {2^{2n}}{\sqrt {\pi n}}}.$${\binom {2n}{n}}\sim {\frac {2^{{2n}}}{{\sqrt {\pi n}}}}.$
• $\sum _{k=0}^{m}{\binom {n}{k}}\leqslant {\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}}$$m<{\frac {n}{2}}$ (неравенство Чебышёва).
• $\sum \limits _{k=0}^{m}{\binom {n}{k}}\leqslant 2^{nH({\frac {m}{n}})}$$\sum \limits _{{k=0}}^{{m}}{\binom {n}{k}}\leqslant 2^{{nH({\frac {m}{n}})}}$, при $m\leq {\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)$ — энтропия.
• $\sum _{k=0}^{n/2-\lambda }{\binom {n}{k}}\leqslant 2^{n}e^{-2\lambda ^{2}/n}$$\sum _{{k=0}}^{{n/2-\lambda }}{\binom {n}{k}}\leqslant 2^{n}e^{{-2\lambda ^{2}/n}}$ (неравенство Чернова).

Непосредственно из формулы Стирлинга следует, что для $\alpha \in (0;1)$$\alpha \in (0;1)$ верно $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}$$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}}$.

Целозначные полиномы

Нетрудно видеть, что биномиальные коэффициенты ${\tbinom {x}{0}}=1,{\tbinom {x}{1}}=x,{\tbinom {x}{2}}={\tfrac {x^{2}}{2}}-{\tfrac {x}{2}},\dots$${\tbinom {x}{0}}=1,{\tbinom {x}{1}}=x,{\tbinom {x}{2}}={\tfrac {x^{2}}{2}}-{\tfrac {x}{2}},\dots$ являются целозначными полиномами от $x$$x$, т.е. принимают целые значения при целых значениях $x$$x$. Более того, они образуют базис целозначных полиномов, в котором все целозначные полиномы выражаются как линейные комбинации с целыми коэффициентами.

В то же время стандартный базис $1,x,x^{2},\dots$$1,x,x^{2},\dots$ не позволяет выразить все целочисленные полиномы, используя только целые коэффициенты, так как уже ${\tbinom {x}{2}}={\tfrac {x^{2}}{2}}-{\tfrac {x}{2}}$${\tbinom {x}{2}}={\tfrac {x^{2}}{2}}-{\tfrac {x}{2}}$ имеет дробные коэффициенты при степенях $x$$x$.

Этот результат обобщается на полиномы многих переменных. А именно, если полином $R(x_{1},\dots ,x_{m})$$R(x_1, \dots, x_m)$ степени $k$$k$ имеет вещественные коэффициенты и принимает целые значения при целых значениях переменных, то

$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),$$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$ — полином с целыми коэффициентами.

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

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

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

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