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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

,

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

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

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

Явные формулы[править | править код]

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

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

,

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

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

.

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

.

Треугольник Паскаля[править | править код]

Треугольник Паскаля.svg
Visualisation of binomial expansion up to the 4th power
Визуализация биномиального коэффициента до 4 степени

Тождество:

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

.

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

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

Свойства[править | править код]

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

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

.

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

.

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

, или .

Делимость[править | править код]

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

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

Основные тождества[править | править код]

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

Бином Ньютона и следствия[править | править код]

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

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

.

Свёртка Вандермонда и следствия[править | править код]

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

,

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

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

.

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

, если .

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

Другие тождества[править | править код]

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

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

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

,

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

Матричные соотношения[править | править код]

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

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

,

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

.

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

, где , , , .

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

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

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

.

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

,

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

.

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

.

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

.

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

для .

Асимптотика и оценки[править | править код]

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

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

Целозначные полиномы[править | править код]

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

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

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

,

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

Алгоритмы вычисления[править | править код]

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

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

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

Примечания[править | править код]

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

Литература[править | править код]