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

Количество подмножеств заданного размера

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

Визуализация биномиального разложения до 4-й степени

В математике биномиальные коэффициенты — это положительные целые числа , которые встречаются как коэффициенты в биномиальной теореме . Обычно биномиальный коэффициент индексируется парой целых чисел n ≥ k ≥ 0 и записывается. Это коэффициент члена x ^k в полиномиальном разложении биномиальной степени (1 + x ) ⁿ ; этот коэффициент можно вычислить по мультипликативной формуле ${\displaystyle {\tbinom {n}{k}}.}$

${\displaystyle {\binom {n}{k}}={\frac {n\times (n-1)\times \cdots \times (n-k+1)}{k\times (k-1)\times \cdots \times 1}},}$

которое, используя обозначение факториала , можно компактно выразить как

${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$

Например, четвертая степень числа 1 + x равна

${\displaystyle {\begin{aligned}(1+x)^{4}&={\tbinom {4}{0}}x^{0}+{\tbinom {4}{1}}x^{1}+{\tbinom {4}{2}}x^{2}+{\tbinom {4}{3}}x^{3}+{\tbinom {4}{4}}x^{4}\\&=1+4x+6x^{2}+4x^{3}+x^{4},\end{aligned}}}$

а биномиальный коэффициент представляет собой коэффициент при ^члене x2 . ${\displaystyle {\tbinom {4}{2}}={\tfrac {4\times 3}{2\times 1}}={\tfrac {4!}{2!2!}}=6}$

Расположение чисел в последовательных строках для n = 0, 1, 2,... дает треугольный массив, называемый треугольником Паскаля , удовлетворяющий рекуррентному соотношению ${\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},\ldots ,{\tbinom {n}{n}}}$

${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}.}$

Биномиальные коэффициенты встречаются во многих областях математики, особенно в комбинаторике . Символ обычно читается как « n выбирает k », потому что существуют способы выбрать (неупорядоченное) подмножество из k элементов из фиксированного набора из n элементов. Например, есть способы выбрать 2 элемента из {1, 2, 3, 4} , а именно {1, 2} , {1, 3} , {1, 4} , {2, 3} , {2, 4. } и {3, 4} . ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {4}{2}}=6}$

Биномиальные коэффициенты можно обобщить для любого комплексного числа z и целого числа k ≥ 0 , и многие из их свойств продолжают сохраняться в этой более общей форме. ${\displaystyle {\tbinom {z}{k}}}$

История и обозначения

Андреас фон Эттингсхаузен ввел обозначения в 1826 году, ^[1] хотя числа были известны столетиями раньше (см. треугольник Паскаля ). Примерно в 1150 году индийский математик Бхаскарачарья дал изложение биномиальных коэффициентов в своей книге «Лилавати» . ^[2] ${\displaystyle {\tbinom {n}{k}}}$

Альтернативные обозначения включают C ( n , k ) , _n Ck _, ⁿ Ck _, C^к
_н, ^[3] С^н
_ки C _{n , k} , во всех из которых C обозначает комбинации или выборы . Многие калькуляторы используют варианты обозначения C , поскольку они могут представлять его на однострочном дисплее. В этой форме биномиальные коэффициенты легко сравниваются с k -перестановками n , записанными как P ( n , k ) и т. д.

Определение и интерпретации

Для натуральных чисел (включающих 0) n и k биномиальный коэффициент можно определить как коэффициент монома X ^k в разложении ( 1 + X ) ⁿ . Тот же коэффициент встречается (если k ≤ n ) в биномиальной формуле ${\displaystyle {\tbinom {n}{k}}}$

(справедливо для любых элементов x , y коммутативного кольца ), что объясняет название «биномиальный коэффициент».

Другое появление этого числа - в комбинаторике, где оно дает количество способов, независимо от порядка, которыми k объектов можно выбрать из n объектов; более формально, количество подмножеств k -элементов (или k - комбинаций ) набора из n -элементов. Это число можно рассматривать как равное числу из первого определения, независимо от какой-либо из приведенных ниже формул для его вычисления: если в каждом из n делителей степени ( 1 + X ) ⁿ временно пометить термин X с помощью индекс i (от 1 до n ), то каждое подмножество индексов k дает после расширения вклад X ^k , а коэффициент этого монома в результате будет числом таких подмножеств. Это показывает, в частности, что это натуральное число для любых натуральных чисел n и k . Существует много других комбинаторных интерпретаций биномиальных коэффициентов (задачи подсчета, для которых ответ дается выражением биномиального коэффициента), например, количество слов, состоящих из n битов (цифр 0 или 1), сумма которых равна k , определяется выражением , а количество способов записи , где каждое a _i является неотрицательным целым числом, определяется выражением . Можно показать, что большинство этих интерпретаций эквивалентны подсчету k -комбинаций. ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle k=a_{1}+a_{2}+\cdots +a_{n}}$ ${\displaystyle {\tbinom {n+k-1}{n-1}}}$

Вычисление значения биномиальных коэффициентов

Существует несколько методов вычисления значения без фактического разложения биномиальной степени или подсчета k -комбинаций. ${\displaystyle {\tbinom {n}{k}}}$

Рекурсивная формула

Один метод использует рекурсивную , чисто аддитивную формулу

$${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}}$$

${\displaystyle n,k}$ ${\displaystyle 1\leq k<n,}$

$${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1}$$

n ≥ 0

Формула следует из рассмотрения набора {1, 2, 3, ..., n } и отдельного подсчета (a) группировок k -элементов, которые включают конкретный элемент множества, скажем " i ", в каждой группе (поскольку " i " " уже выбран для заполнения одного места в каждой группе, нам нужно только выбрать k - 1 из оставшихся n - 1 ) и (b) все k -группы, которые не включают " i "; это перечисляет все возможные k -комбинации из n элементов. Это также следует из отслеживания вкладов в X ^k в (1 + X ) ^{n −1} (1 + X ) . Поскольку в (1 + X ) ⁿ имеется ноль X ^{n +1} или X ⁻¹ , можно расширить определение за пределы вышеуказанных границ, включив в него случаи, когда либо k > n , либо k < 0 . Эта рекурсивная формула затем позволяет построить треугольник Паскаля , окруженный пробелами там, где должны быть нули или тривиальные коэффициенты. ${\displaystyle {\tbinom {n}{k}}=0}$

Мультипликативная формула

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

$${\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n(n-1)(n-2)\cdots (n-(k-1))}{k(k-1)(k-2)\cdots 1}}=\prod _{i=1}^{k}{\frac {n+1-i}{i}},}$$

падающая факториальная степеньknk ${\displaystyle n^{\underline {k}}}$

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

Факториальная формула

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

$${\displaystyle {\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{for }}\ 0\leq k\leq n,}$$

н ! n( n − k )! kn

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

$${\displaystyle {\binom {n}{k}}={\begin{cases}n^{\underline {k}}/k!&{\text{if }}\ k\leq {\frac {n}{2}}\\n^{\underline {n-k}}/(n-k)!&{\text{if }}\ k>{\frac {n}{2}}\end{cases}}.}$$

Обобщение и привязка к биномиальному ряду

