ru.wikipedia.org

Биномиальный коэффициент — Википедия

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

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

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

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

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

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

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

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

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

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

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

Для целых отрицательных показателей коэффициенты разложения бинома $(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}}$ .

Тождество:

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

Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от той, что выписана здесь, поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, Омару Хайяму, аль-Караджи, Яну Хуэю).

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

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

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

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

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

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

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

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

Этот раздел нужно дополнить.

Пожалуйста, улучшите и дополните его.

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

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

$\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}{r \choose m+k}{s \choose n-k}={r+s \choose m+n}$ ,

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

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

${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 _{m=1}^{n}{s_{m}}<p$ .

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

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

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

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

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

${\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}$ — количество размещений из $n$ по $k$ .

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

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

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

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

$U^{-1}={\begin{bmatrix}(-1)^{i+j}{\binom {i}{j}}\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}}$ , где $i$ , $j$ , $m$ , $n=0\dots p$ .

Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы ${\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}$ , недостаточно приписать новую строку и столбец. Столбец $j$ матрицы ${\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}}_{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$ при $a<p$ , где ${P}_{a}(n)$ многочлен степени $a$ .

Если произвольный вектор длины $p+1$ можно интерполировать многочленом степени $i<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}{\tbinom {i+j}{i}}\end{bmatrix}}$ , получаем:

$\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)$ ,

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

${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)$ .

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

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

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

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

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

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

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

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

где $P$ — полином с целыми коэффициентами.^[2]

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

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

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

↑ Прасолов В. В. Глава 12. Целозначные многочлены // Многочлены. — М.: МЦНМО, 1999, 2001, 2003. Архивировано 21 января 2022 года.
↑ Ю. Матиясевич. Десятая проблема Гильберта. — Наука, 1993.

Биномиальные коэффициенты // Энциклопедический словарь Брокгауза и Ефрона : в 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.