Биномиа́льный коэффицие́нт — коэффициент перед членом разложения бинома Ньютона по степеням . Коэффициент при обозначается или и читается «биномиальный коэффициент из по » (или «число сочетаний из по »):
для натуральных степеней .
Биномиальные коэффициенты могут быть также определены для произвольных действительных показателей . В случае произвольного действительного числа биномиальные коэффициенты определяются как коэффициенты разложения выражения в бесконечный степенной ряд: , где в случае неотрицательных целых все коэффициенты при обращаются в нуль и поэтому данное разложение является конечной суммой.
В комбинаторике биномиальный коэффициент для неотрицательных целых чисел и интерпретируется как количество сочетаний из по , то есть как количество всех (нестрогих) подмножеств (выборок) размера в -элементном множестве.
Биномиальные коэффициенты часто возникают в задачах комбинаторики и теории вероятностей. Обобщением биномиальных коэффициентов являются мультиномиальные коэффициенты.
Явные формулы Вычисляя коэффициенты в разложении в степенной ряд, можно получить явные формулы для биномиальных коэффициентов .
Для всех действительных чисел и целых чисел : , где обозначает факториал числа .
Для неотрицательных целых и также справедливы формулы: .
Для целых отрицательных показателей коэффициенты разложения бинома равны: .
Треугольник Паскаля
Тождество:
позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел , в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих: . Треугольная таблица, предложенная Паскалем в «Трактате об арифметическом треугольнике» (1654), отличается от той, что выписана здесь, поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (Тарталье, Омару Хайяму, аль-Караджи, Яну Хуэю).
Если в каждой строке треугольника Паскаля все числа разделить на (это сумма всех чисел в строке), то все строки при стремлении к бесконечности примут вид функции нормального распределения.
Свойства
Производящие функции Для фиксированного значения производящей функцией последовательности биномиальных коэффициентов является: .
Для фиксированного значения производящая функция последовательности коэффициентов равна: .
Двумерной производящей функцией биномиальных коэффициентов для целых является: , или .
Делимость Из теоремы Люка следует, что: коэффициент нечётен в двоичной записи числа единицы не стоят в тех разрядах, где в числе стоят нули; коэффициент некратен простому числу в -ичной записи числа все разряды не превосходят соответствующих разрядов числа ; в последовательности биномиальных коэффициентов : все числа не кратны заданному простому число представимо в виде , где натуральное число ; все числа, кроме первого и последнего, кратны заданному простому ; количество нечётных чисел равно степени двойки, показатель которой равен количеству единиц в двоичной записи числа ; чётных и нечётных чисел не может быть поровну; количество чисел, не кратных простому , равно , где числа — разряды -ичной записи числа ; а число , где — функция «пол», — это длина данной записи.
Основные тождества
. . (правило симметрии). (вынесение за скобки). (замена индексов). .
Бином Ньютона и следствия , где .
. , где . Более сильное тождество: , где . ,
а более общем виде
.
Свёртка Вандермонда и следствия
Свёртка Вандермонда: , где а . Это тождество получается вычислением коэффициента при в разложении с учётом тождества . Сумма берётся по всем целым , для которых . Для произвольных действительных , число ненулевых слагаемых в сумме будет конечно.
Следствие свёртки Вандермонда: . Более общее тождество: , если . Ещё одним следствием свёртки является следующее тождество: .
Другие тождества , где — натуральное число. — -е гармоническое число. Мультисекция ряда даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом и смещением в виде конечной суммы из слагаемых: . Также имеют место равенства:
Откуда следует:
, где — количество размещений из по .
Матричные соотношения Если взять квадратную матрицу, отсчитав элементов по катетам треугольника Паскаля и повернув матрицу на любой из четырёх углов, то детерминант этих четырёх матриц равен ±1 при любом , причём детерминант матрицы с вершиной треугольника в верхнем левом углу равен 1.
В матрице числа на диагонали повторяют числа строк треугольника Паскаля (). Её можно разложить в произведение двух строго диагональных матриц: нижнетреугольной и получаемой из неё транспонированием: , где . Обратная матрица к имеет вид: . Таким образом, можно разложить обратную матрицу к в произведение двух строго диагональных матриц: первая матрица — верхнетреугольная, а вторая получается из первой путём транспонирования, что позволяет дать явное выражение для обратных элементов: , где , , , . Элементы обратной матрицы меняются при изменении её размера и, в отличие от матрицы , недостаточно приписать новую строку и столбец. Столбец матрицы есть многочлен степени по аргументу , следовательно, первые p столбцов образуют полный базис в пространстве векторов длины +1, чьи координаты могут быть интерполированы многочленом равной или меньшей степени . Нижняя строка матрицы ортогональна любому такому вектору.
при , где многочлен степени .
Если произвольный вектор длины можно интерполировать многочленом степени , то скалярное произведение со строками (нумерация с 0) матрицы равно нулю. Используя тождество выше и равенство единицы скалярного произведения нижней строки матрицы на последний столбец матрицы , получаем:
.
Для показателя большего можно задать рекуррентную формулу: , где многочлен .
Для доказательства сперва устанавливается тождество: .
Если требуется найти формулу не для всех показателей степени, то: .
Старший коэффициент равен 1, потребуется a-1 значений, чтобы найти другие коэффициенты: для .
Асимптотика и оценки . при (неравенство Чебышёва). , при (энтропийная оценка), где — энтропия. (неравенство Чернова). Непосредственно из формулы Стирлинга следует, что для верно .
Целозначные полиномы
Биномиальные коэффициенты , … являются целозначными полиномами от , то есть принимают целые значения при целых значениях , — это нетрудно понять, например, по треугольнику Паскаля. Более того, они образуют базис целозначных полиномов, в котором все целозначные полиномы выражаются как линейные комбинации с целыми коэффициентами.
В то же время стандартный базис , … не позволяет выразить все целочисленные полиномы, если использовать только целые коэффициенты, так как уже имеет дробные коэффициенты при степенях .
Этот результат обобщается на полиномы многих переменных. А именно, если полином степени имеет вещественные коэффициенты и принимает целые значения при целых значениях переменных, то , где — полином с целыми коэффициентами.
Алгоритмы вычисления Биномиальные коэффициенты можно вычислить с помощью рекуррентной формулы , если на каждом шаге хранить значения при . Этот алгоритм особенно эффективен, если нужно получить все значения вплоть до заданного . Алгоритм требует памяти ( при вычислении всей таблицы биномиальных коэффициентов) и времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени), где — «» большое.
При фиксированном значении биномиальные коэффициенты могут быть вычислены по рекуррентной формуле с начальным значением . Для вычисления значения этот метод требует памяти и времени.
Если требуется вычислить коэффициенты при фиксированном значении , можно воспользоваться формулой при начальном условии . При каждом шаге итерации числитель уменьшается на (начальное значение равно ), а знаменатель соответственно увеличивается на (начальное значение — ). Для вычисления значения этот метод требует памяти и времени.
Примечания
Литература
Категория:Комбинаторика Категория:Факториалы и биномиальные коэффициенты