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

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

Биномиальные коэффициенты — коэффициенты в разложении $(1 + x) n$ по степеням $x$ (т. н. бином Ньютона):

$(1+x)^n = {n\choose 0} + {n\choose 1}x + {n\choose 2}x^2 + \cdots = \sum_k {n\choose k} x^k.$

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

${n\choose k} = \frac{n!}{k!\;(n-k)!}= \frac{n(n-1)(n-2)...(n-k+1))}{k!}$ для $0\leq k \leq n$ ;

${n\choose k} = 0$ для

k < 0

или $0\leq n < k$ ;

${n\choose k} = (-1)^k {-n+k-1\choose k}$ для $n<0\leq k$ ,

где $n!$ и $k!$ — факториалы чисел $n$ и $k$ .

Биномиальный коэффициент ${n\choose k}$ является обобщением числа сочетаний $C^k_n$ , которое определено только для неотрицательных целых чисел $n$ , $k$ .

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

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

Содержание

1 Треугольник Паскаля
2 Свойства
3 Тождества
4 Асимптотика и оценки
5 Алгоритмы вычисления биномиальных коэффициентов
6 См. также

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

Тождество

${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\choose k} = {n-1\choose k-1} + {n-1\choose k}$
${n\choose k} = {n\choose n-k}$ (правило симметрии)
${n\choose 0} + {n\choose 1} + \cdots + {n\choose n} = 2^n$
${n\choose 0} + {n\choose 2} + \cdots + {n\choose 2\lfloor n/2\rfloor} = 2^{n-1}$
${n\choose 0}^2 + {n\choose 1}^2 + \cdots + {n\choose n}^2 = {2n\choose n}$
$\sum_{k=0}^n{r\choose m+k}{s\choose n-k}={r+s\choose m+n}$ (свёртка Вандермонда)

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

${2n\choose n}\sim \frac{2^{2n}}{\sqrt{\pi n}}$
$\sum^{m}_{k=0}{n\choose k}\le \frac{n}{(n/2-m)^2}2^{n-3}$ при $m\le n/2$ (неравенство Чебышёва)
$\sum^{m}_{k=0}{n\choose k}\le 2^{nH(m/n)}$ (энтропийная оценка), где $H (x) = - x log 2 x - (1 - x)log 2 (1 - x)$ — энтропия.
$\sum^{n/2-\lambda}_{k=0}{n\choose k} \le 2^ne^{-2\lambda^2/n}$ (неравенство Чернова)

[править] Алгоритмы вычисления биномиальных коэффициентов

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

Второй способ основан на тождестве ${n\choose k}=\frac{n}{n-k}{n-1\choose k}$ . Он позволяет вычислить значения ${n\choose k}$ при фиксированном $k$ . Алгоритм требует $O (1)$ памяти ( $O (l)$ если нужно посчитать $l$ последовательных коэффициентов с фиксированным $k$ ) и $O (k)$ времени.