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

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

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

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

,

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

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

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

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

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

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

 ,

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

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

 .

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

 .

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

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

Тождество:

 

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

 .

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

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

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

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

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

 .

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

 .

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

 , или  .

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

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

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

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

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

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

  •  , где  .
  •  
  •  .
  •  , где  .
  • Более сильное тождество:  , где  .
  •  ,

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

 .

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

Свёртка Вандермонда:

 ,

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

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

 .

Более общее тождество:

 , если  .

Ещё одним следствием свёртки является следующее тождество:  .

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

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

Также имеют место равенства:

 
 
 

Откуда следует:

 
 
 
 ,

где   — количество размещений из   по  .

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

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

В матрице   числа на диагонали   повторяют числа строк треугольника Паскаля ( ). Её можно разложить в произведение двух строго диагональных матриц: нижнетреугольной и получаемой из неё транспонированием:

 ,

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

 .

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

 , где  ,  ,  ,  .

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

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

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

 .

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

 ,

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

 .

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

 .

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

 .

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

  для  .

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

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

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

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

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

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

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

 ,

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

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

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

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

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

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

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

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