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

Разделы:

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

(1+x)n=(n0)+(n1)x+(n2)x2+…+(nn)xn=∑k=0n(nk)xk,{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 (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{displaystyle n} $n$ .

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

(1+x)a=∑k=0∞(ak)xk,{displaystyle (1+x)^{a}=sum _{k=0}^{infty }{binom {a}{k}}x^{k},}

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

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

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

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

Содержание

1 Явные формулы
2 Треугольник Паскаля
3 Свойства
4 Алгоритмы вычисления
5 См. также
6 Примечания
7 Литература

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

Вычисляя коэффициенты в разложении (1+x)n{displaystyle (1+x)^{n}}

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

Для всех действительных чисел n и целых чисел k:

(nk)={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!}},&kgeqslant 0,,&k<0,end{cases}}}

{binom {n}{k}}={begin{cases}{frac {n(n-1)(n-2)cdot ldots cdot (n-k+1)}{k!}},&kgeqslant 0,�,&k<0,end{cases}}

где k!{displaystyle k!}

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

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

(nk)={n!k!(n−k)!,0⩽k⩽n.0,k>n.{displaystyle {binom {n}{k}}={begin{cases}{frac {n!}{k!(n-k)!}},&0leqslant kleqslant n.,&k>n.end{cases}}}

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

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

${displaystyle (1+x)^{-n}}$ равны

(−nk)={(−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)!}},&kgeqslant 0.,&k<0.end{cases}}}

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

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

Основная статья: Треугольник Паскаля

Тождество

(nk)=(n−1k−1)+(n−1k){displaystyle {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 в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:

n=0:1n=1:11n=2:121n=3:1331n=4:14641⋮⋮⋮⋮⋮{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&&1vdots &&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&&1vdots &&vdots &&vdots &&vdots &&vdots &end{matrix}}

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

Строки в треугольнике Паскаля, делённые на 2n{displaystyle 2^{n}}

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

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

Свойства

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

Для фиксированного значения n производящей функцией последовательности биномиальных коэффициентов (n0),(n1),(n2),…{displaystyle {tbinom {n}{0}},;{tbinom {n}{1}},;{tbinom {n}{2}},;ldots }

${tbinom {n}{0}},;{tbinom {n}{1}},;{tbinom {n}{2}},;ldots$ является:

∑k(nk)xk=(1+x)n.{displaystyle sum _{k}{binom {n}{k}}x^{k}=(1+x)^{n}.}

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

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

${tbinom {0}{k}},;{tbinom {1}{k}},;{tbinom {2}{k}},;ldots$ является:

∑n(nk)yn=yk(1−y)k+1.{displaystyle 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}}}}.

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

$tbinom{n}{k}$ для целых n,k{displaystyle n,,k} $n,,k$ является:

∑n,k(nk)xkyn=11−y−xy.{displaystyle 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}}.

Делимость

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

(nk){displaystyle textstyle {binom {n}{k}}} $textstyle {binom {n}{k}}$ нечётен ⟺{displaystyle iff } $iff$ в двоичной записи числа k единицы не стоят в тех разрядах, где в числе n стоят нули.
(nk){displaystyle textstyle {binom {n}{k}}} $textstyle {binom {n}{k}}$ некратен простому p ⟺{displaystyle iff } $iff$ в p-ичной записи числа k все разряды не превосходят соответствующих разрядов числа n.
В последовательности биномиальных коэффициентов (n0),(n1),…,(nn){displaystyle textstyle {binom {n}{0}},;{binom {n}{1}},;ldots ,;{binom {n}{n}}} :
- все числа не кратны заданному простому p ⟺{displaystyle iff } $iff$ n=mpk−1{displaystyle n=mp^{k}-1} $n=mp^{k}-1$ , где натуральное число m < p;
- все числа, кроме первого и последнего, кратны заданному простому p ⟺{displaystyle iff } $iff$ n=pk{displaystyle n=p^{k}} $n=p^{k}$ ;
- количество нечётных чисел равно степени двойки (степень двойки равна количеству единиц в двоичной записи числа n);
- не может быть поровну чётных и нечётных чисел;
- количество не кратных простому p чисел равно (a1+1)⋯(am+1){displaystyle (a_{1}+1)cdots (a_{m}+1)} $(a_{1}+1)cdots (a_{m}+1)$ , где числа a1,…,am{displaystyle a_{1},;ldots ,;a_{m}} $a_{1},;ldots ,;a_{m}$ — разряды p-ичной записи числа n; а число m=⌊logp⁡n⌋+1{displaystyle textstyle m=lfloor log _{p}{n}rfloor +1} $textstyle m=lfloor log _{p}{n}rfloor +1$ — её длина.

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

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