Мультипликативная формула позволяет расширить определение биномиальных коэффициентов ^[4] за счет замены n произвольным числом α (отрицательным, вещественным, комплексным) или даже элементом любого коммутативного кольца , в котором все положительные целые числа обратимы:

$${\displaystyle {\binom {\alpha }{k}}={\frac {\alpha ^{\underline {k}}}{k!}}={\frac {\alpha (\alpha -1)(\alpha -2)\cdots (\alpha -k+1)}{k(k-1)(k-2)\cdots 1}}\quad {\text{for }}k\in \mathbb {N} {\text{ and arbitrary }}\alpha .}$$

Благодаря этому определению получается обобщение биномиальной формулы (с одной из переменных, равной 1), что оправдывает дальнейшее использование биномиальных коэффициентов: ${\displaystyle {\tbinom {\alpha }{k}}}$

Эта формула справедлива для всех комплексных чисел α и X с | Х | < 1. Его также можно интерпретировать как тождество формального степенного ряда в X , где оно фактически может служить определением произвольных степеней степенного ряда с постоянным коэффициентом, равным 1; Дело в том, что с этим определением сохраняются все тождества, которые можно ожидать от возведения в степень , в частности

$${\displaystyle (1+X)^{\alpha }(1+X)^{\beta }=(1+X)^{\alpha +\beta }\quad {\text{and}}\quad ((1+X)^{\alpha })^{\beta }=(1+X)^{\alpha \beta }.}$$

Если α — неотрицательное целое число n , то все члены с k > n равны нулю, и бесконечный ряд становится конечной суммой, тем самым восстанавливая биномиальную формулу. Однако для других значений α , включая отрицательные целые и рациональные числа, ряд действительно бесконечен.

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

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

Правило Паскаля — важное рекуррентное соотношение

которое можно использовать для доказательства с помощью математической индукции , что это натуральное число для всех целых чисел n ≥ 0 и всех целых k , факт, который не сразу очевиден из формулы (1). Слева и справа от треугольника Паскаля все записи (показаны пробелами) равны нулю. ${\displaystyle {\tbinom {n}{k}}}$

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

Строка номер n содержит числа для k = 0,…, n . Он создается путем размещения единиц на крайних позициях, а затем заполнения каждой внутренней позиции суммой двух чисел, расположенных непосредственно выше. Этот метод позволяет быстро рассчитать биномиальные коэффициенты без необходимости дробей или умножений. Например, взглянув на строку номер 5 треугольника, можно быстро прочитать, что ${\displaystyle {\tbinom {n}{k}}}$

${\displaystyle (x+y)^{5}={\underline {1}}x^{5}+{\underline {5}}x^{4}y+{\underline {10}}x^{3}y^{2}+{\underline {10}}x^{2}y^{3}+{\underline {5}}xy^{4}+{\underline {1}}y^{5}.}$

Комбинаторика и статистика

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

• Есть способы выбрать k элементов из набора из n элементов. См. Комбинация . ${\displaystyle {\tbinom {n}{k}}}$
• Существуют способы выбрать k элементов из набора из n элементов, если повторы разрешены. См. Мультисет . ${\displaystyle {\tbinom {n+k-1}{k}}}$
• Существуют строки , содержащие k единиц и n нулей. ${\displaystyle {\tbinom {n+k}{k}}}$
• Существуют строки, состоящие из k единиц и n нулей, такие, что никакие две единицы не являются соседними. ^[5] ${\displaystyle {\tbinom {n+1}{k}}}$
• Каталонские цифры _ ${\displaystyle {\tfrac {1}{n+1}}{\tbinom {2n}{n}}.}$
• Биномиальное распределение в статистике _ ${\displaystyle {\tbinom {n}{k}}p^{k}(1-p)^{n-k}.}$

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

Для любого неотрицательного целого числа k выражение можно упростить и определить как многочлен, разделенный на k ! : ${\textstyle {\binom {t}{k}}}$

${\displaystyle {\binom {t}{k}}={\frac {t^{\underline {k}}}{k!}}={\frac {t(t-1)(t-2)\cdots (t-k+1)}{k(k-1)(k-2)\cdots 2\cdot 1}};}$

это представляет собой полином от t с рациональными коэффициентами.

Таким образом, его можно оценить по любому действительному или комплексному числу t , чтобы определить биномиальные коэффициенты с такими первыми аргументами. Эти «обобщенные биномиальные коэффициенты» появляются в обобщенной биномиальной теореме Ньютона .

Для каждого k полином можно охарактеризовать как уникальный полином p ( t ) степени k , удовлетворяющий p (0) = p (1) = ⋯ = p ( k - 1) = 0 и p ( k ) = 1 . ${\displaystyle {\tbinom {t}{k}}}$

Его коэффициенты выражаются через числа Стирлинга первого рода :

${\displaystyle {\binom {t}{k}}=\sum _{i=0}^{k}s(k,i){\frac {t^{i}}{k!}}.}$

Производную можно вычислить логарифмическим дифференцированием : ${\displaystyle {\tbinom {t}{k}}}$

${\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}={\binom {t}{k}}\sum _{i=0}^{k-1}{\frac {1}{t-i}}.}$

Это может вызвать проблемы при вычислении целых чисел от до , но, используя приведенные ниже тождества, мы можем вычислить производную как: ${\displaystyle 0}$ ${\displaystyle t-1}$

${\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}=\sum _{i=0}^{k-1}{\frac {(-1)^{k-i-1}}{k-i}}{\binom {t}{i}}.}$

Биномиальные коэффициенты как основа пространства многочленов

Над любым полем характеристики (то есть любым полем, содержащим рациональные числа ), каждый многочлен p ( t ) степени не выше d однозначно выражается как линейная комбинация биномиальных коэффициентов. Коэффициент a _k — это k- я разность последовательности p (0), p (1), ..., p ( k ). Явно, ^[6] ${\textstyle \sum _{k=0}^{d}a_{k}{\binom {t}{k}}}$

Целочисленные полиномы

Каждый полином является целочисленным : он имеет целочисленное значение на всех целочисленных входах . (Один из способов доказать это — провести индукцию по k с использованием тождества Паскаля .) Следовательно, любая целочисленная линейная комбинация полиномов с биномиальными коэффициентами также является целочисленной. И наоборот, ( 4 ) показывает, что любой целочисленный полином является целочисленной линейной комбинацией этих биномиальных полиномов с коэффициентами. В более общем смысле, для любого подкольца R поля характеристики 0 K многочлен из K [ t ] принимает значения в R во всех целых числах тогда и только тогда, когда он является R -линейной комбинацией биномиальных полиномов коэффициентов. ${\displaystyle {\tbinom {t}{k}}}$ ${\displaystyle t}$

Пример

Целочисленный многочлен 3 t (3 t + 1)/2 можно переписать в виде

${\displaystyle 9{\binom {t}{2}}+6{\binom {t}{1}}+0{\binom {t}{0}}.}$

Тождества с биномиальными коэффициентами

Формула факториала облегчает связь близлежащих биномиальных коэффициентов. Например, если k — целое положительное число, а n — произвольное, то

