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

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

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

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

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

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

Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от выписанной здесь поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, О. Хайяму и др.).
Строки в треугольнике Паскаля, делённые на
(сумма всех чисел в строке), в пределе стремятся к функции нормального распределения.
Для фиксированного значения 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 биномиальные коэффициенты могут быть вычислены по рекуррентной формуле
с начальным значением
. Для вычисления значения
этот метод требует
памяти и
времени.
Если требуется вычислить коэффициенты
при фиксированном значении
можно воспользоваться формулой
при начальном задании
. При каждом шаге итерации числитель уменьшается на
(начальное значение
), а знаменатель соответственно увеличивается на
(начальное значение
). Для вычисления значения
этот метод требует
памяти и
времени.
- ↑ Прасолов В. В. Глава 12. Целозначные многочлены // Многочлены. — М.: МЦНМО, 1999, 2001, 2003.
- ↑ Ю. Матиясевич. Десятая проблема Гильберта. — Наука, 1993.