Открыть главное меню

В математике биномиальные коэффициенты — это коэффициенты в разложении бинома Ньютона по степеням x. Коэффициент при обозначается или и читается «биномиальный коэффициент из n по k» (или «число сочетаний из n по k», читается как «це из n по k»):

(1)

для натуральных степеней .

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

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

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

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

Явные формулыПравить

Вычисляя коэффициенты в разложении   в степенной ряд, мы получим явные формулы для биномиальных коэффициентов   .

Для всех действительных чисел n и целых чисел k:

 

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

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

 

Для целых отрицательных показателей степени коэффициенты разложения   равны

 

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

Основная статья: Треугольник Паскаля

Тождество

 

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

 

Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от выписанной здесь поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, О. Хайяму и др.).

Строки в треугольнике Паскаля, делённые на   (сумма всех чисел в строке), в пределе стремятся к функции нормального распределения.

 
Визуализация биномиального коэффициента до 4 степени

Визуализация биномиального коэффициента до 4 степени [1]

СвойстваПравить

Производящие функцииПравить

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

 

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

 

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

 

ДелимостьПравить

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

  •   нечётен   в двоичной записи числа k единицы не стоят в тех разрядах, где в числе n стоят нули.
  •   некратен простому p   в p-ичной записи числа k все разряды не превосходят соответствующих разрядов числа n.
  • В последовательности биномиальных коэффициентов  :
    • все числа не кратны заданному простому p    , где натуральное число m < p;
    • все числа, кроме первого и последнего, кратны заданному простому p    ;
    • количество нечётных чисел равно степени двойки (степень двойки равна количеству единиц в двоичной записи числа n);
    • не может быть поровну чётных и нечётных чисел;
    • количество не кратных простому p чисел равно  , где числа   — разряды p-ичной записи числа n; а число   — её длина.

Основные тождестваПравить

  •  
  •  
  •   (правило симметрии).
  •   (вынесение за скобки).
  •   (замена индексов).
  •  .

Бином Ньютона и следствияПравить

  •   где  
  •  
  •  
  •   где   Это тождество можно усилить:
  •   где  
  •  

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

 

Свёртка Вандермонда и следствияПравить

  •   (свёртка Вандермонда), где  

Получается вычислением коэффициента при   в тождестве  . Сумма берётся по всем целым  , для которых слагаемое отлично от нуля. Для произвольных действительных  ,   число ненулевых слагаемых в сумме будет конечно.

  •  .
  •  , если  , — более общий вид тождества выше.
  •  

Другие тождестваПравить

  •  m-ое гармоническое число.
  • Мультисекция ряда   даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом s и смещением t   в виде замкнутой суммы из s слагаемых:
 

Матричные соотношенияПравить

Если взять квадратную матрицу, отсчитав N элементов по катетам треугольника Паскаля и повернув матрицу на любой из четырёх углов, то детерминант этих четырёх матриц равен ±1 при любом N, причём детерминант матрицы с вершиной треугольника в верхнем левом углу равен 1.

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

 

где  . Обратная матрица к U имеет вид:

 

Таким образом, можно разложить обратную матрицу к   в произведение двух строго диагональных матриц: первая матрица — верхнетреугольная, а вторая получается из первой путём транспонирования, что позволяет дать явное выражение для обратных элементов:

 , где i, j , m, n = 0..p.

Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы  , недостаточно приписать новую строку и столбец. Столбец j матрицы   есть многочлен степени j по аргументу i, следовательно, первые p столбцов образуют полный базис в пространстве векторов длины p+1, чьи координаты могут быть интерполированы многочленом равной или меньшей степени p-1. Нижняя строка матрицы   ортогональна любому такому вектору.

 
  при  , где   многочлен степени a.

Если произвольный вектор длины   можно интерполировать многочленом степени  , то скалярное произведение со строками   (нумерация с 0) матрицы   равно нулю. Используя тождество выше и равенство единицы скалярного произведения нижней строки матрицы   на последний столбец матрицы  , получаем:

 

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

 

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

 

Для доказательства сперва доказывается тождество:

 

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

 

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

  для  

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

  •  
  •   при   (неравенство Чебышёва).
  •  , при   (энтропийная оценка), где   — энтропия.
  •   (неравенство Чернова).

Непосредственно из формулы Стирлинга следует, что для   верно  .

Целозначные полиномыПравить

Основная статья: Целозначный многочлен

Нетрудно видеть, что биномиальные коэффициенты   являются целозначными полиномами от  , т.е. принимают целые значения при целых значениях  . Более того, они образуют базис целозначных полиномов, в котором все целозначные полиномы выражаются как линейные комбинации с целыми коэффициентами.[1]

В то же время стандартный базис   не позволяет выразить все целочисленные полиномы, используя только целые коэффициенты, так как уже   имеет дробные коэффициенты при степенях  .

Этот результат обобщается на полиномы многих переменных. А именно, если полином   степени   имеет вещественные коэффициенты и принимает целые значения при целых значениях переменных, то

 

где   — полином с целыми коэффициентами.[2]

Алгоритмы вычисленияПравить

Биномиальные коэффициенты могут быть вычислены с помощью формулы  , если на каждом шаге хранить значения   при  . Этот алгоритм особенно эффективен, если нужно получить все значения   при фиксированном  . Алгоритм требует   памяти (  при вычислении всей таблицы биномиальных коэффициентов) и   времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).

При фиксированном значении k биномиальные коэффициенты могут быть вычислены по рекуррентной формуле   с начальным значением  . Для вычисления значения   этот метод требует   памяти и   времени.

Если требуется вычислить коэффициенты   при фиксированном значении   можно воспользоваться формулой   при начальном задании  . При каждом шаге итерации числитель уменьшается на   (начальное значение  ), а знаменатель соответственно увеличивается на   (начальное значение  ). Для вычисления значения   этот метод требует   памяти и   времени.

См. такжеПравить

ПримечанияПравить

  1. Прасолов В. В. Глава 12. Целозначные многочлены // Многочлены. — М.: МЦНМО, 1999, 2001, 2003.
  2. Ю. Матиясевич. Десятая проблема Гильберта. — Наука, 1993.

ЛитератураПравить