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

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

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

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

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

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

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

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

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

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

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

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

где ${\displaystyle k!}$ обозначает факториал числа ${\displaystyle k}$ .

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

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

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

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

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

Тождество:

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

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

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

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

Свойства

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

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

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

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

${\displaystyle \sum _{n}{\binom {n}{k}}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}}$ .

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

${\displaystyle \sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}}$ , или ${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}}$ .

Делимость

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

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

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

• ${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}$ .
• ${\displaystyle {\binom {n}{k}}=(-1)^{k}{\binom {-n+k-1}{k}}}$ .
• ${\displaystyle {n \choose k}={n \choose n-k}}$ (правило симметрии).
• ${\displaystyle {n \choose k}={\frac {n}{k}}{n-1 \choose k-1}}$ (вынесение за скобки).
• ${\displaystyle {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}}}$ (замена индексов).
• ${\displaystyle (n-k){n \choose k}=n{n-1 \choose k}}$ .

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

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

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

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

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

Этот раздел не завершён . Вы поможете проекту, исправив и дополнив его.

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

${\displaystyle \sum _{k}{r \choose m+k}{s \choose n-k}={r+s \choose m+n}}$ ,

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

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

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

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

${\displaystyle \sum _{i=0}^{p}(-1)^{i}{p \choose i}\prod _{m=1}^{n}{i+s_{m} \choose s_{m}}=0}$ , если ${\displaystyle \sum _{m=1}^{n}{s_{m}}<p}$ .

Ещё одним следствием свёртки является следующее тождество: ${\displaystyle {n \choose 0}^{2}+{n \choose 1}^{2}+\ldots +{n \choose n}^{2}={2n \choose n}}$ .

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

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

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

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

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

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

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

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

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

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

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

где ${\displaystyle A_{n}^{k}}$ — количество размещений из ${\displaystyle n}$ по ${\displaystyle k}$ .

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

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

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

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

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

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

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

${\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}}}$ , где ${\displaystyle i}$ , ${\displaystyle j}$ , ${\displaystyle m}$ , ${\displaystyle n=0\dots p}$ .

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

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

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

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

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

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

${\displaystyle \sum _{n=0}^{p}(-1)^{p+n}{\binom {p}{n}}{n}^{p+a}=p!{P}_{2a}(p)={f}_{a}(p)}$ ,

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

${\displaystyle {P}_{2a+2}(p)=\sum _{x=1}^{p}x{P}_{2a}(x);\quad a\geqslant 0;\quad {P}_{0}(p)=1}$ .

Для доказательства сперва устанавливается тождество:

${\displaystyle {f}_{a}(p+1)=\sum _{x=0}^{a}{(p+1)}^{x+1}{f}_{a-x}(p)}$ .

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

${\displaystyle {P}_{2a}(p)={\frac {p}{{2}^{a}}}{\binom {p+a}{a}}{Q}_{a-1}(p);\quad a>0}$ .

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

${\displaystyle {Q}_{a-1}(p)=p(p+1){T}_{a-3}(p)}$ для ${\displaystyle a\equiv 1{\pmod {2}};a\geqslant 3}$ .

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

• ${\displaystyle {\binom {2n}{n}}\sim {\frac {2^{2n}}{\sqrt {\pi n}}}}$ .
• ${\displaystyle \sum _{k=0}^{m}{\binom {n}{k}}\leqslant {\frac {n}{(n/2-m)^{2}}}2^{n-3}}$ при ${\displaystyle m<{\frac {n}{2}}}$ ( неравенство Чебышёва ).
• ${\displaystyle \sum \limits _{k=0}^{m}{\binom {n}{k}}\leqslant 2^{nH({\frac {m}{n}})}}$ , при ${\displaystyle m\leq {\frac {n}{2}}}$ ( ), где ${\displaystyle H(x)=-x\log _{2}x-(1-x)\log _{2}(1-x)}$ — энтропия .
• ${\displaystyle \sum _{k=0}^{n/2-\lambda }{\binom {n}{k}}\leqslant 2^{n}e^{-2\lambda ^{2}/n}}$ ( неравенство Чернова ).

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

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

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

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

Этот результат обобщается на полиномы многих переменных. А именно, если полином ${\displaystyle R(x_{1},\dots ,x_{m})}$ степени ${\displaystyle 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)}$ ,

где ${\displaystyle P}$ — полином с целыми коэффициентами.

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

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

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

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