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

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

Биномиальные коэффициенты — коэффициенты в разложении \((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\leq n < k\); $${n\choose k} = (-1)^k {-n+k-1\choose k}$$для \(n\),

где \(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)=-x\log_2x-(1-x)\log_2(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(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)\) времени.

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

Ссылки[править]