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

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

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

Визуализация биномиального разложения до 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}}}$

а биномиальный коэффициент — это коэффициент при члене x ² . ${\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 года индийский математик Бхаскарачарья дал изложение биномиальных коэффициентов в своей книге Līlāvatī . ^[2] ${\displaystyle {\tbinom {n}{k}}}$

Альтернативные обозначения включают C ( n , k ) , _n C _k , ⁿ C _k , C^к
_н, ^[3] С^н
_к, и C _{n , k} , во всех из которых C обозначает комбинации или выборы ; нотация C означает количество способов выбрать k из n объектов. Многие калькуляторы используют варианты нотации 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}}}$

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

Один метод использует рекурсивную , чисто аддитивную формулу для всех целых чисел, такую, что с граничными значениями для всех целых чисел n ≥ 0 . $${\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}$$

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

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

Более эффективный метод вычисления индивидуальных биномиальных коэффициентов дается формулой , где числитель первой дроби, , является убывающим факториалом . Эту формулу проще всего понять для комбинаторной интерпретации биномиальных коэффициентов. Числитель дает количество способов выбрать последовательность из k различных объектов, сохраняя порядок выбора, из набора из n объектов. Знаменатель подсчитывает количество различных последовательностей, которые определяют одну и ту же k -комбинацию, когда порядок игнорируется. $${\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}},}$$ ${\displaystyle n^{\underline {k}}}$

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

Формула факториала

Наконец, хотя и невыгодная с точки зрения вычислений, существует компактная форма, часто используемая в доказательствах и выводах, которая многократно использует знакомую функцию факториала : где n ! обозначает факториал n . Эта формула следует из мультипликативной формулы выше путем умножения числителя и знаменателя на ( n − k )! ; как следствие, она включает в себя много множителей, общих для числителя и знаменателя. Она менее практична для явных вычислений (в случае, когда k мало, а n велико), если только общие множители сначала не будут отменены (в частности, поскольку значения факториала растут очень быстро). Формула действительно демонстрирует симметрию, которая менее очевидна из мультипликативной формулы (хотя она есть из определений) $${\displaystyle {\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{for }}\ 0\leq k\leq n,}$$

что приводит к более эффективной мультипликативной вычислительной процедуре. Используя обозначение падающего факториала , $${\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 с | 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 равны нулю, ^[5] и бесконечный ряд становится конечной суммой, тем самым восстанавливая биномиальную формулу. Однако для других значений α , включая отрицательные целые числа и рациональные числа, ряд действительно бесконечен.

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

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 элементов, если разрешены повторения. См. Multiset . ${\displaystyle {\tbinom {n+k-1}{k}}}$
• Имеются строки, содержащие k единиц и n нулей. ${\displaystyle {\tbinom {n+k}{k}}}$
• Существуют строки, состоящие из k единиц и n нулей, такие, что никакие две единицы не являются соседними. ^[6] ${\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 многочлен можно охарактеризовать как уникальный многочлен степени k p ( t ), удовлетворяющий соотношениям 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 ). Явно, ^[7] ${\textstyle \sum _{k=0}^{d}a_{k}{\binom {t}{k}}}$

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

Каждый многочлен является целочисленным : он имеет целочисленное значение при всех целочисленных входах . (Один из способов доказать это — индукция по k с использованием тождества Паскаля .) Следовательно, любая целочисленная линейная комбинация полиномов с биномиальными коэффициентами также является целочисленной. Наоборот, ( 4 ) показывает, что любой целочисленный многочлен является целочисленной линейной комбинацией этих полиномов с биномиальными коэффициентами. В более общем смысле, для любого подкольца R поля K с характеристикой 0 многочлен из 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}}}$

${\displaystyle ={\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 эти ряды имеют особенно красивые формы; например, ^[8]

${\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}}}$

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

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

с особым случаем ^[10]

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

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