и, еще немного поработав,

${\displaystyle {\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.}$

Мы также можем получить

${\displaystyle {\binom {n-1}{k}}={\frac {n-k}{n}}{\binom {n}{k}}.}$

Кроме того, могут оказаться полезными:

${\displaystyle {\binom {n}{h}}{\binom {n-h}{k}}={\binom {n}{k}}{\binom {n-k}{h}}={\binom {n}{h+k}}{\binom {h+k}{h}}.}$

Для постоянного n мы имеем следующую повторяемость:

${\displaystyle {\binom {n}{k}}={\frac {n-k+1}{k}}{\binom {n}{k-1}}.}$

Подводя итог, мы имеем

${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}={\frac {n-k+1}{k}}{\binom {n}{k-1}}={\frac {n}{n-k}}{\binom {n-1}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}={\frac {n}{n-2k}}{\Bigg (}{\binom {n-1}{k}}-{\binom {n-1}{k-1}}{\Bigg )}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}.}$

Суммы биномиальных коэффициентов

Формула

говорит, что сумма элементов в n -й строке треугольника Паскаля всегда равна 2, возведенным в n- ю степень. Это получается из биномиальной теоремы ( ∗ ), если установить x = 1 и y = 1 . Формула также имеет естественную комбинаторную интерпретацию: левая часть суммирует количество подмножеств {1, ..., n } размеров k = 0, 1, ..., n , давая общее количество подмножеств. (То есть левая часть подсчитывает набор степеней {1, ..., n }.) Однако эти подмножества также могут быть сгенерированы путем последовательного выбора или исключения каждого элемента 1, ..., n ; n независимых двоичных вариантов выбора (битовых строк) допускают общее количество вариантов выбора. Левая и правая части — это два способа подсчета одной и той же коллекции подмножеств, поэтому они равны. ${\displaystyle 2^{n}}$

Формулы

и

${\displaystyle \sum _{k=0}^{n}k^{2}{\binom {n}{k}}=(n+n^{2})2^{n-2}}$

следуют из биномиальной теоремы после дифференцирования по x (дважды для последнего) и последующей подстановки x = y = 1 .

Тождество Чу-Вандермонда , которое справедливо для любых комплексных значений m и n и любого неотрицательного целого числа k , равно

и может быть найден путем изучения коэффициента в разложении (1 + x ) ^m (1 + x ) ^{n - m} = (1 + x ) ⁿ с использованием уравнения ( 2 ). Когда m = 1 , уравнение ( 7 ) сводится к уравнению ( 3 ). В частном случае n = 2 m , k = m , используя ( 1 ), разложение ( 7 ) становится (как видно из треугольника Паскаля справа) ${\displaystyle x^{k}}$

${\displaystyle {\begin{array}{c}1\\1\qquad 1\\1\qquad 2\qquad 1\\{\color {blue}1\qquad 3\qquad 3\qquad 1}\\1\qquad 4\qquad 6\qquad 4\qquad 1\\1\qquad 5\qquad 10\qquad 10\qquad 5\qquad 1\\1\qquad 6\qquad 15\qquad {\color {red}20}\qquad 15\qquad 6\qquad 1\\1\qquad 7\qquad 21\qquad 35\qquad 35\qquad 21\qquad 7\qquad 1\end{array}}}$

Треугольник Паскаля, строки с 0 по 7. Уравнение 8 для m = 3 показано в строках 3 и 6 как ${\displaystyle 1^{2}+3^{2}+3^{2}+1^{2}=20.}$

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

Другая форма идентичности Чу-Вандермонда, которая применяется для любых целых чисел j , k и n, удовлетворяющих условиям 0 ≤ j ≤ k ≤ n , — это

Доказательство аналогично, но использует разложение в биномиальный ряд ( 2 ) с отрицательными целыми показателями. Когда j = k , уравнение ( 9 ) дает тождество хоккейной клюшки

${\displaystyle \sum _{m=k}^{n}{\binom {m}{k}}={\binom {n+1}{k+1}}}$

и его родственник

${\displaystyle \sum _{r=0}^{m}{\binom {n+r}{r}}={\binom {n+m+1}{m}}.}$

Пусть F ( n ) обозначает n -е число Фибоначчи . Затем

${\displaystyle \sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n-k}{k}}=F(n+1).}$

Это можно доказать индукцией с использованием ( 3 ) или представлением Цекендорфа . Комбинаторное доказательство приведено ниже.

Мультисекции сумм

Для целых чисел s и t , таких, что многосечение ряда дает следующее тождество для суммы биномиальных коэффициентов: ${\displaystyle 0\leq t<s,}$

${\displaystyle {\binom {n}{t}}+{\binom {n}{t+s}}+{\binom {n}{t+2s}}+\ldots ={\frac {1}{s}}\sum _{j=0}^{s-1}\left(2\cos {\frac {\pi j}{s}}\right)^{n}\cos {\frac {\pi (n-2t)j}{s}}.}$

Для маленьких s эти серии имеют особенно красивые формы; например, ^[7]

${\displaystyle {\binom {n}{0}}+{\binom {n}{3}}+{\binom {n}{6}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {n\pi }{3}}\right)}$

${\displaystyle {\binom {n}{1}}+{\binom {n}{4}}+{\binom {n}{7}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-2)\pi }{3}}\right)}$

${\displaystyle {\binom {n}{2}}+{\binom {n}{5}}+{\binom {n}{8}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-4)\pi }{3}}\right)}$

${\displaystyle {\binom {n}{0}}+{\binom {n}{4}}+{\binom {n}{8}}+\cdots ={\frac {1}{2}}\left(2^{n-1}+2^{\frac {n}{2}}\cos {\frac {n\pi }{4}}\right)}$

${\displaystyle {\binom {n}{1}}+{\binom {n}{5}}+{\binom {n}{9}}+\cdots ={\frac {1}{2}}\left(2^{n-1}+2^{\frac {n}{2}}\sin {\frac {n\pi }{4}}\right)}$

${\displaystyle {\binom {n}{2}}+{\binom {n}{6}}+{\binom {n}{10}}+\cdots ={\frac {1}{2}}\left(2^{n-1}-2^{\frac {n}{2}}\cos {\frac {n\pi }{4}}\right)}$

${\displaystyle {\binom {n}{3}}+{\binom {n}{7}}+{\binom {n}{11}}+\cdots ={\frac {1}{2}}\left(2^{n-1}-2^{\frac {n}{2}}\sin {\frac {n\pi }{4}}\right)}$

Частичные суммы

Хотя закрытой формулы для частичных сумм не существует.

${\displaystyle \sum _{j=0}^{k}{\binom {n}{j}}}$

биномиальных коэффициентов, ^[8] можно снова использовать ( 3 ) и индукцию, чтобы показать, что для k = 0, …, n − 1 ,

${\displaystyle \sum _{j=0}^{k}(-1)^{j}{\binom {n}{j}}=(-1)^{k}{\binom {n-1}{k}},}$

в особом случае ^[9]

${\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}=0}$

для п > 0 . Этот последний результат также является частным случаем результата теории конечных разностей , согласно которому для любого многочлена P ( x ) степени меньше n , ^[10]

