Биномиа́льный коэффицие́нт — коэффициент перед членом разложения бинома Ньютона
(
1
+
x
)
n
{\displaystyle (1+x)^{n}}
по степеням
x
{\displaystyle x}
. Коэффициент при
x
k
{\displaystyle x^{k}}
обозначается
(
n
k
)
{\displaystyle \textstyle {\binom {n}{k}}}
или
C
n
k
{\displaystyle \textstyle C_{n}^{k}}
и читается «биномиальный коэффициент из
n
{\displaystyle n}
по
k
{\displaystyle k}
» (или «число сочетаний из
n
{\displaystyle n}
по
k
{\displaystyle k}
»):
(
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}={\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
{\displaystyle n}
.
Биномиальные коэффициенты могут быть также определены для произвольных действительных показателей
n
{\displaystyle n}
. В случае произвольного действительного числа
n
{\displaystyle n}
биномиальные коэффициенты определяются как коэффициенты разложения выражения
(
1
+
x
)
n
{\displaystyle (1+x)^{n}}
в бесконечный степенной ряд :
(
1
+
x
)
n
=
∑
k
=
0
∞
(
n
k
)
x
k
{\displaystyle (1+x)^{n}=\sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}}
,
где в случае неотрицательных целых
n
{\displaystyle n}
все коэффициенты
(
n
k
)
{\displaystyle \textstyle {\binom {n}{k}}}
при
k
>
n
{\displaystyle k>n}
обращаются в нуль и поэтому данное разложение является конечной суммой.
В комбинаторике биномиальный коэффициент
(
n
k
)
{\displaystyle \textstyle {\binom {n}{k}}}
для неотрицательных целых чисел
n
{\displaystyle n}
и
k
{\displaystyle k}
интерпретируется как количество сочетаний из
n
{\displaystyle n}
по
k
{\displaystyle k}
, то есть как количество всех (нестрогих) подмножеств (выборок ) размера
k
{\displaystyle k}
в
n
{\displaystyle n}
-элементном множестве .
Биномиальные коэффициенты часто возникают в задачах комбинаторики и теории вероятностей . Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты .
Вычисляя коэффициенты в разложении
(
1
+
x
)
n
{\displaystyle (1+x)^{n}}
в степенной ряд, можно получить явные формулы для биномиальных коэффициентов
(
n
k
)
{\displaystyle \textstyle {\binom {n}{k}}}
.
Для всех действительных чисел
n
{\displaystyle n}
и целых чисел
k
{\displaystyle 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
{\displaystyle k}
.
Для неотрицательных целых
n
{\displaystyle n}
и
k
{\displaystyle 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}}}
.
Визуализация биномиального коэффициента до 4 степени
Тождество:
(
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°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье , Омару Хайяму ).
Если в каждой строке треугольника Паскаля все числа разделить на
2
n
{\displaystyle 2^{n}}
(это сумма всех чисел в строке ), то все строки при стремлении
n
{\displaystyle n}
к бесконечности примут вид функции нормального распределения .
Для фиксированного значения
n
{\displaystyle n}
производящей функцией последовательности биномиальных коэффициентов
(
n
0
)
,
(
n
1
)
,
(
n
2
)
,
…
{\displaystyle {\tbinom {n}{0}},\;{\tbinom {n}{1}},\;{\tbinom {n}{2}},\dots }
является:
∑
k
=
0
∞
(
n
k
)
x
k
=
(
1
+
x
)
n
{\displaystyle \sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}=(1+x)^{n}}
.
Для фиксированного значения
k
{\displaystyle k}
производящая функция последовательности коэффициентов
(
0
k
)
,
(
1
k
)
,
(
2
k
)
,
…
{\displaystyle {\tbinom {0}{k}},\;{\tbinom {1}{k}},\;{\tbinom {2}{k}},\dots }
равна:
∑
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
{\displaystyle k}
единицы не стоят в тех разрядах, где в числе
n
{\displaystyle n}
стоят нули;
коэффициент
(
n
k
)
{\displaystyle \textstyle {\binom {n}{k}}}
некратен простому числу
p
{\displaystyle p}
⟺
{\displaystyle \iff }
в
p
{\displaystyle p}
-ичной записи числа
k
{\displaystyle k}
все разряды не превосходят соответствующих разрядов числа
n
{\displaystyle n}
;
в последовательности биномиальных коэффициентов
(
n
0
)
,
(
n
1
)
,
…
,
(
n
n
)
{\displaystyle \textstyle {\binom {n}{0}},\;{\binom {n}{1}},\;\ldots ,\;{\binom {n}{n}}}
:
все числа не кратны заданному простому
p
{\displaystyle p}
⟺
{\displaystyle \iff }
число
n
{\displaystyle n}
представимо в виде
m
p
k
−
1
{\displaystyle mp^{k}-1}
, где натуральное число
m
<
p
{\displaystyle m<p}
;
все числа, кроме первого и последнего, кратны заданному простому
p
{\displaystyle p}
⟺
{\displaystyle \iff }
n
=
p
k
{\displaystyle n=p^{k}}
;
количество нечётных чисел равно степени двойки, показатель которой равен количеству единиц в двоичной записи числа
n
{\displaystyle n}
;
чётных и нечётных чисел не может быть поровну;
количество чисел, не кратных простому
p
{\displaystyle p}
, равно
(
a
1
+
1
)
⋯
(
a
m
+
1
)
{\displaystyle (a_{1}+1)\cdots (a_{m}+1)}
, где числа
a
1
,
…
,
a
m
{\displaystyle a_{1},\;\ldots ,a_{m}}
— разряды
p
{\displaystyle p}
-ичной записи числа
n
{\displaystyle 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
)
=
(
−
1
)
k
(
−
n
+
k
−
1
k
)
{\displaystyle {\binom {n}{k}}=(-1)^{k}{\binom {-n+k-1}{k}}}
.
(
n
k
)
=
(
n
n
−
k
)
{\displaystyle {n \choose k}={n \choose n-k}}
(правило симметрии).
(
n
k
)
=
n
k
(
n
−
1
k
−
1
)
{\displaystyle {n \choose k}={\frac {n}{k}}{n-1 \choose k-1}}
(вынесение за скобки).
(
n
m
)
(
m
n
−
k
)
=
(
n
k
)
(
k
n
−
m
)
{\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}}}
(замена индексов).
(
n
−
k
)
(
n
k
)
=
n
(
n
−
1
k
)
{\displaystyle (n-k){n \choose k}=n{n-1 \choose k}}
.
(
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
)
(
−
1
)
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}}(-1)^{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}}
.
4
n
∑
k
=
1
n
k
2
(
2
n
n
+
k
)
=
2
2
n
{\displaystyle {\frac {4}{n}}\sum _{k=1}^{n}k^{2}{\binom {2n}{n+k}}=2^{2n}}
, где
n
{\displaystyle 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
{\displaystyle n}
-е гармоническое число .
Мультисекция ряда
(
1
+
x
)
n
{\displaystyle (1+x)^{n}}
даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом
s
{\displaystyle s}
и смещением
t
{\displaystyle t}
(
0
⩽
t
<
s
)
{\displaystyle (0\leqslant t<s)}
в виде конечной суммы из
s
{\displaystyle 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
{\displaystyle n}
по
k
{\displaystyle k}
.
Если взять квадратную матрицу, отсчитав
N
{\displaystyle N}
элементов по катетам треугольника Паскаля и повернув матрицу на любой из четырёх углов, то детерминант этих четырёх матриц равен ±1 при любом
N
{\displaystyle N}
, причём детерминант матрицы с вершиной треугольника в верхнем левом углу равен 1.
В матрице
[
(
i
+
j
i
)
]
{\displaystyle {\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}}
числа на диагонали
i
+
j
=
C
o
n
s
t
{\displaystyle i+j=\mathrm {Const} }
повторяют числа строк треугольника Паскаля (
i
,
j
=
0
,
1
,
…
{\displaystyle i,j=0,1,\dots }
). Её можно разложить в произведение двух строго диагональных матриц: нижнетреугольной и получаемой из неё транспонированием:
[
(
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
{\displaystyle i}
,
j
{\displaystyle j}
,
m
{\displaystyle m}
,
n
=
0
…
p
{\displaystyle n=0\dots p}
.
Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы
[
(
i
+
j
i
)
]
{\displaystyle {\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}}
, недостаточно приписать новую строку и столбец. Столбец
j
{\displaystyle j}
матрицы
[
(
i
+
j
i
)
]
{\displaystyle {\begin{bmatrix}{\tbinom {i+j}{i}}\end{bmatrix}}}
есть многочлен степени
j
{\displaystyle j}
по аргументу
i
{\displaystyle i}
, следовательно, первые p столбцов образуют полный базис в пространстве векторов длины
p
{\displaystyle p}
+1, чьи координаты могут быть интерполированы многочленом равной или меньшей степени
p
−
1
{\displaystyle 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
{\displaystyle 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 значений, чтобы найти другие коэффициенты:
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}
.
(
2
n
n
)
∼
2
2
n
π
n
{\displaystyle {\binom {2n}{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}{\binom {n}{k}}\leqslant {\frac {n}{(n/2-m)^{2}}}2^{n-3}}
при
m
<
n
2
{\displaystyle m<{\frac {n}{2}}}
(неравенство Чебышёва ).
∑
k
=
0
m
(
n
k
)
⩽
2
n
H
(
m
n
)
{\displaystyle \sum \limits _{k=0}^{m}{\binom {n}{k}}\leqslant 2^{nH({\frac {m}{n}})}}
, при
m
≤
n
2
{\displaystyle m\leq {\frac {n}{2}}}
(энтропийная оценка ), где
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 }{\binom {n}{k}}\leqslant 2^{n}e^{-2\lambda ^{2}/n}}
(неравенство Чернова ).
Непосредственно из формулы Стирлинга следует, что для
α
∈
(
0
;
1
)
{\displaystyle \alpha \in (0;1)}
верно
C
n
α
n
∼
1
2
π
α
(
1
−
α
)
n
(
1
α
)
α
n
(
1
1
−
α
)
(
1
−
α
)
n
=
(
1
α
α
(
1
−
α
)
(
1
−
α
)
+
o
(
1
)
)
n
{\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}}
.
Биномиальные коэффициенты
(
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}
, — это нетрудно понять, например, по треугольнику Паскаля. Более того, они образуют базис целозначных полиномов, в котором все целозначные полиномы выражаются как линейные комбинации с целыми коэффициентами.[1]
В то же время стандартный базис
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}
— полином с целыми коэффициентами.[2]
Биномиальные коэффициенты можно вычислить с помощью рекуррентной формулы
(
n
k
)
=
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
{\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k}}+{\tbinom {n-1}{k-1}}}
, если на каждом шаге
n
{\displaystyle n}
хранить значения
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
при
k
=
0
,
1
,
…
,
n
¯
{\displaystyle k={\overline {0,1,\;\ldots ,n}}}
. Этот алгоритм особенно эффективен, если нужно получить все значения
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
при фиксированном
n
{\displaystyle n}
. Алгоритм требует
O
(
n
)
{\displaystyle O(n)}
памяти (
O
(
n
2
)
{\displaystyle O(n^{2})}
при вычислении всей таблицы биномиальных коэффициентов) и
O
(
n
2
)
{\displaystyle O(n^{2})}
времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени), где
O
{\displaystyle O}
— «
o
{\displaystyle o}
» большое .
При фиксированном значении
k
{\displaystyle k}
биномиальные коэффициенты могут быть вычислены по рекуррентной формуле
(
n
k
)
=
n
n
−
k
⋅
(
n
−
1
k
)
{\displaystyle {\tbinom {n}{k}}={\tfrac {n}{n-k}}\cdot {\tbinom {n-1}{k}}}
с начальным значением
(
k
k
)
=
1
{\displaystyle {\tbinom {k}{k}}=1}
. Для вычисления значения
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
этот метод требует
O
(
1
)
{\displaystyle O(1)}
памяти и
O
(
n
)
{\displaystyle O(n)}
времени.
Если требуется вычислить коэффициенты
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
при фиксированном значении
n
{\displaystyle n}
, можно воспользоваться формулой
(
n
k
)
=
n
−
k
+
1
k
⋅
(
n
k
−
1
)
{\displaystyle {\tbinom {n}{k}}={\tfrac {n-k+1}{k}}\cdot {\tbinom {n}{k-1}}}
при начальном условии
(
n
0
)
=
1
{\displaystyle {\tbinom {n}{0}}=1}
. При каждом шаге итерации числитель уменьшается на
1
{\displaystyle 1}
(начальное значение равно
n
{\displaystyle n}
), а знаменатель соответственно увеличивается на
1
{\displaystyle 1}
(начальное значение —
1
{\displaystyle 1}
). Для вычисления значения
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
этот метод требует
O
(
1
)
{\displaystyle O(1)}
памяти и
O
(
k
)
{\displaystyle O(k)}
времени.
↑ Прасолов В. В. Глава 12. Целозначные многочлены // Многочлены . — М. : МЦНМО , 1999, 2001, 2003. Архивировано 21 января 2022 года.
↑ Ю. Матиясевич. Десятая проблема Гильберта. — Наука, 1993.