(nk)=(n−1k−1)+(n−1k).{displaystyle {n choose k}={n-1 choose k-1}+{n-1 choose k}.} ${n choose k}={n-1 choose k-1}+{n-1 choose k}.$
(nk)=(−1)k(−n+k−1k).{displaystyle {binom {n}{k}}=(-1)^{k}{binom {-n+k-1}{k}}.} ${binom {n}{k}}=(-1)^{k}{binom {-n+k-1}{k}}.$
(nk)=(nn−k){displaystyle {n choose k}={n choose n-k}} ${n choose k}={n choose n-k}$ (правило симметрии).
(nk)=nk(n−1k−1){displaystyle {n choose k}={frac {n}{k}}{n-1 choose k-1}} ${n choose k}={frac {n}{k}}{n-1 choose k-1}$ (вынесение за скобки).
(nm)(mn−k)=(nk)(kn−m){displaystyle {n choose m}{m choose n-k}={n choose k}{k choose n-m}} ${displaystyle {n choose m}{m choose n-k}={n choose k}{k choose n-m}}$ (замена индексов).
(n−k)(nk)=n(n−1k){displaystyle (n-k){n choose k}=n{n-1 choose k}} ${displaystyle (n-k){n choose k}=n{n-1 choose k}}$ .

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

(n0)+(n1)+…+(nn)=2n,{displaystyle {n choose 0}+{n choose 1}+ldots +{n choose n}=2^{n},} ${displaystyle {n choose 0}+{n choose 1}+ldots +{n choose n}=2^{n},}$ где n∈N.{displaystyle nin mathbb {N} .} ${displaystyle nin mathbb {N} .}$
∑i+j=m(nj)(ni)(−1)j={(−1)m/2(nm/2)if m≡0(mod2),0if m≡1(mod2).{displaystyle sum _{i+j=m}{binom {n}{j}}{binom {n}{i}}(-1)^{j}={begin{cases}(-1)^{m/2}{binom {n}{m/2}}&{text{if}} mequiv 0{pmod {2}},&{text{if}} mequiv 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}} mequiv 0{pmod {2}},�&{text{if}} mequiv 1{pmod {2}}.end{cases}}$
∑j=kn(nj)(−1)j=(−1)k(n−1k−1).{displaystyle 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}}.$
(n0)−(n1)+…+(−1)n(nn)=0,{displaystyle {n choose 0}-{n choose 1}+ldots +(-1)^{n}{n choose n}=0,} ${displaystyle {n choose 0}-{n choose 1}+ldots +(-1)^{n}{n choose n}=0,}$ где n∈N.{displaystyle nin mathbb {N} .} ${displaystyle nin mathbb {N} .}$ Это тождество можно усилить:
(n0)+(n2)+…+(n2⌊n/2⌋)=2n−1,{displaystyle {n choose 0}+{n choose 2}+ldots +{n choose 2lfloor n/2rfloor }=2^{n-1},} ${displaystyle {n choose 0}+{n choose 2}+ldots +{n choose 2lfloor n/2rfloor }=2^{n-1},}$ где n∈N.{displaystyle nin mathbb {N} .} ${displaystyle nin mathbb {N} .}$
∑k=−aa(−1)k(2ak+a)3=(3a)!(a!)3{displaystyle 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}}}$

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

∑k=−aa(−1)k(a+ba+k)(b+cb+k)(c+ac+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!}},,}

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(rm+k)(sn−k)=(r+sm+n){displaystyle sum _{k}{r choose m+k}{s choose n-k}={r+s choose m+n}} ${displaystyle sum _{k}{r choose m+k}{s choose n-k}={r+s choose m+n}}$ (свёртка Вандермонда), где m,n∈Z,r,s∈R.{displaystyle m,nin mathbb {Z} ,r,sin mathbb {R} .} ${displaystyle m,nin mathbb {Z} ,r,sin mathbb {R} .}$

Получается вычислением коэффициента при xm+n{displaystyle x^{m+n}}