${\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(j)=0.}$

Дифференцирование ( 2 ) k раз и установка x = −1 дает это для , когда 0 ≤ k < n , и общий случай следует из принятия линейных комбинаций этих значений. ${\displaystyle P(x)=x(x-1)\cdots (x-k+1)}$

Когда P ( x ) имеет степень меньше или равна n ,

где – коэффициент степени n в P ( x ). ${\displaystyle a_{n}}$

В более общем смысле для ( 10 )

${\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(m+(n-j)d)=d^{n}n!a_{n}}$

где m и d — комплексные числа. Это следует из немедленного применения ( 10 ) к многочлену вместо и наблюдения, что он все еще имеет степень, меньшую или равную n , и что его коэффициент степени n равен d ⁿ a _n . ${\displaystyle Q(x):=P(m+dx)}$ ${\displaystyle P(x)}$ ${\displaystyle Q(x)}$

Ряд сходится при k ≥ 2. Эта формула используется при анализе немецкой танковой задачи . Отсюда следует , что доказывается индукцией по M . ${\textstyle {\frac {k-1}{k}}\sum _{j=0}^{\infty }{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}}$ ${\textstyle {\frac {k-1}{k}}\sum _{j=0}^{M}{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}-{\frac {1}{\binom {M+x}{k-1}}}}$

Тождества с комбинаторными доказательствами

Многие тождества, включающие биномиальные коэффициенты, можно доказать комбинаторными методами . Например, для неотрицательных целых чисел тождество ${\displaystyle {n}\geq {q}}$

${\displaystyle \sum _{k=q}^{n}{\binom {n}{k}}{\binom {k}{q}}=2^{n-q}{\binom {n}{q}}}$

(которое сводится к ( 6 ), когда q = 1) может быть дано доказательство с двойным подсчетом следующим образом. В левой части подсчитывается количество способов выбора подмножества [ n ] = {1, 2, ..., n } по крайней мере с q элементами и маркировки q элементов среди выбранных. Правая часть учитывает то же самое, потому что есть способы выбрать набор из q элементов для маркировки и выбрать, какой из оставшихся элементов [ n ] также принадлежит подмножеству. ${\displaystyle {\tbinom {n}{q}}}$ ${\displaystyle 2^{n-q}}$

В личности Паскаля

${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k},}$

обе стороны подсчитывают количество подмножеств k -элементов [ n ]: два термина в правой части группируют их на те, которые содержат элемент n , и те, которые его не содержат.

Тождество ( 8 ) также имеет комбинаторное доказательство. Идентичность гласит

${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}.}$

Предположим, у вас есть пустые квадраты, расположенные в ряд, и вы хотите отметить (выбрать) n из них. Есть способы сделать это. С другой стороны, вы можете выбрать n квадратов, выбрав k квадратов из первых n и квадратов из оставшихся n квадратов; любой k от 0 до n подойдет. Это дает ${\displaystyle 2n}$ ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle n-k}$

${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}{\binom {n}{n-k}}={\binom {2n}{n}}.}$

Теперь примените ( 1 ), чтобы получить результат.

Если обозначить через F ( i ) последовательность чисел Фибоначчи , пронумерованную так, что F (0) = F (1) = 1 , то тождество

$${\displaystyle \sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\binom {n-k}{k}}=F(n)}$$

^{[11] С помощью} индукцииF ( n )n × 1 может быть покрыта плитками 2 × 11 × 1k2 × 1n - 2 k1 × 1n - kk ${\displaystyle {\tbinom {n-k}{k}}}$

Сумма коэффициентов ряда

Число k - комбинаций для всех k , , представляет собой сумму n -й строки (считая от 0) биномиальных коэффициентов. Эти комбинации нумеруются 1 цифрами набора чисел с основанием 2 , считая от 0 до , где каждая позиция цифры является элементом из набора n . ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ ${\displaystyle 2^{n}-1}$

Личность Диксона

Личность Диксона

${\displaystyle \sum _{k=-a}^{a}(-1)^{k}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}}}$

или, в более общем смысле,

${\displaystyle \sum _{k=-a}^{a}(-1)^{k}{a+b \choose a+k}{b+c \choose b+k}{c+a \choose c+k}={\frac {(a+b+c)!}{a!\,b!\,c!}}\,,}$

где a , b и c — неотрицательные целые числа.

Непрерывные тождества

Некоторые тригонометрические интегралы имеют значения, выражаемые через биномиальные коэффициенты: для любого ${\displaystyle m,n\in \mathbb {N} ,}$

${\displaystyle \int _{-\pi }^{\pi }\cos((2m-n)x)\cos ^{n}(x)\ dx={\frac {\pi }{2^{n-1}}}{\binom {n}{m}}}$

${\displaystyle \int _{-\pi }^{\pi }\sin((2m-n)x)\sin ^{n}(x)\ dx={\begin{cases}(-1)^{m+(n+1)/2}{\frac {\pi }{2^{n-1}}}{\binom {n}{m}},&n{\text{ odd}}\\0,&{\text{otherwise}}\end{cases}}}$

${\displaystyle \int _{-\pi }^{\pi }\cos((2m-n)x)\sin ^{n}(x)\ dx={\begin{cases}(-1)^{m+(n/2)}{\frac {\pi }{2^{n-1}}}{\binom {n}{m}},&n{\text{ even}}\\0,&{\text{otherwise}}\end{cases}}}$

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

Сравнения

Если n простое, то

$${\displaystyle {\binom {n-1}{k}}\equiv (-1)^{k}\mod n}$$

knkkn ${\displaystyle 0\leq k\leq n-1.}$

Действительно, у нас есть

${\displaystyle {\binom {n-1}{k}}={(n-1)(n-2)\cdots (n-k) \over 1\cdot 2\cdots k}=\prod _{i=1}^{k}{n-i \over i}\equiv \prod _{i=1}^{k}{-i \over i}=(-1)^{k}\mod n.}$

Генерирующие функции

Обыкновенные производящие функции

Для фиксированного n обычная производящая функция последовательности равна ${\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},{\tbinom {n}{2}},\ldots }$

${\displaystyle \sum _{k=0}^{\infty }{n \choose k}x^{k}=(1+x)^{n}.}$

Для фиксированного k обычная производящая функция последовательности равна ${\displaystyle {\tbinom {0}{k}},{\tbinom {1}{k}},{\tbinom {2}{k}},\ldots ,}$

${\displaystyle \sum _{n=0}^{\infty }{n \choose k}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}.}$

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

${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{n}{n \choose k}x^{k}y^{n}={\frac {1}{1-y-xy}}.}$

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

${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}x^{k}y^{n}={\frac {1}{1-x-y}}.}$

что совпадает с предыдущей производящей функцией после подстановки . ${\displaystyle x\to xy}$

Экспоненциальная производящая функция

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

${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}{\frac {x^{k}y^{n}}{(n+k)!}}=e^{x+y}.}$

Свойства делимости

