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

Биномиальные коэффициенты — коэффициенты в разложении (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.

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

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

Содержание

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

Тождество

{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°. Таблицы для изображения биномиальных коэффициентов были известны и ранее.

Свойства

Интересно, что если рассмотреть ряды в треугольнике Паскаля, состоящие из биномиальных коэффициентов, то в пределе получим функцию нормального распределения - распределение Гаусса.

Тождества

  1. {n\choose k} = {n-1\choose k-1} + {n-1\choose k}
  2. {n\choose k} = {n\choose n-k} (правило симметрии)
  3. {n\choose 0} + {n\choose 1} + \cdots + {n\choose n} = 2^n
  4. {n\choose 0} + {n\choose 2} + \cdots + {n\choose 2\lfloor n/2\rfloor} = 2^{n-1}
  5. {n\choose 0}^2 + {n\choose 1}^2 + \cdots + {n\choose n}^2 = {2n\choose n}
  6. \sum_{k=0}^n{r\choose m+k}{s\choose n-k}={r+s\choose m+n} (свёртка Вандермонда)

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

  1. {2n\choose n}\sim \frac{2^{2n}}{\sqrt{\pi n}}
  2. \sum^{m}_{k=0}{n\choose k}\le \frac{n}{(n/2-m)^2}2^{n-3} при m\le n/2 (неравенство Чебышёва)
  3. \sum^{m}_{k=0}{n\choose k}\le 2^{nH(m/n)} (энтропийная оценка), где H(x) = − xlog2x − (1 − x)log2(1 − x)энтропия.
  4. \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(n2) при вычислении всей таблицы биномиальных коэффициентов) и O(n2) времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).

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

См. также

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home