${displaystyle x^{m+n}}$ в тождестве (1+x)r(1+x)s=(1+x)r+s{displaystyle (1+x)^{r}(1+x)^{s}=(1+x)^{r+s}} ${displaystyle (1+x)^{r}(1+x)^{s}=(1+x)^{r+s}}$ . Сумма берётся по всем целым k{displaystyle k} $k$ , для которых слагаемое отлично от нуля. Для произвольных действительных r{displaystyle r} $r$ , s{displaystyle s} $s$ число ненулевых слагаемых в сумме будет конечно.

(n0)(aa)−(n1)(a+1a)+…+(−1)n(nn)(a+na)=(−1)n(an){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}} ${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=0p(−1)i(pi)∏m=1n(i+smsm)=0{displaystyle 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$ , если ∑m=1nsm<p{displaystyle sum _{m=1}^{n}{s_{m}}<p} $sum _{{m=1}}^{n}{s_{m}}<p$ , — более общий вид тождества выше.
(n0)2+(n1)2+…+(nn)2=(2nn).{displaystyle {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}.$

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

∑k=1m(−1)k−1k(mk)=∑k=1m1k=Hm{displaystyle 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{displaystyle (1+x)^{n}} $(1+x)^{n}$ даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом s и смещением t (0⩽t<s){displaystyle (0leqslant t<s)} $(0leqslant t<s)$ в виде замкнутой суммы из s слагаемых:

(nt)+(nt+s)+(nt+2s)+…=1s∑j=0s−1(2cos⁡πjs)ncos⁡π(n−2t)js.{displaystyle {binom {n}{t}}+{binom {n}{t+s}}+{binom {n}{t+2s}}+ldots ={frac {1}{s}}sum _{j=0}^{s-1}left(2cos {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(2cos {frac {pi j}{s}}right)^{n}cos {frac {pi (n-2t)j}{s}}.

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

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

В матрице [(i+ji)]{displaystyle {begin{bmatrix}{tbinom {i+j}{i}}end{bmatrix}}}

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

[(i+ji)]=UUT,{displaystyle {begin{bmatrix}{binom {i+j}{i}}end{bmatrix}}=UU^{T},}

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

где U=[(ij)]{displaystyle U={begin{bmatrix}{tbinom {i}{j}}end{bmatrix}}}

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

U−1=[(−1)i+j(ij)].{displaystyle U^{-1}={begin{bmatrix}(-1)^{i+j}{binom {i}{j}}end{bmatrix}}.}

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

Таким образом, можно разложить обратную матрицу к [(i+ji)]{displaystyle {begin{bmatrix}{tbinom {i+j}{i}}end{bmatrix}}}

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

[(i+ji)]m,n−1=∑k=0p(−1)m+n(km)(kn){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}}}

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

Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы [(i+ji)]{displaystyle {begin{bmatrix}{tbinom {i+j}{i}}end{bmatrix}}}

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

[(i+ji)]p,n−1=∑k=0p(−1)p+n(kp)(kn)=(−1)p+n(pn){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}}}

{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=0p(−1)p+n(pn)Pa(n)=0{displaystyle 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{displaystyle a<p}

a<p

, где Pa(n){displaystyle {P}_{a}(n)}

{P}_{{a}}(n)

многочлен степени a.

Если произвольный вектор длины p+1{displaystyle p+1}

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

∑n=0p(−1)p+n(pn)np=p!.{displaystyle 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 можно задать рекуррентную формулу:

∑n=0p(−1)p+n(pn)np+a=p!P2a(p)=fa(p),{displaystyle 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),

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

P2a+2(p)=∑x=1pxP2a(x);a⩾0;P0(p)=1.{displaystyle {P}_{2a+2}(p)=sum _{x=1}^{p}x{P}_{2a}(x);quad ageqslant 0;quad {P}_{0}(p)=1.}

{P}_{{2a+2}}(p)=sum _{{x=1}}^{{p}}x{P}_{{2a}}(x);quad ageqslant 0;quad {P}_{{0}}(p)=1.

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

fa(p+1)=∑x=0a(p+1)x+1fa−x(p).{displaystyle {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).

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

P2a(p)=p2a(p+aa)Qa−1(p);a>0.{displaystyle {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.

Старший коэффициент Qa−1(p){displaystyle {Q}_{a-1}(p)}

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

Qa−1(p)=p(p+1)Ta−3(p){displaystyle {Q}_{a-1}(p)=p(p+1){T}_{a-3}(p)}

{Q}_{{a-1}}(p)=p(p+1){T}_{{a-3}}(p)

для a≡1(mod2);a⩾3.{displaystyle aequiv 1{pmod {2}};ageqslant 3.}

aequiv 1{pmod {2}};ageqslant 3.

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

(2nn)∼22nπn.{displaystyle {binom {2n}{n}}sim {frac {2^{2n}}{sqrt {pi n}}}.} ${binom {2n}{n}}sim {frac {2^{{2n}}}{{sqrt {pi n}}}}.$
∑k=0m(nk)⩽n(n/2−m)22n−3{displaystyle 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<n2{displaystyle m<{frac {n}{2}}} $m<{frac {n}{2}}$ (неравенство Чебышёва).
∑k=0m(nk)⩽2nH(mn){displaystyle 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≤n2{displaystyle mleq {frac {n}{2}}} $mleq {frac {n}{2}}$ (энтропийная оценка), где H(x)=−xlog2⁡x−(1−x)log2⁡(1−x){displaystyle H(x)=-xlog _{2}x-(1-x)log _{2}(1-x)} $H(x)=-xlog _{2}x-(1-x)log _{2}(1-x)$ — энтропия.
∑k=0n/2−λ(nk)⩽2ne−2λ2/n{displaystyle sum _{k=0}^{n/2-lambda }{binom {n}{k}}leqslant 2^{n}e^{-2lambda ^{2}/n}} $sum _{{k=0}}^{{n/2-lambda }}{binom {n}{k}}leqslant 2^{n}e^{{-2lambda ^{2}/n}}$ (неравенство Чернова).

Непосредственно из формулы Стирлинга следует, что для α∈(0;1){displaystyle alpha in (0;1)}

$alpha in (0;1)$ верно Cnαn∼12πα(1−α)n(1α)αn(11−α)(1−α)n=(1αα(1−α)(1−α)+o(1))n{displaystyle C_{n}^{alpha n}sim {sqrt {frac {1}{2pi 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}{2pi 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}}$ .

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

Основная статья: Целозначный многочлен

Нетрудно видеть, что биномиальные коэффициенты (x0)=1,(x1)=x,(x2)=x22−x2,…{displaystyle {tbinom {x}{0}}=1,{tbinom {x}{1}}=x,{tbinom {x}{2}}={tfrac {x^{2}}{2}}-{tfrac {x}{2}},dots }

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

В то же время стандартный базис 1,x,x2,…{displaystyle 1,x,x^{2},dots }

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

Этот результат обобщается на полиномы многих переменных. А именно, если полином R(x1,…,xm){displaystyle R(x_{1},dots ,x_{m})}

$R(x_1, dots, x_m)$ степени k{displaystyle k} $k$ имеет вещественные коэффициенты и принимает целые значения при целых значениях переменных, то

R(x1,…,xm)=P((x11),…,(x1k),…,(xm1),…,(xmk)),{displaystyle R(x_{1},dots ,x_{m})=Pleft({binom {x_{1}}{1}},dots ,{binom {x_{1}}{k}},dots ,{binom {x_{m}}{1}},dots ,{binom {x_{m}}{k}}right),}

{displaystyle R(x_{1},dots ,x_{m})=Pleft({binom {x_{1}}{1}},dots ,{binom {x_{1}}{k}},dots ,{binom {x_{m}}{1}},dots ,{binom {x_{m}}{k}}right),}

где P{displaystyle P}

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

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

Биномиальные коэффициенты могут быть вычислены с помощью формулы (nk)=(n−1k)+(n−1k−1){displaystyle {tbinom {n}{k}}={tbinom {n-1}{k}}+{tbinom {n-1}{k-1}}}

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

При фиксированном значении k биномиальные коэффициенты могут быть вычислены по рекуррентной формуле (nk)=nn−k⋅(n−1k){displaystyle {tbinom {n}{k}}={tfrac {n}{n-k}}cdot {tbinom {n-1}{k}}}

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

Если требуется вычислить коэффициенты (nk){displaystyle {tbinom {n}{k}}}

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

См. также

Примечания

↑ Прасолов В. В. Глава 12. Целозначные многочлены // Многочлены. — М.: МЦНМО, 1999, 2001, 2003.
↑ Ю. Матиясевич. Десятая проблема Гильберта. — Наука, 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.