${\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 ) к многочлену ⁠ ⁠ ${\displaystyle Q(x):=P(m+dx)}$ вместо ⁠ ⁠ ${\displaystyle P(x)}$ , и наблюдения, что ⁠ ⁠ ${\displaystyle Q(x)}$ все еще имеет степень, меньшую или равную n , и что его коэффициент степени n равен d ⁿ a _n .

Ряд сходится при 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 , то тождество имеет следующее комбинаторное доказательство. ^[12] Можно показать по индукции , что F ( n ) подсчитывает количество способов, которыми полоса квадратов n × 1 может быть покрыта плитками 2 × 1 и 1 × 1. С другой стороны, если такая плитка использует ровно k из плиток 2 × 1 , то она использует n − 2 k из плиток 1 × 1 , и, таким образом, использует n − k плиток в общей сложности. Существуют способы упорядочить эти плитки, и поэтому суммирование этого коэффициента по всем возможным значениям k дает тождество. $${\displaystyle \sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\binom {n-k}{k}}=F(n)}$$ ${\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 — простое число, то для любого k с Более общим образом, это остается верным, если n — любое число, а k таково, что все числа от 1 до k взаимно просты с n . $${\displaystyle {\binom {n-1}{k}}\equiv (-1)^{k}\mod n}$$ ${\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 равна p ^c , где c — число переносов при сложении m и n в системе счисления с основанием p . Эквивалентно, показатель степени простого числа p в равен числу неотрицательных целых чисел 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}}}$

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

${\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 < к < р

поскольку — натуральное число, а 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!}$

Из свойств делимости можно сделать вывод, что оба равенства могут быть достигнуты. ^[13] $${\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}},}$$

Следующие границы полезны в теории информации: ^{[14] : 353} где — бинарная функция энтропии . Ее можно еще больше сузить до для всех . ^{[15] : 309} $${\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)}}$$ ${\displaystyle 1\leq k\leq n-1}$

Обаникбольшой

Приближение Стирлинга дает следующее приближение, справедливое, когда оба стремятся к бесконечности: Поскольку формы неравенства формулы Стирлинга также ограничивают факториалы, небольшие изменения в приведенном выше асимптотическом приближении дают точные границы. В частности, когда достаточно велико, то и . В более общем случае, для m ≥ 2 и n ≥ 1 (опять же, применяя формулу Стирлинга к факториалам в биномиальном коэффициенте), ${\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 }}}}$$ ${\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 , существуют различные точные асимптотические оценки для биномиального коэффициента . Например, если то где d = n − 2 k . ^[16] ${\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)}}$$

ннамного больше, чемк

Если n велико и k равно o ( n ) (то есть если k / n → 0 ), то где снова o — это маленькая нотация o . ^[17] $${\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)}$$

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

Простую и грубую верхнюю границу для суммы биномиальных коэффициентов можно получить с помощью биномиальной теоремы : Более точные границы даются формулой , которая действительна для всех целых чисел с . ^[18] $${\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},}$$ ${\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 }$

Это асимптотическое поведение также содержится в приближении . (Здесь — номер k -й гармоники , а — постоянная Эйлера–Маскерони .) $${\displaystyle {z+k \choose k}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}}$$ ${\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}}}$

Биномиальный коэффициент сн = 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}}$

применяется.

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

Биномиальные коэффициенты подсчитывают подмножества заданного размера из заданного набора. Связанная комбинаторная задача заключается в подсчете мультимножеств заданного размера с элементами, взятыми из заданного набора, то есть в подсчете количества способов выбора определенного количества элементов из заданного набора с возможностью повторного выбора одного и того же элемента. Полученные числа называются коэффициентами мультимножества ; ^[19] количество способов «мультивыбрать» (т. е. выбрать с заменой) 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}}.}$$

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

Биномиальные коэффициенты 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-аналоговое обобщение, известное как гауссовский биномиальный коэффициент .

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

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