В 1852 году Куммер доказал, что если ^m и n — неотрицательные целые числа, а p — простое число, то наибольшая степень деления p равна pc , где c — количество переносов, когда m и n складываются по основанию p . Эквивалентно, показатель степени простого числа p in равен количеству неотрицательных целых чисел j таких, что дробная часть k / p j ^больше дробной части n / p ^j . Отсюда можно вывести, что делится на n / gcd ( n , k ). В частности, отсюда следует, что p делит все положительные целые числа r и s такие, что s < p ^r . Однако это не относится к высшим степеням p : например, 9 не делится . ${\displaystyle {\tbinom {m+n}{m}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {p^{r}}{s}}}$ ${\displaystyle {\tbinom {9}{6}}}$

Несколько неожиданный результат Дэвида Сингмастера (1974) заключается в том, что любое целое число делит почти все биномиальные коэффициенты. Точнее, зафиксируйте целое число d и пусть f ( N ) обозначает количество биномиальных коэффициентов с n < N таких, что d делит . Затем ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$

${\displaystyle \lim _{N\to \infty }{\frac {f(N)}{N(N+1)/2}}=1.}$

Поскольку количество биномиальных коэффициентов при n < N равно N ( N + 1)/2, это означает, что плотность биномиальных коэффициентов, делящихся на d, стремится к 1. ${\displaystyle {\tbinom {n}{k}}}$

Биномиальные коэффициенты обладают свойствами делимости, связанными с наименьшими общими кратными последовательных целых чисел. Например: ^[12]

${\displaystyle {\binom {n+k}{k}}}$делит . ${\displaystyle {\frac {\operatorname {lcm} (n,n+1,\ldots ,n+k)}{n}}}$

${\displaystyle {\binom {n+k}{k}}}$кратно . ${\displaystyle {\frac {\operatorname {lcm} (n,n+1,\ldots ,n+k)}{n\cdot \operatorname {lcm} ({\binom {k}{0}},{\binom {k}{1}},\ldots ,{\binom {k}{k}})}}}$

Еще один факт: целое число n ≥ 2 является простым тогда и только тогда, когда все промежуточные биномиальные коэффициенты

${\displaystyle {\binom {n}{1}},{\binom {n}{2}},\ldots ,{\binom {n}{n-1}}}$

делятся на n .

Доказательство: когда p простое, p делит

${\displaystyle {\binom {p}{k}}={\frac {p\cdot (p-1)\cdots (p-k+1)}{k\cdot (k-1)\cdots 1}}}$для всех 0 < k < p

потому что это натуральное число и p делит числитель, но не знаменатель. Если n составное, пусть p будет наименьшим простым делителем числа n и пусть k = n / p . Тогда 0 < p < n и ${\displaystyle {\tbinom {p}{k}}}$

${\displaystyle {\binom {n}{p}}={\frac {n(n-1)(n-2)\cdots (n-p+1)}{p!}}={\frac {k(n-1)(n-2)\cdots (n-p+1)}{(p-1)!}}\not \equiv 0{\pmod {n}}}$

в противном случае числитель k ( n - 1)( n - 2)⋯( n - p + 1) должен делиться на n = k × p , это может быть только в том случае, когда ( n - 1)( n - 2) ⋯( n − p + 1) делится на p . Но n делится на p , поэтому p не делит n − 1, n − 2, …, n − p + 1 , а поскольку p простое число, мы знаем, что p не делит ( n − 1)( n − 2) ⋯( n − p + 1) , поэтому числитель не может делиться на n .

Границы и асимптотические формулы

Следующие границы справедливы для всех значений n и k , таких что 1 ≤ k ≤ n : ${\displaystyle {\tbinom {n}{k}}}$

$${\displaystyle {\frac {n^{k}}{k^{k}}}\leq {n \choose k}\leq {\frac {n^{k}}{k!}}<\left({\frac {n\cdot e}{k}}\right)^{k}.}$$

$${\displaystyle {n \choose k}={\frac {n}{k}}\cdot {\frac {n-1}{k-1}}\cdots {\frac {n-(k-1)}{1}}}$$

${\displaystyle k}$ ${\textstyle \geq {\frac {n}{k}}}$ ${\textstyle e^{k}>k^{k}/k!}$ ${\textstyle e^{k}=\sum _{j=0}^{\infty }k^{j}/j!}$

Из свойств делимости можно сделать вывод, что

$${\displaystyle {\frac {\operatorname {lcm} (n-k,\ldots ,n)}{(n-k)\cdot \operatorname {lcm} \left({\binom {k}{0}},\ldots ,{\binom {k}{k}}\right)}}\leq {\binom {n}{k}}\leq {\frac {\operatorname {lcm} (n-k,\ldots ,n)}{n-k}},}$$

^[12]

Следующие оценки полезны в теории информации: ^{[13] : 353}

$${\displaystyle {\frac {1}{n+1}}2^{nH(k/n)}\leq {n \choose k}\leq 2^{nH(k/n)}}$$

двоичная функция энтропии ${\displaystyle H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)}$

$${\displaystyle {\sqrt {\frac {n}{8k(n-k)}}}2^{nH(k/n)}\leq {n \choose k}\leq {\sqrt {\frac {n}{2\pi k(n-k)}}}2^{nH(k/n)}}$$

^{[14] : 309} ${\displaystyle 1\leq k\leq n-1}$

И n, и k большие

Приближение Стирлинга дает следующее приближение, справедливое, когда оба стремятся к бесконечности: ${\displaystyle n-k,k}$

$${\displaystyle {n \choose k}\sim {\sqrt {n \over 2\pi k(n-k)}}\cdot {n^{n} \over k^{k}(n-k)^{n-k}}}$$

${\displaystyle n}$

$${\displaystyle {2n \choose n}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}}$$

m ≥ 2n ≥ 1 ^{[ почему? ]} ${\displaystyle {\sqrt {n}}{2n \choose n}\geq 2^{2n-1}}$

$${\displaystyle {\sqrt {n}}{mn \choose n}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}.}$$

Если n велико и k линейно по n , существуют различные точные асимптотические оценки биномиального коэффициента . Например, если тогда ${\textstyle {\binom {n}{k}}}$ ${\displaystyle |n/2-k|=o(n^{2/3})}$

$${\displaystyle {\binom {n}{k}}\sim {\binom {n}{\frac {n}{2}}}e^{-d^{2}/(2n)}\sim {\frac {2^{n}}{\sqrt {{\frac {1}{2}}n\pi }}}e^{-d^{2}/(2n)}}$$

dпk^[15]

n намного больше k

Если n велико и k равно o ( n ) (то есть, если k / n → 0 ), то

$${\displaystyle {\binom {n}{k}}\sim \left({\frac {ne}{k}}\right)^{k}\cdot (2\pi k)^{-1/2}\cdot \exp \left(-{\frac {k^{2}}{2n}}(1+o(1))\right)}$$

oмаленькое обозначение o^[16]

Суммы биномиальных коэффициентов

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

$${\displaystyle \sum _{i=0}^{k}{n \choose i}\leq \sum _{i=0}^{k}n^{i}\cdot 1^{k-i}\leq (1+n)^{k}}$$

$${\displaystyle {\frac {1}{\sqrt {8n\varepsilon (1-\varepsilon )}}}\cdot 2^{H(\varepsilon )\cdot n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\varepsilon )\cdot n},}$$

