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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

Тождество

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

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

Строки в треугольнике Паскаля, делённые на (сумма всех чисел в строке), в пределе стремятся к функции нормального распределения.

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

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

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

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

Для фиксированного значения 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 биномиальные коэффициенты могут быть вычислены по рекуррентной формуле с начальным значением . Для вычисления значения этот метод требует памяти и времени.

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

См. также[править | править вики-текст]

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

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

Литература[править | править вики-текст]