${\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), где также дано определение для . Альтернативные обобщения, такие как для двух действительных или комплексных аргументов с использованием гамма-функции, присваивают ненулевые значения для , но это приводит к тому, что большинство тождеств биномиальных коэффициентов перестают работать, и поэтому широко не используется большинством определений. Один из таких выборов ненулевых значений приводит к эстетически приятной «ветряной мельнице Паскаля» в Hilton, Holton and Pedersen, Mathematical reflections: in a room with many mirrors , Springer, 1997, но даже тождество Паскаля перестает работать (в начале координат). ${\displaystyle {\tbinom {n}{k}}=0}$ ${\displaystyle k<0}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle k<0}$
5. Когда — неотрицательное целое число, так как -й множитель числителя равен . Таким образом, -й член — это нулевое произведение для всех . ${\displaystyle \alpha =n}$ ${\displaystyle \textstyle {\binom {n}{k}}=0}$ ${\displaystyle k>n}$ ${\displaystyle (k=n+1)}$ ${\displaystyle n-(n+1)+1=0}$ ${\displaystyle k}$ ${\displaystyle k\geq n+1}$
6. Мьюир, Томас (1902). «Заметка об избранных комбинациях». Труды Королевского общества Эдинбурга .
7. Это можно рассматривать как дискретный аналог теоремы Тейлора . Он тесно связан с полиномом Ньютона . Знакопеременные суммы этой формы могут быть выражены как интеграл Нёрлунда–Райса .
8. Градштейн и Рыжик (2014, стр. 3–4).
9. Бордман, Майкл (2004), «Числа капли яйца», Mathematics Magazine , 77 (5): 368–372, doi :10.2307/3219201, JSTOR  3219201, MR  1573776, хорошо известно, что не существует замкнутой формы (то есть прямой формулы) для частичной суммы биномиальных коэффициентов..
10. см. индукцию, разработанную в уравнении (7) стр. 1389 в Aupetit, Michael (2009), "Почти однородное многораздельное разбиение с детерминированным генератором", Neurocomputing , 72 (7–9): 1379–1389, doi :10.1016/j.neucom.2008.12.024, ISSN  0925-2312.
11. Руис, Себастьян (1996). «Алгебраическое тождество, приводящее к теореме Вильсона». The Mathematical Gazette . 80 (489): 579–582. arXiv : math/0406086 . doi :10.2307/3618534. JSTOR  3618534. S2CID  125556648.
12. Бенджамин и Куинн 2003, стр. 4−5.
13. Farhi, Bakir (2007). «Нетривиальные нижние оценки наименьшего общего кратного некоторой конечной последовательности целых чисел». Журнал теории чисел . 125 (2): 393–411. arXiv : 0803.0290 . doi : 10.1016/j.jnt.2006.10.017. S2CID  115167580.
14. Томас М. Кавер; Джой А. Томас (18 июля 2006 г.). Элементы теории информации . Хобокен, Нью-Джерси: Wiley. ISBN 0-471-24195-4.
15. FJ MacWilliams; NJA Sloane (1981). Теория кодов, исправляющих ошибки . Т. 16 (3-е изд.). Северная Голландия. ISBN 0-444-85009-0.
16. Спенсер, Джоэл ; Флореску, Лаура (2014). Асимптопия . Студенческая математическая библиотека. Т. 71. AMS . С. 66. ISBN 978-1-4704-0904-3. OCLC  865574788.
17. Спенсер, Джоэл ; Флореску, Лаура (2014). Асимптопия . Студенческая математическая библиотека. Т. 71. AMS . С. 59. ISBN 978-1-4704-0904-3. OCLC  865574788.
18. см., например, Ash (1990, стр. 121) или Flum & Grohe (2006, стр. 427).
19. Мунарини, Эмануэле (2011), «Матрицы Риордана и суммы гармонических чисел» (PDF) , Прикладной анализ и дискретная математика , 5 (2): 176–200, doi :10.2298/AADM110609014M, MR  2867317.

Ссылки

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

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

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

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