^[17] ${\displaystyle n>k\geq 1}$ ${\displaystyle \varepsilon \doteq k/n\leq 1/2}$

Обобщенные биномиальные коэффициенты

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

$${\displaystyle (-1)^{k}{z \choose k}={-z+k-1 \choose k}={\frac {1}{\Gamma (-z)}}{\frac {1}{(k+1)^{z+1}}}\prod _{j=k+1}{\frac {\left(1+{\frac {1}{j}}\right)^{-z-1}}{1-{\frac {z+1}{j}}}}}$$

$${\displaystyle {z \choose k}\approx {\frac {(-1)^{k}}{\Gamma (-z)k^{z+1}}}\qquad {\text{and}}\qquad {z+k \choose k}={\frac {k^{z}}{\Gamma (z+1)}}\left(1+{\frac {z(z+1)}{2k}}+{\mathcal {O}}\left(k^{-2}\right)\right)}$$

${\displaystyle k\to \infty }$

Это асимптотическое поведение содержится в приближении

$${\displaystyle {z+k \choose k}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}}$$

kгармоникиконстанта Эйлера–Машерони ${\displaystyle H_{k}}$ ${\displaystyle \gamma }$

Далее, асимптотическая формула

$${\displaystyle {\frac {z+k \choose j}{k \choose j}}\to \left(1-{\frac {j}{k}}\right)^{-z}\quad {\text{and}}\quad {\frac {j \choose j-k}{j-z \choose j-k}}\to \left({\frac {j}{k}}\right)^{z}}$$

${\displaystyle k\to \infty }$ ${\displaystyle j/k\to x}$ ${\displaystyle x}$

Обобщения

Обобщение на многочлены

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

${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{r}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{r}!}}}$

где

${\displaystyle \sum _{i=1}^{r}k_{i}=n.}$

В то время как биномиальные коэффициенты представляют собой коэффициенты ( x + y ) ⁿ , полиномиальные коэффициенты представляют собой коэффициенты полинома

${\displaystyle (x_{1}+x_{2}+\cdots +x_{r})^{n}.}$

Случай r = 2 дает биномиальные коэффициенты:

${\displaystyle {n \choose k_{1},k_{2}}={n \choose k_{1},n-k_{1}}={n \choose k_{1}}={n \choose k_{2}}.}$

Комбинаторная интерпретация полиномиальных коэффициентов представляет собой распределение n различимых элементов по r (различимым) контейнерам, каждый из которых содержит ровно k _i элементов, где i — номер контейнера.

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

${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{r}}={n-1 \choose k_{1}-1,k_{2},\ldots ,k_{r}}+{n-1 \choose k_{1},k_{2}-1,\ldots ,k_{r}}+\ldots +{n-1 \choose k_{1},k_{2},\ldots ,k_{r}-1}}$

и симметрия:

${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{r}}={n \choose k_{\sigma _{1}},k_{\sigma _{2}},\ldots ,k_{\sigma _{r}}}}$

где — перестановка (1, 2,..., r ). ${\displaystyle (\sigma _{i})}$

Серия Тейлора

Используя числа Стирлинга первого рода, разложение в ряд вокруг любой произвольно выбранной точки имеет вид ${\displaystyle z_{0}}$

${\displaystyle {\begin{aligned}{z \choose k}={\frac {1}{k!}}\sum _{i=0}^{k}z^{i}s_{k,i}&=\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{j=i}^{k}{z_{0} \choose j-i}{\frac {s_{k+i-j,i}}{(k+i-j)!}}\\&=\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{j=i}^{k}z_{0}^{j-i}{j \choose i}{\frac {s_{k,j}}{k!}}.\end{aligned}}}$

Биномиальный коэффициент при n = 1/2

Определение биномиальных коэффициентов можно распространить на случай, когда вещественное и целое число. ${\displaystyle n}$ ${\displaystyle k}$

В частности, для любого неотрицательного целого числа справедливо следующее тождество : ${\displaystyle k}$

${\displaystyle {{1/2} \choose {k}}={{2k} \choose {k}}{\frac {(-1)^{k+1}}{2^{2k}(2k-1)}}.}$

Это проявляется при разложении в степенной ряд с использованием биномиального ряда Ньютона: ${\displaystyle {\sqrt {1+x}}}$

${\displaystyle {\sqrt {1+x}}=\sum _{k\geq 0}{\binom {1/2}{k}}x^{k}.}$

Произведения биномиальных коэффициентов

Произведение двух биномиальных коэффициентов можно выразить как линейную комбинацию биномиальных коэффициентов:

${\displaystyle {z \choose m}{z \choose n}=\sum _{k=0}^{\min(m,n)}{m+n-k \choose k,m-k,n-k}{z \choose m+n-k},}$

где коэффициенты связи являются полиномиальными коэффициентами . Что касается помеченных комбинаторных объектов, коэффициенты связи представляют собой количество способов назначить m + n - k меток паре помеченных комбинаторных объектов - веса m и n соответственно - у которых были идентифицированы или склеены первые k меток. чтобы получить новый помеченный комбинаторный объект веса m + n − k . (То есть разделить метки на три части и применить к склеенной части, отклеенной части первого объекта и отклеенной части второго объекта.) В этом отношении биномиальные коэффициенты являются для экспоненциального порождающего ряда тем же, чем падающие факториалы. относятся к обычным порождающим рядам.

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

${\displaystyle \prod _{k=0}^{n}{\binom {n}{k}}=\prod _{k=1}^{n}k^{2k-n-1}.}$

Частичное дробное разложение

Разложение обратной величины на частные дроби определяется выражением

${\displaystyle {\frac {1}{z \choose n}}=\sum _{i=0}^{n-1}(-1)^{n-1-i}{n \choose i}{\frac {n-i}{z-i}},\qquad {\frac {1}{z+n \choose n}}=\sum _{i=1}^{n}(-1)^{i-1}{n \choose i}{\frac {i}{z+i}}.}$

Биномиальный ряд Ньютона

Биномиальный ряд Ньютона, названный в честь сэра Исаака Ньютона , представляет собой обобщение биномиальной теоремы на бесконечные ряды:

${\displaystyle (1+z)^{\alpha }=\sum _{n=0}^{\infty }{\alpha \choose n}z^{n}=1+{\alpha \choose 1}z+{\alpha \choose 2}z^{2}+\cdots .}$

Тождество можно получить, показав, что обе стороны удовлетворяют дифференциальному уравнению (1 + z ) f' ( z ) = α f ( z ) .

Радиус сходимости этого ряда равен 1. Альтернативное выражение:

${\displaystyle {\frac {1}{(1-z)^{\alpha +1}}}=\sum _{n=0}^{\infty }{n+\alpha \choose n}z^{n}}$

где личность

${\displaystyle {n \choose k}=(-1)^{k}{k-n-1 \choose k}}$

применены.

Мультимножественный (растущий) биномиальный коэффициент

