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

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

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

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

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

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

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

Для всех действительных чисел  и целых чисел :
 ,
где  обозначает факториал числа .

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

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

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

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

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

Свойства

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

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

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

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

Основные тождества 

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

Бином Ньютона и следствия 
 , где .
 
 .
 , где .
 Более сильное тождество: , где .
 ,

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

 .

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

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

Следствие свёртки Вандермонда:
 .
Более общее тождество: 
 , если .
Ещё одним следствием свёртки является следующее тождество: 
.

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

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

В матрице  числа на диагонали  повторяют числа строк треугольника Паскаля (). Её можно разложить в произведение двух строго диагональных матриц: нижнетреугольной и получаемой из неё транспонированием:
 ,
где . Обратная матрица к  имеет вид:
 .
Таким образом, можно разложить обратную матрицу к  в произведение двух строго диагональных матриц: первая матрица — верхнетреугольная, а вторая получается из первой путём транспонирования, что позволяет дать явное выражение для обратных элементов:
 , где , , , .
Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы , недостаточно приписать новую строку и столбец. Столбец  матрицы  есть многочлен степени  по аргументу , следовательно, первые p столбцов образуют полный базис в пространстве векторов длины +1, чьи координаты могут быть интерполированы многочленом равной или меньшей степени . Нижняя строка матрицы  ортогональна любому такому вектору.

 

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

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

 .

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

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

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

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

Асимптотика и оценки 
 .
  при  (неравенство Чебышёва).
 , при  (энтропийная оценка), где  — энтропия.
  (неравенство Чернова).
Непосредственно из формулы Стирлинга следует, что для  верно .

Целозначные полиномы 

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

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

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

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

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

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

Примечания

Литература 
 
 
 
 
 
 

Комбинаторика
Факториалы и биномиальные коэффициенты
Целочисленные последовательности