Русская Википедия:Биномиальный коэффициент
Биномиальный коэффициент — коэффициент перед членом разложения бинома Ньютона <math>(1+x)^n</math> по степеням <math>x</math>. Коэффициент при <math>x^k</math> обозначается <math>\textstyle\binom{n}{k}</math> или <math>\textstyle C_n^k</math> и читается «биномиальный коэффициент из <math>n</math> по <math>k</math>» (или «число сочетаний из <math>n</math> по <math>k</math>»):
- <math>(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</math>
для натуральных степеней <math>n</math>.
Биномиальные коэффициенты могут быть также определены для произвольных действительных показателей <math>n</math>. В случае произвольного действительного числа <math>n</math> биномиальные коэффициенты определяются как коэффициенты разложения выражения <math>(1+x)^n</math> в бесконечный степенной ряд:
- <math>(1+x)^n=\sum_{k=0}^{\infty} \binom{n}{k} x^k</math>,
где в случае неотрицательных целых <math>n</math> все коэффициенты <math>\textstyle\binom{n}{k}</math> при <math>k>n</math> обращаются в нуль и поэтому данное разложение является конечной суммой.
В комбинаторике биномиальный коэффициент <math>\textstyle\binom{n}{k}</math> для неотрицательных целых чисел <math>n</math> и <math>k</math> интерпретируется как количество сочетаний из <math>n</math> по <math>k</math>, то есть как количество всех (нестрогих) подмножеств (выборок) размера <math>k</math> в <math>n</math>-элементном множестве.
Биномиальные коэффициенты часто возникают в задачах комбинаторики и теории вероятностей. Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты.
Явные формулы
Вычисляя коэффициенты в разложении <math>(1+x)^n</math> в степенной ряд, можно получить явные формулы для биномиальных коэффициентов <math>\textstyle\binom{n}{k}</math>.
Для всех действительных чисел <math>n</math> и целых чисел <math>k</math>:
- <math>\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}</math>, где <math>k!</math> обозначает факториал числа <math>k</math>.
Для неотрицательных целых <math>n</math> и <math>k</math> также справедливы формулы:
- <math>\binom{n}{k} = \begin{cases}
\frac{n!}{k!(n-k)!}, & 0\leqslant k\leqslant n\\ 0, & k>n \end{cases}</math>.
Для целых отрицательных показателей коэффициенты разложения бинома <math>(1+x)^{-n}</math> равны:
- <math>\binom{-n}{k} = \begin{cases}
(-1)^k\cdot\frac{(n+k-1)!}{k!(n-1)!}, & k\geqslant 0\\ 0, & k<0 \end{cases}</math>.
Треугольник Паскаля
Тождество:
- <math>{n\choose k}={n-1\choose k-1}+{n-1\choose k}</math>
позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел <math>n</math>, <math>k</math> в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:
- <math>\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}</math>. Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от той, что выписана здесь, поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, Омару Хайяму).
Если в каждой строке треугольника Паскаля все числа разделить на <math>2^n</math> (это сумма всех чисел в строке), то все строки при стремлении <math>n</math> к бесконечности примут вид функции нормального распределения.
Свойства
Производящие функции
Для фиксированного значения <math>n</math> производящей функцией последовательности биномиальных коэффициентов <math>\tbinom{n}{0},\;\tbinom{n}{1},\;\tbinom{n}{2}, \dots</math> является:
- <math>\sum_{k=0}^{\infty} \binom{n}{k} x^k = (1+x)^n</math>.
Для фиксированного значения <math>k</math> производящая функция последовательности коэффициентов <math>\tbinom{0}{k},\;\tbinom{1}{k},\;\tbinom{2}{k}, \dots</math> равна:
- <math>\sum_n \binom{n}{k} y^n = \frac{y^k}{(1-y)^{k+1}}</math>.
Двумерной производящей функцией биномиальных коэффициентов <math>\tbinom{n}{k}</math> для целых <math>n,k</math> является:
- <math>\sum_{n,k} \binom{n}{k} x^k y^n = \frac{1}{1-y-xy}</math>, или <math>\sum_{n=0}^\infty\sum_{k=0}^n \binom{n}{k} x^k y^n = \frac{1}{1-y-xy}</math>.
Делимость
Из теоремы Люка следует, что:
- коэффициент <math>\textstyle \binom{n}{k}</math> нечётен <math>\iff</math> в двоичной записи числа <math>k</math> единицы не стоят в тех разрядах, где в числе <math>n</math> стоят нули;
- коэффициент <math>\textstyle \binom{n}{k}</math> некратен простому числу <math>p</math> <math>\iff</math> в <math>p</math>-ичной записи числа <math>k</math> все разряды не превосходят соответствующих разрядов числа <math>n</math>;
- в последовательности биномиальных коэффициентов <math>\textstyle \binom{n}{0},\;\binom{n}{1},\;\ldots,\;\binom{n}{n}</math>:
- все числа не кратны заданному простому <math>p</math> <math>\iff</math> число <math>n</math> представимо в виде <math>mp^k-1</math>, где натуральное число <math>m<p</math>;
- все числа, кроме первого и последнего, кратны заданному простому <math>p</math> <math>\iff</math> <math>n=p^k</math>;
- количество нечётных чисел равно степени двойки, показатель которой равен количеству единиц в двоичной записи числа <math>n</math>;
- чётных и нечётных чисел не может быть поровну;
- количество чисел, не кратных простому <math>p</math>, равно <math>(a_1+1)\cdots(a_m+1)</math>, где числа <math>a_1,\;\ldots,a_m</math> — разряды <math>p</math>-ичной записи числа <math>n</math>; а число <math>\textstyle m=\lfloor\log_p{n}\rfloor + 1</math>, где <math>\lfloor\cdot\rfloor</math> — функция «пол», — это длина данной записи.
Основные тождества
- <math>{n\choose k}={n-1\choose k-1}+{n-1\choose k}</math>.
- <math>\binom{n}{k}=(-1)^k\binom{-n+k-1}{k}</math>.
- <math>{n\choose k}={n\choose n-k}</math> (правило симметрии).
- <math>{n\choose k}=\frac{n}{k}{n - 1\choose k-1}</math> (вынесение за скобки).
- <math>{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}}</math> (замена индексов).
- <math>(n-k){n\choose k}=n{n-1\choose k}</math>.
Бином Ньютона и следствия
- <math>{n\choose 0}+{n\choose 1}+\ldots+{n\choose n}=2^n</math>, где <math>n\in\mathbb{N}</math>.
- <math>\sum_{i+j=m}\binom{n}{j}\binom{n}{i}(-1)^j=
\begin{cases} \binom{n}{m/2}, & \text{если} \ m\equiv 0\pmod{2},\\ 0, & \text{если}\ m\equiv 1\pmod{2}. \end{cases} </math>
- <math>\sum_{j=k}^{n} \binom{n}{j} (-1)^j = (-1)^k \binom{n-1}{k-1}</math>.
- <math>{n\choose 0}-{n\choose 1}+\ldots+(-1)^n{n\choose n}=0</math>, где <math>n\in\mathbb{N}</math>.
- Более сильное тождество: <math>{n\choose 0}+{n\choose 2}+\ldots+{n\choose 2\lfloor n/2\rfloor}=2^{n-1}</math>, где <math>n\in\mathbb{N}</math>.
- <math>\sum_{k=-a}^{a}(-1)^{k}{2a\choose k+a}^3 =\frac{(3a)!}{(a!)^3}</math>,
а более общем виде
- <math>\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!}</math>.
Свёртка Вандермонда и следствия
Шаблон:Stub-section Свёртка Вандермонда:
- <math>\sum_{k}{r\choose m+k}{s\choose n-k}={r+s\choose m+n}</math>,
где <math>m, n\in\mathbb{Z}, </math> а <math>r, s \in\mathbb{R}</math>. Это тождество получается вычислением коэффициента при <math>x^{m+n}</math> в разложении <math>(1+x)^{r} (1+x)^{s}</math> с учётом тождества <math>(1+x)^{r+s}=(1+x)^r(1+x)^s</math>. Сумма берётся по всем целым <math>k</math>, для которых <math>\textstyle{r\choose m+k}{s\choose n-k}\ne0</math>. Для произвольных действительных <math>r</math>, <math>s</math> число ненулевых слагаемых в сумме будет конечно.
Следствие свёртки Вандермонда:
- <math>{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}</math>.
Более общее тождество:
- <math>\sum_{i=0}^{p} (-1)^i{p\choose i}\prod_{m=1}^{n} {i+s_m\choose s_m} =0</math>, если <math>\sum_{m=1}^n{s_m} <p </math>.
Ещё одним следствием свёртки является следующее тождество: <math>{n\choose 0}^2+{n\choose 1}^2+\ldots+{n\choose n}^2={2n\choose n}</math>.
Другие тождества
- <math>\frac{4}{n} \sum_{k=1}^{n}k^2\binom{2n}{n+k}=2^{2n}</math>, где <math>n</math> — натуральное число.
- <math>\sum_{k=1}^n \frac{(-1)^{k-1}}{k}{n \choose k}=\sum_{k=1}^n \frac{1}{k} = H_n</math> — <math>n</math>-е гармоническое число.
- Мультисекция ряда <math>(1+x)^n</math> даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом <math>s</math> и смещением <math>t</math> <math>(0\leqslant t<s)</math> в виде конечной суммы из <math>s</math> слагаемых:
- <math>\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}</math>.
Также имеют место равенства:
- <math>\begin{alignat}{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{alignat}</math>
- <math>\begin{alignat}{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{alignat}</math>
- <math>\begin{alignat}{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{alignat}</math> Откуда следует:
- <math>\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};</math>
- <math>\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};</math>
- <math>\begin{alignat}{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{alignat}</math>
- <math>\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}</math>,
где <math>A_n^k</math> — количество размещений из <math>n</math> по <math>k</math>.
Матричные соотношения
Если взять квадратную матрицу, отсчитав <math>N</math> элементов по катетам треугольника Паскаля и повернув матрицу на любой из четырёх углов, то детерминант этих четырёх матриц равен ±1 при любом <math>N</math>, причём детерминант матрицы с вершиной треугольника в верхнем левом углу равен 1.
В матрице <math>\begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix}</math> числа на диагонали <math>i+j=\mathrm{Const}</math> повторяют числа строк треугольника Паскаля (<math>i, j = 0, 1,\dots</math>). Её можно разложить в произведение двух строго диагональных матриц: нижнетреугольной и получаемой из неё транспонированием:
- <math>\begin{bmatrix}\binom{i+j}{i}\end{bmatrix} = UU^T</math>,
где <math>U=\begin{bmatrix}\tbinom{i}{j}\end{bmatrix}</math>. Обратная матрица к <math>U</math> имеет вид:
- <math> U^{-1}=\begin{bmatrix}(-1)^{i+j}\binom{i}{j}\end{bmatrix}</math>.
Таким образом, можно разложить обратную матрицу к <math>\begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix}</math> в произведение двух строго диагональных матриц: первая матрица — верхнетреугольная, а вторая получается из первой путём транспонирования, что позволяет дать явное выражение для обратных элементов:
- <math>\begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n}=\sum_{k=0}^{p}(-1)^{m+n}\binom{k}{m}\binom{k}{n}</math>, где <math>i</math>, <math>j</math>, <math>m</math>, <math>n = 0 \dots p</math>.
Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы <math>\begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix}</math>, недостаточно приписать новую строку и столбец. Столбец <math>j</math> матрицы <math>\begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix}</math> есть многочлен степени <math>j</math> по аргументу <math>i</math>, следовательно, первые p столбцов образуют полный базис в пространстве векторов длины <math>p</math>+1, чьи координаты могут быть интерполированы многочленом равной или меньшей степени <math>p-1</math>. Нижняя строка матрицы <math>\begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n}</math> ортогональна любому такому вектору.
- <math>\begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{p,n}=\sum_{k=0}^{p}(-1)^{p+n}\binom{k}{p}\binom{k}{n} = (-1)^{p+n}\binom{p}{n}</math>
- <math>\sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{P}_{a}(n) = 0</math> при <math>a<p</math>, где <math>{P}_{a}(n)</math> многочлен степени <math>a</math>.
Если произвольный вектор длины <math>p+1</math> можно интерполировать многочленом степени <math>i < p</math>, то скалярное произведение со строками <math>i+1, i+2, \dots, p</math> (нумерация с 0) матрицы <math>\begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n}</math> равно нулю. Используя тождество выше и равенство единицы скалярного произведения нижней строки матрицы <math>\begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n}</math> на последний столбец матрицы <math>\begin{bmatrix}\tbinom{i+j}{i}\end{bmatrix}</math>, получаем:
- <math>\sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{n}^{p} = p!</math>.
Для показателя большего <math>p</math> можно задать рекуррентную формулу:
- <math>\sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{n}^{p+a} = p!{P}_{2a}(p)={f}_{a}(p)</math>,
где многочлен
- <math>{P}_{2a+2}(p) = \sum_{x=1}^{p} x{P}_{2a}(x);\quad a\geqslant 0;\quad {P}_{0}(p)=1</math>.
Для доказательства сперва устанавливается тождество:
- <math>{f}_{a}(p+1)=\sum_{x=0}^{a} {(p+1)}^{x+1}{f}_{a-x}(p)</math>.
Если требуется найти формулу не для всех показателей степени, то:
- <math>{P}_{2a}(p) = \frac{p}{{2}^{a}}\binom{p+a}{a}{Q}_{a-1}(p);\quad a>0</math>.
Старший коэффициент <math> {Q}_{a-1}(p)</math> равен 1, потребуется a-1 значений, чтобы найти другие коэффициенты:
- <math> {Q}_{a-1}(p)=p(p+1){T}_{a-3}(p)</math> для <math>a\equiv 1\pmod{2}; a\geqslant 3</math>.
Асимптотика и оценки
- <math>\binom{2n}{n}\sim\frac{2^{2n}}{\sqrt{\pi n}}</math>.
- <math>\sum^{m}_{k=0} \binom{n}{k}\leqslant\frac{n}{(n/2-m)^2}2^{n-3}</math> при <math>m<\frac{n}{2}</math> (неравенство Чебышёва).
- <math>\sum\limits_{k=0}^{m} \binom{n}{k}\leqslant 2^{nH(\frac{m}{n})}</math>, при <math>m \le \frac{n}{2}</math> (энтропийная оценка), где <math>H(x)=-x\log_2x-(1-x)\log_2(1-x)</math> — энтропия.
- <math>\sum^{n/2-\lambda}_{k=0} \binom{n}{k}\leqslant 2^ne^{-2\lambda^2/n}</math> (неравенство Чернова).
Непосредственно из формулы Стирлинга следует, что для <math>\alpha \in (0;1)</math> верно <math>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}</math>.
Целозначные полиномы
Шаблон:Main Биномиальные коэффициенты <math>\tbinom{x}{0}=1, \tbinom{x}{1}=x, \tbinom{x}{2}=\tfrac{x^2}{2}-\tfrac{x}{2}</math>, … являются целозначными полиномами от <math>x</math>, то есть принимают целые значения при целых значениях <math>x</math>, — это нетрудно понять, например, по треугольнику Паскаля. Более того, они образуют базис целозначных полиномов, в котором все целозначные полиномы выражаются как линейные комбинации с целыми коэффициентами.[1]
В то же время стандартный базис <math>1, x, x^2</math>, … не позволяет выразить все целочисленные полиномы, если использовать только целые коэффициенты, так как уже <math>\tbinom{x}{2}=\tfrac{x^2}{2}-\tfrac{x}{2}</math> имеет дробные коэффициенты при степенях <math>x</math>.
Этот результат обобщается на полиномы многих переменных. А именно, если полином <math>R(x_1, \dots, x_m)</math> степени <math>k</math> имеет вещественные коэффициенты и принимает целые значения при целых значениях переменных, то
- <math>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)</math>,
где <math>P</math> — полином с целыми коэффициентами.[2]
Алгоритмы вычисления
Биномиальные коэффициенты можно вычислить с помощью рекуррентной формулы <math>\tbinom{n}{k}=\tbinom{n-1}{k}+\tbinom{n-1}{k-1}</math>, если на каждом шаге <math>n</math> хранить значения <math>\tbinom{n}{k}</math> при <math>k=\overline{0,1,\;\ldots,n}</math>. Этот алгоритм особенно эффективен, если нужно получить все значения <math>\tbinom{n}{k}</math> при фиксированном <math>n</math>. Алгоритм требует <math>O(n)</math> памяти (<math>O(n^2)</math> при вычислении всей таблицы биномиальных коэффициентов) и <math>O(n^2)</math> времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени), где <math>O</math> — «<math>o</math>» большое.
При фиксированном значении <math>k</math> биномиальные коэффициенты могут быть вычислены по рекуррентной формуле <math>\tbinom{n}{k}=\tfrac{n}{n-k}\cdot\tbinom{n-1}{k}</math> с начальным значением <math>\tbinom{k}{k}=1</math>. Для вычисления значения <math>\tbinom{n}{k}</math> этот метод требует <math>O(1)</math> памяти и <math>O(n)</math> времени.
Если требуется вычислить коэффициенты <math>\tbinom{n}{k}</math> при фиксированном значении <math>n</math>, можно воспользоваться формулой <math>\tbinom{n}{k}=\tfrac{n-k+1}{k}\cdot\tbinom{n}{k-1}</math> при начальном условии <math>\tbinom{n}{0}=1</math>. При каждом шаге итерации числитель уменьшается на <math>1</math> (начальное значение равно <math>n</math>), а знаменатель соответственно увеличивается на <math>1</math> (начальное значение — <math>1</math>). Для вычисления значения <math>\tbinom{n}{k}</math> этот метод требует <math>O(1)</math> памяти и <math>O(k)</math> времени.
Примечания
Литература