Биномиальные коэффициенты подсчитывают подмножества заданного размера из заданного набора. Связанная с этим комбинаторная задача состоит в подсчете мультимножеств заданного размера с элементами, взятыми из заданного набора, то есть подсчете количества способов выбора определенного количества элементов из заданного набора с возможностью многократного выбора одного и того же элемента. Полученные числа называются коэффициентами мультимножества ; ^{В [18]} обозначается количество способов «множественного выбора» (т.е. выбора с заменой) k элементов из n набора элементов . ${\textstyle \left(\!\!{\binom {n}{k}}\!\!\right)}$

Чтобы избежать двусмысленности и путаницы с основным обозначением n
в этой статье, пусть f = n = r + ( k − 1) и r = f − ( k − 1) .

Коэффициенты мультимножества могут быть выражены через биномиальные коэффициенты по правилу

$${\displaystyle {\binom {f}{k}}=\left(\!\!{\binom {r}{k}}\!\!\right)={\binom {r+k-1}{k}}.}$$

падающий факториал

$${\displaystyle (f)_{k}=f^{\underline {k}}=(f-k+1)\cdots (f-3)\cdot (f-2)\cdot (f-1)\cdot f,}$$

$${\displaystyle r^{(k)}=\,r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1);}$$

$${\displaystyle 17\cdot 18\cdot 19\cdot 20\cdot 21=(21)_{5}=21^{\underline {5}}=17^{\overline {5}}=17^{(5)}.}$$

$${\displaystyle {\binom {f}{k}}={\frac {(f)_{k}}{k!}}={\frac {(f-k+1)\cdots (f-2)\cdot (f-1)\cdot f}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}},}$$

$${\displaystyle \left(\!\!{\binom {r}{k}}\!\!\right)={\frac {r^{(k)}}{k!}}={\frac {r\cdot (r+1)\cdot (r+2)\cdots (r+k-1)}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}}.}$$

Обобщение на отрицательные целые числа n

Биномиальные коэффициенты C  ( n , k ) , расширенные для отрицательных и дробных n , проиллюстрированы простым биномом . Можно заметить, что треугольник Паскаля поворачивается, а альтернативные члены инвертируются. Случай n  = −1 дает ряд Гранди .

Для любого n

${\displaystyle {\begin{aligned}{\binom {-n}{k}}&={\frac {-n\cdot -(n+1)\dots -(n+k-2)\cdot -(n+k-1)}{k!}}\\&=(-1)^{k}\;{\frac {n\cdot (n+1)\cdot (n+2)\cdots (n+k-1)}{k!}}\\&=(-1)^{k}{\binom {n+k-1}{k}}\\&=(-1)^{k}\left(\!\!{\binom {n}{k}}\!\!\right)\;.\end{aligned}}}$

В частности, биномиальные коэффициенты, оцениваемые как отрицательные целые числа n , задаются знаковыми коэффициентами мультимножества. В частном случае это сводится к ${\displaystyle n=-1}$ ${\displaystyle (-1)^{k}={\binom {-1}{k}}=\left(\!\!{\binom {-k}{k}}\!\!\right).}$

Например, если n = −4 и k = 7, то r = 4 и f = 10:

