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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\ldots =\sum_{k=0}^{\infty} \binom{n}{k} x^k,

причём n здесь может быть как целым, так и произвольным действительным числом. Для неотрицательных целых n все коэффициенты с индексами k>n в этом ряду являются нулевыми, и поэтому данное разложение представляет собой конечную сумму (см. бином Ньютона).

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

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

Явные формулы[править | править вики-текст]

Значение биномиального коэффициента \textstyle\binom{n}{k} определено для всех действительных чисел n и целых чисел k по формулам:

\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}

где m! обозначает факториал числа m.

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

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

Треугольник Паскаля[править | править вики-текст]

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

Тождество

{n\choose k}={n-1\choose k-1}+{n-1\choose k}

позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел n, k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:

\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°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, О. Хайяму и др.).

Строки в треугольнике Паскаля в пределе стремятся[уточнить] к функции нормального распределения.

Свойства[править | править вики-текст]

Производящие функции[править | править вики-текст]

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

\sum_k \binom{n}{k} x^k = (1+x)^n.

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

\sum_n \binom{n}{k} y^n = \frac{y^k}{(1-y)^{k+1}}.

Двумерной производящей функцией биномиальных коэффициентов \tbinom{n}{k} для целых n,\,k является:

\sum_{n,k} \binom{n}{k} x^k y^n = \frac{1}{1-y-xy}.

Делимость[править | править вики-текст]

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

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

Основные тождества[править | править вики-текст]

  • {n\choose k}={n-1\choose k-1}+{n-1\choose k}.
  • \binom{n}{k}=(-1)^k\binom{-n+k-1}{k}.
  • {n\choose k}={n\choose n-k} (правило симметрии).
  • {n\choose k}=\frac{n}{k}{n-1\choose k-1} (вынесение за скобки).
  • {n\choose m}{m\choose k}={n\choose k}{n-k\choose m-k} (замена индексов).

Бином Ньютона и следствия[править | править вики-текст]

  • {n\choose 0}+{n\choose 1}+\ldots+{n\choose n}=2^n.
  • \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}
  • \sum_{j=k}^{n} \binom{n}{j} (-1)^j = (-1)^k \binom{n-1}{k-1}.
  • {n\choose 0}-{n\choose 1}+\ldots+(-1)^n{n\choose n}=0. Это тождество можно усилить:
  • {n\choose 0}+{n\choose 2}+\ldots+{n\choose 2\lfloor n/2\rfloor}=2^{n-1}.
  • \sum_{k=-a}^{a}(-1)^{k}{2a\choose k+a}^3 =\frac{(3a)!}{(a!)^3}

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

\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=-\infty}^{+\infty}{r\choose m+k}{s\choose n-k}={r+s\choose m+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}.
  • \sum_{i=0}^{p} (-1)^i{p\choose i}\prod_{m=1}^{n} {i+s_m\choose s_m} =0, если \sum_{m=1}^n{s_m} <p , — более общий вид тождества выше.
  • {n\choose 0}^2+{n\choose 1}^2+\ldots+{n\choose n}^2={2n\choose n}.

Другие тождества[править | править вики-текст]

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

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

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

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

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

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

\begin{bmatrix}\binom{i+j}{i}\end{bmatrix}^{-1}_{m,n}=\sum_{k=0}^{p}(-1)^{m+n}\binom{k}{m}\binom{k}{n}, где i, j , m, n = 0..p.

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

\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}
\sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{P}_{a}(n) = 0 при a<p, где {P}_{a}(n) многочлен степени a.

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

\sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{n}^{p} = p!.

Для показателя большего p можно задать рекуррентную формулу:

\sum_{n=0}^{p}(-1)^{p+n}\binom{p}{n}{n}^{p+a} = p!{P}_{2a}(p)={f}_{a}(p),

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

{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)=\sum_{x=0}^{a} {(p+1)}^{x+1}{f}_{a-x}(p).

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

{P}_{2a}(p) = \frac{p}{{2}^{a}}\binom{p+a}{a}{Q}_{a-1}(p);\quad a>0.

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

 {Q}_{a-1}(p)=p(p+1){T}_{a-3}(p) для a\equiv 1\pmod{2}; a\geqslant 3.

Асимптотика и оценки[править | править вики-текст]

Алгоритмы вычисления[править | править вики-текст]

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

При фиксированном значении k биномиальные коэффициенты могут быть вычислены по рекуррентной формуле \tbinom{n}{k}=\frac{n}{n-k}\tbinom{n-1}{k} с начальным значением \tbinom{k}{k}=1. Для вычисления значения \tbinom{n}{k} этот метод требует O(1) памяти и O(n) времени.

См. также[править | править вики-текст]

Литература[править | править вики-текст]