Матеріал з Вікіпедії — вільної енциклопедії.
Біноміальні коефіцієнти — коефіцієнти в розкладі
(
1
+
x
)
n
{\displaystyle \ (1+x)^{n}}
по степенях
x
{\displaystyle \ x}
(так званий біном Ньютона ):
(
1
+
x
)
n
=
(
n
0
)
x
0
+
(
n
1
)
x
+
(
n
2
)
x
2
+
⋯
+
(
n
n
)
x
n
=
∑
k
=
0
n
(
n
k
)
x
k
.
{\displaystyle (1+x)^{n}={n \choose 0}x^{0}+{n \choose 1}x+{n \choose 2}x^{2}+\cdots +{n \choose n}x^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}.}
Значення біноміального коефіцієнта
(
n
k
)
{\displaystyle {n \choose k}}
визначено для усіх цілих чисел
n
{\displaystyle \ n}
та
k
{\displaystyle \ k}
. Явні формули для обчислення біноміальних коефіцієнтів:
(
n
k
)
=
n
!
k
!
(
n
−
k
)
!
{\displaystyle {n \choose k}={\frac {n!}{k!\;(n-k)!}}}
для
0
≤
k
≤
n
{\displaystyle 0\leq k\leq n}
;
(
n
k
)
=
0
{\displaystyle {n \choose k}=0}
для
k
<
0
{\displaystyle \ k<0}
або
0
≤
n
<
k
{\displaystyle 0\leq n<k}
;
(
n
k
)
=
(
−
1
)
k
(
−
n
+
k
−
1
k
)
{\displaystyle {n \choose k}=(-1)^{k}{-n+k-1 \choose k}}
для
n
<
0
≤
k
{\displaystyle n<0\leq k}
,
де
n
!
{\displaystyle n!}
та
k
!
{\displaystyle k!}
— факторіали чисел
n
{\displaystyle n}
і
k
{\displaystyle k}
.
Біноміальний коефіцієнт
(
n
k
)
{\displaystyle {n \choose k}}
є узагальненням кількості невпорядкованих виборів
C
n
k
{\displaystyle C_{n}^{k}}
, що визначена тільки для невід'ємних цілих чисел
n
{\displaystyle n}
,
k
{\displaystyle k}
.
Біноміальні коефіцієнти часто зустрічаються в комбінаторних задачах і теорії імовірності .
Узагальненням біноміального коефіцієнта є поліноміальний коефіцієнт .
(
n
k
)
=
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
{\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}
(
n
k
)
=
n
n
−
k
(
n
−
1
k
)
{\displaystyle {n \choose k}={\frac {n}{n-k}}{n-1 \choose k}}
(
n
0
)
+
(
n
1
)
+
⋯
+
(
n
n
)
=
2
n
{\displaystyle {n \choose 0}+{n \choose 1}+\cdots +{n \choose n}=2^{n}}
(
n
0
)
+
(
n
2
)
+
⋯
+
(
n
2
⌊
n
/
2
⌋
)
=
2
n
−
1
{\displaystyle {n \choose 0}+{n \choose 2}+\cdots +{n \choose 2\lfloor n/2\rfloor }=2^{n-1}}
(
n
0
)
2
+
(
n
1
)
2
+
⋯
+
(
n
n
)
2
=
(
2
n
n
)
{\displaystyle {n \choose 0}^{2}+{n \choose 1}^{2}+\cdots +{n \choose n}^{2}={2n \choose n}}
∑
k
=
0
n
(
r
m
+
k
)
(
s
n
−
k
)
=
(
r
+
s
m
+
n
)
{\displaystyle \sum _{k=0}^{n}{r \choose m+k}{s \choose n-k}={r+s \choose m+n}}
(згортка Вандермонда )
Тотожність
(
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
n
)
∼
2
2
n
π
n
{\displaystyle {2n \choose 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}{n \choose k}\leq {\frac {n}{(n/2-m)^{2}}}2^{n-3}}
при
m
≤
n
/
2
{\displaystyle m\leq n/2}
(нерівність Чебишева )
∑
k
=
0
m
(
n
k
)
≤
2
n
H
(
m
/
n
)
{\displaystyle \sum _{k=0}^{m}{n \choose k}\leq 2^{nH(m/n)}}
(ентропійна оцінка ), де
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 }{n \choose k}\leq 2^{n}e^{-2\lambda ^{2}/n}}
(нерівність Чернова )
Алгоритми обчислення [ ред. | ред. код ]
Біноміальні коефіцієнти можуть бути обчислені за допомогою тотожності
(
n
k
)
=
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
{\displaystyle {n \choose k}={n-1 \choose k}+{n-1 \choose k-1}}
, якщо на кожному кроці зберігати значення
(
n
k
)
{\displaystyle {n \choose k}}
для
k
=
0
,
1
,
…
,
n
{\displaystyle k=0,1,\dots ,n}
. Цей алгоритм особливо ефективний, якщо необхідно отримати всі значення
(
n
k
)
{\displaystyle {n \choose k}}
при фіксованому
n
{\displaystyle n}
. Алгоритм потребує
O
(
n
)
{\displaystyle \ O(n)}
пам'яті (
O
(
n
2
)
{\displaystyle \ O(n^{2})}
для обчислення всієї таблиці) і
O
(
n
2
)
{\displaystyle \ O(n^{2})}
часу.
Інший спосіб ґрунтується на тотожності
(
n
k
)
=
n
n
−
k
(
n
−
1
k
)
{\displaystyle {n \choose k}={\frac {n}{n-k}}{n-1 \choose k}}
. Він дозволяє обчислити значення
(
n
k
)
{\displaystyle {n \choose k}}
при фіксованому
k
{\displaystyle k}
. Алгоритм потребує
O
(
1
)
{\displaystyle \ O(1)}
пам'яті і
O
(
k
)
{\displaystyle \ O(k)}
часу.
#include <iostream>
#include <string>
using namespace std ;
void C ( int n , int m , int startAt = 1 , string s = "" ) {
for ( int i = startAt ; i <= n - m + 1 ; i ++ ) {
if ( 1 == m )
cout << s + ( char )( i + '0' ) << endl ;
else
C ( n , m - 1 , i + 1 , s + ( char )( i + '0' ));
}
}
int main () {
C ( 7 , 3 );
return 0 ;
}