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

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

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

Явные формулы

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

для

для или

для

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

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

Тождество

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

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

Строки в треугольнике Паскаля в пределе стремятся к функции нормального распределения.

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

В матрице числа на диагонали i + j = const повторяют числа строк треугольника Паскаля (i, j = 0...∞).

Матрицу , где i, j = 0..p можно разложить в произведение двух строго диагональных матриц. Первая нижнетреугольная, а вторая получается из первой путем транcпонирования. Матрицы удовлетворяет соотношению:

где i, j = 0..p.

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

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

, где i, j , m, n = 0..p.

Элементы обратной матрицы меняются при изменение её размера и, в отличие от матрицы , недостаточно приписать новую строку и столбец.

Свойства

Производящие функции

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

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

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

Делимость

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

• нечётен в двоичной записи числа k единицы не стоят в тех разрядах, где в числе n стоят нули.
• некратен простому p в p-ичной записи числа k все разряды не превосходят соответствующих разрядов числа n.
• В последовательности биномиальных коэффициентов :
  • все числа не кратны заданному простому p , где натуральное число m < p;
  • все числа, кроме первого и последнего, кратны заданному простому p ;
  • количество нечётных чисел равно степени двойки (степень двойки равна количеству единиц в двоичной записи числа n);
  • не может быть поровну чётных и нечётных чисел;
  • количество не кратных простому p чисел равно , где числа  — разряды p-ичной записи числа n; а число — её длина.

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

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

Бином Ньютона и следствия

• для .
• Это тождество можно усилить

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

(свёртка Вандермонда).

• для .
• для .
• если — более общий вид тождества выше.

Другие тождества

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

Асимптотика и оценки

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

где  — энтропия.

• (неравенство Чернова).

Алгоритмы вычисления

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

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

См. также

• Биномиальное распределение
• История комбинаторики
• Композиция (теория чисел)
• Пирамида Паскаля
• Разбиение числа
• Треугольник Паскаля
• Треугольное число

Ссылки

• Фукс Д., Фукс М. Арифметика биномиальных коэффициентов // Квант. — 1970. — № 6. — С. 17—25.
• Кузьмин О. В. Треугольник и пирамида Паскаля: свойства и обобщения // Соросовский Образовательный Журнал. — 2000. — Т. 6. — № 5. — С. 101—109.
• Ландо С. К. Теневое исчисление // VIII летняя школа «Современная математика». — Дубна, 2008.
• Винберг Э. Б. Удивительные арифметические свойства биномиальных коэффициентов // Математическое просвещение. — 2008. — В. 12. — С. 33–42.