WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

• ${\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 m}{m \choose n-k}={n \choose k}{k \choose n-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}(-1)^{m/2}{\binom {n}{m/2}}&{\text{if}}\ m\equiv 0{\pmod {2}},\\0&{\text{if}}\ 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} ,r,s\in \mathbb {R} .}$

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

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

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

где ${\displaystyle U={\begin{bmatrix}{\tbinom {i}{j}}\end{bmatrix}}}$ . Обратная матрица к 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}}}$ , где i, j , m, n = 0..p.

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

Для показателя большего 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}},\dots }$ являются целозначными полиномами от ${\displaystyle x}$ , т.е. принимают целые значения при целых значениях ${\displaystyle x}$ . Более того, они образуют базис целозначных полиномов, в котором все целозначные полиномы выражаются как линейные комбинации с целыми коэффициентами.^[1]

В то же время стандартный базис ${\displaystyle 1,x,x^{2},\dots }$ не позволяет выразить все целочисленные полиномы, используя только целые коэффициенты, так как уже ${\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}$ — полином с целыми коэффициентами.^[2]