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

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

Биномиальные коэффициенты — коэффициенты в разложении ( 1 + x ) n (1+x)^n по степеням x x (т. н. бином Ньютона): ( 1 + x ) n = ( n 0 ) + ( n 1 ) x + ( n 2 ) x 2 + = k ( n k ) x k . (1+x)^n = {n\choose 0} + {n\choose 1}x + {n\choose 2}x^2 + \cdots = \sum_k {n\choose k} x^k. Значение биномиального коэффициента ( n k ) {n\choose k} определено для всех целых чисел n n и k k . Явные формулы для вычисления биномиальных коэффициентов: ( n k ) = n ! k ! ( n k ) ! = n ( n 1 ) ( n 2 ) . . . ( n k + 1 ) ) k ! {n\choose k} = \frac{n!}{k!\;(n-k)!}= \frac{n(n-1)(n-2)...(n-k+1))}{k!} для 0 k n 0\leq k \leq n ; ( n k ) = 0 {n\choose k} = 0 для k k или 0 n < k 0\leq n < k ; ( n k ) = ( 1 ) k ( n + k 1 k ) {n\choose k} = (-1)^k {-n+k-1\choose k} для n n ,

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

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

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

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

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

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

Тождество ( n k ) = ( n 1 k 1 ) + ( n 1 k ) {n\choose k}={n-1\choose k-1} + {n-1\choose k} позволяет расположить биномиальные коэффициенты для неотрицательных n n , k k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих: 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 \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 k ) = ( n 1 k 1 ) + ( n 1 k ) {n\choose k} = {n-1\choose k-1} + {n-1\choose k}
  2. ( n k ) = ( n n k ) {n\choose k} = {n\choose n-k} (правило симметрии)
  3. ( n 0 ) + ( n 1 ) + + ( n n ) = 2 n {n\choose 0} + {n\choose 1} + \cdots + {n\choose n} = 2^n
  4. ( n 0 ) + ( n 2 ) + + ( n 2 n / 2 ) = 2 n 1 {n\choose 0} + {n\choose 2} + \cdots + {n\choose 2\lfloor n/2\rfloor} = 2^{n-1}
  5. ( n 0 ) 2 + ( n 1 ) 2 + + ( n n ) 2 = ( 2 n n ) {n\choose 0}^2 + {n\choose 1}^2 + \cdots + {n\choose n}^2 = {2n\choose n}
  6. k = 0 n ( r m + k ) ( s n k ) = ( r + s m + n ) \sum_{k=0}^n{r\choose m+k}{s\choose n-k}={r+s\choose m+n} (свёртка Вандермонда)

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

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

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

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

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

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

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

lt:Deriniai