${\displaystyle {\begin{aligned}{\binom {-4}{7}}&={\frac {-10\cdot -9\cdot -8\cdot -7\cdot -6\cdot -5\cdot -4}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=(-1)^{7}\;{\frac {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=\left(\!\!{\binom {-7}{7}}\!\!\right)\left(\!\!{\binom {4}{7}}\!\!\right)={\binom {-1}{7}}{\binom {10}{7}}.\end{aligned}}}$

Два вещественных или комплексных аргумента

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

${\displaystyle {x \choose y}={\frac {\Gamma (x+1)}{\Gamma (y+1)\Gamma (x-y+1)}}={\frac {1}{(x+1)\mathrm {B} (y+1,x-y+1)}}.}$

Это определение наследует следующие дополнительные свойства от : ${\displaystyle \Gamma }$

${\displaystyle {x \choose y}={\frac {\sin(y\pi )}{\sin(x\pi )}}{-y-1 \choose -x-1}={\frac {\sin((x-y)\pi )}{\sin(x\pi )}}{y-x-1 \choose y};}$

более того,

${\displaystyle {x \choose y}\cdot {y \choose x}={\frac {\sin((x-y)\pi )}{(x-y)\pi }}.}$

Результирующая функция мало изучена и, по-видимому, впервые была изображена в виде графика (Fowler 1996). Примечательно, что многие биномиальные тождества терпят неудачу: за исключением n положительного (настолько отрицательного). Поведение довольно сложное и заметно различается в разных октантах (то есть относительно осей x и y и линии ), при этом поведение для отрицательного x имеет особенности при отрицательных целочисленных значениях и шахматную доску положительных и отрицательных областей: ${\textstyle {\binom {n}{m}}={\binom {n}{n-m}}}$ ${\textstyle {\binom {-n}{m}}\neq {\binom {-n}{-n-m}}}$ ${\displaystyle -n}$ ${\displaystyle y=x}$

• в октанте это плавно интерполированная форма обычного бинома с гребнем («гребень Паскаля»). ${\displaystyle 0\leq y\leq x}$
• в октанте и квадранте функция близка к нулю. ${\displaystyle 0\leq x\leq y}$ ${\displaystyle x\geq 0,y\leq 0}$
• в квадранте функция попеременно очень большая положительная и отрицательная на параллелограммах с вершинами ${\displaystyle x\leq 0,y\geq 0}$
  $${\displaystyle (-n,m+1),(-n,m),(-n-1,m-1),(-n-1,m)}$$
• в октанте поведение снова поочередно очень большое, положительное и отрицательное, но на квадратной сетке. ${\displaystyle 0>x>y}$
• в октанте оно близко к нулю, за исключением вблизи особенностей. ${\displaystyle -1>y>x+1}$

Обобщение на q -ряды

Биномиальный коэффициент имеет q-аналоговое обобщение, известное как биномиальный коэффициент Гаусса .

Обобщение на бесконечные кардиналы

Определение биномиального коэффициента можно обобщить на бесконечные кардиналы , определив:

${\displaystyle {\alpha \choose \beta }=\left|\left\{B\subseteq A:\left|B\right|=\beta \right\}\right|}$

где A — некоторое множество мощности . Можно показать, что обобщенный биномиальный коэффициент четко определен в том смысле, что независимо от того, какой набор мы выберем для представления кардинального числа , он останется неизменным. Для конечных кардиналов это определение совпадает со стандартным определением биномиального коэффициента. ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\textstyle {\alpha \choose \beta }}$

Приняв аксиому выбора , можно показать это для любого бесконечного кардинала . ${\textstyle {\alpha \choose \alpha }=2^{\alpha }}$ ${\displaystyle \alpha }$

Смотрите также

• Биномиальное преобразование
• Число Деланной
• Эйлерово число
• Гипергеометрическая функция
• Список факториальных и биномиальных тем
• Представление Маколея целого числа
• число Моцкина
• Кратность элементов в треугольнике Паскаля
• Число Нараяны
• Теорема о звезде Давида
• Любопытная личность Сана
• Таблица ньютоновских рядов
• Трехчленное расширение

Примечания

1. Хайэм (1998)
2. Лилавати , раздел 6, глава 4 (см. Кнут (1997)).
3. Успенский 1937, с. 18
4. См. (Graham, Knuth & Patashnik 1994), где также определяется . Альтернативные обобщения, такие как два вещественных или комплексных аргумента с использованием функции Гамма, присваивают ненулевые значения for , но это приводит к сбою большинства тождеств биномиальных коэффициентов и, следовательно, не широко используется в большинстве определений. Один из таких вариантов ненулевых значений приводит к эстетически приятной «ветряной мельнице Паскаля» в Хилтоне, Холтоне и Педерсене, « Математические размышления: в комнате с множеством зеркал» , Springer, 1997, но приводит к тому, что даже личность Паскаля терпит неудачу (в начале). ${\displaystyle {\tbinom {n}{k}}=0}$ ${\displaystyle k<0}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle k<0}$
5. Мьюир, Томас (1902). «Примечание к избранным сочетаниям». Труды Королевского общества Эдинбурга .
6. Это можно рассматривать как дискретный аналог теоремы Тейлора . Он тесно связан с полиномом Ньютона . Переменные суммы этой формы могут быть выражены как интеграл Нёрлунда – Райса .
7. Градштейн и Рыжик (2014, стр. 3–4).
8. Бордман, Майкл (2004), «Числа падения яиц», Журнал Mathematics Magazine , 77 (5): 368–372, doi : 10.2307/3219201, JSTOR  3219201, MR  1573776, хорошо известно, что закрытой формы не существует. (т.е. прямая формула) для частичной суммы биномиальных коэффициентов.
9. см. индукцию, развитую в уравнении (7) с. 1389 в Аупетите, Майкл (2009), «Почти однородное многоразделение с детерминированным генератором», Neurocomputing , 72 (7–9): 1379–1389, doi : 10.1016/j.neucom.2008.12.024, ISSN  0925-2312..
10. Руис, Себастьян (1996). «Алгебраическое тождество, ведущее к теореме Вильсона». Математический вестник . 80 (489): 579–582. arXiv : math/0406086 . дои : 10.2307/3618534. JSTOR  3618534. S2CID  125556648.
11. Бенджамин и Куинн 2003, стр. 4–5.
12. Фархи, Бакир (2007). «Нетривиальные нижние оценки наименьшего общего кратного некоторой конечной последовательности целых чисел». Журнал теории чисел . 125 (2): 393–411. arXiv : 0803.0290 . дои : 10.1016/j.jnt.2006.10.017. S2CID  115167580.
13. Томас М. Обложка; Джой А. Томас (18 июля 2006 г.). Элементы теории информации . Хобокен, Нью-Джерси: Уайли. ISBN 0-471-24195-4.
14. Ф. Дж. МакВильямс; НЯА Слоан (1981). Теория кодов, исправляющих ошибки . Том. 16 (3-е изд.). Северная Голландия. ISBN 0-444-85009-0.
15. Спенсер, Джоэл ; Флореску, Лаура (2014). Асимптопия . Студенческая математическая библиотека. Том. 71. АМС . п. 66. ИСБН 978-1-4704-0904-3. ОКЛК  865574788.
16. Спенсер, Джоэл ; Флореску, Лаура (2014). Асимптопия . Студенческая математическая библиотека. Том. 71. АМС . п. 59. ИСБН 978-1-4704-0904-3. ОКЛК  865574788.
17. см., например, Ash (1990, стр. 121) или Flum & Grohe (2006, стр. 427).
18. Мунарини, Эмануэле (2011), «Матрицы Риордана и суммы гармонических чисел» (PDF) , Applicable Analysis and Discrete Mathematics , 5 (2): 176–200, doi : 10.2298/AADM110609014M, MR  2867317.

Рекомендации

• Эш, Роберт Б. (1990) [1965]. Теория информации . ISBN Dover Publications, Inc. 0-486-66521-6.
• Бенджамин, Артур Т .; Куинн, Дженнифер Дж. (2003). Доказательства, которые действительно имеют значение: искусство комбинаторного доказательства . Математические изложения Дольчиани. Том. 27. Математическая ассоциация Америки . ISBN 978-0-88385-333-7.
• Брайант, Виктор (1993). Аспекты комбинаторики . Издательство Кембриджского университета. ISBN 0-521-41974-3.
• Флум, Йорг; Гроэ, Мартин (2006). Параметризованная теория сложности. Спрингер. ISBN 978-3-540-29952-3. Архивировано из оригинала 18 ноября 2007 г. Проверено 28 августа 2017 г.
• Фаулер, Дэвид (январь 1996 г.). «Биномиальная коэффициентная функция». Американский математический ежемесячник . Математическая ассоциация Америки. 103 (1): 1–17. дои : 10.2307/2975209. JSTOR  2975209.
• Гетгелак, П. (1987). «Вычисление биномиальных коэффициентов». Американский математический ежемесячник . 94 (4): 360–365. дои : 10.2307/2323099. JSTOR  2323099.
• Грэм, Рональд Л .; Кнут, Дональд Э .; Паташник, Орен (1994). Конкретная математика (второе изд.). Аддисон-Уэсли. стр. 153–256. ISBN 0-201-55802-5.
• Градштейн И.С.; Рыжик, И.М. (2014). Таблица интегралов, рядов и произведений (8-е изд.). Академическая пресса. ISBN 978-0-12-384933-5.
• Гриншпан, А.З. (2010), «Взвешенные неравенства и отрицательные биномы», Успехи в прикладной математике , 45 (4): 564–606, doi : 10.1016/j.aam.2010.04.004
• Хайэм, Николас Дж. (1998). Справочник по письму для математических наук . СИАМ . п. 25. ISBN 0-89871-420-6.
• Кнут, Дональд Э. (1997). Искусство компьютерного программирования, Том 1: Фундаментальные алгоритмы(Третье изд.). Аддисон-Уэсли. стр. 52–74. ISBN 0-201-89683-4.
• Сингмастер, Дэвид (1974). «Заметки о биномиальных коэффициентах. III. Любое целое число делит почти все биномиальные коэффициенты». Журнал Лондонского математического общества . 8 (3): 555–560. дои : 10.1112/jlms/s2-8.3.555.
• Шилов, Г.Э. (1977). Линейная алгебра . Дуврские публикации. ISBN 978-0-486-63518-7.
• Успенский, Джеймс (1937), Введение в математическую вероятность, McGraw-Hill

Внешние ссылки

• «Биномиальные коэффициенты», Математическая энциклопедия , EMS Press , 2001 [1994]
• Эндрю Грэнвилл (1997). «Арифметические свойства биномиальных коэффициентов I. Биномиальные коэффициенты по модулю простых степеней». Конференция CMS. Проц . 20 : 151–162. Архивировано из оригинала 23 сентября 2015 г. Проверено 3 сентября 2013 г.

В эту статью включены материалы из следующих статей PlanetMath , которые доступны по лицензии Creative Commons Attribution/Share-Alike : Биномиальный коэффициент, Верхняя и нижняя границы биномиального коэффициента, Биномиальный коэффициент — целое число, Обобщенные биномиальные коэффициенты.