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

«nCk» перенаправляется сюда. Чтобы узнать о других значениях, см. NCK (значения) .

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

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

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

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

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

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

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

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

и биномиальный коэффициент ${\tbinom {4}{2}}={\tfrac {4\times 3}{2\times 1}}={\tfrac {4!}{2!2!}}=6$ коэффициент при x ² срок.

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

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

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

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

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

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

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

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

к н	0	1	2	3	4	⋯
0	1	0	0	0	0	⋯
1	1	1	0	0	0	⋯
2	1	2	1	0	0	⋯
3	1	3	3	1	0	⋯
4	1	4	6	4	1	⋯
⋮	⋮	⋮	⋮	⋮	⋮	⋱
Первые несколько биномиальных коэффициентов на левом треугольнике Паскаля

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

$(x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n-k}$ ( ∗ )

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

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

значения

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

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

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

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

для всех целых чисел $n,k$ такой, что $1\leq k<n,$с граничными значениями

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

для всех целых чисел n ≥ 0 .

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

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

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

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

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

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

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

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

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

где н ! обозначает факториал числа n . Эта формула следует из мультипликативной формулы, приведенной выше, путем умножения числителя и знаменателя на ( n − k )! ; как следствие, он включает в себя множество факторов, общих для числителя и знаменателя. Это менее практично для явных вычислений (в случае, когда k мало, а n велико), если сначала не отменить общие факторы (в частности, поскольку значения факториалов растут очень быстро). Формула действительно демонстрирует симметрию, которая менее очевидна из мультипликативной формулы (хотя она и есть из определений).

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

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

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

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

Основная статья: Биномиальный ряд

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

$${\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), что оправдывает дальнейшее обращение к ${\tbinom {\alpha }{k}}$ биномиальные коэффициенты:

$(1+X)^{\alpha }=\sum _{k=0}^{\infty }{\alpha \choose k}X^{k}.$ ( 2 )

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

$$(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 \choose k}+{n \choose k+1}={n+1 \choose k+1},$ ( 3 )

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

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

0:											1
1:										1		1
2:									1		2		1
3:								1		3		3		1
4:							1		4		6		4		1
5:						1		5		10		10		5		1
6:					1		6		15		20		15		6		1
7:				1		7		21		35		35		21		7		1
8:			1		8		28		56		70		56		28		8		1
9.		1		9		36		84		126		126		84		36		9		1
10.	1		10		45		120		210		252		210		120		45		10		1

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

$(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}.$

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

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

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

как

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

${\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 полином ${\tbinom {t}{k}}$ может быть охарактеризован как уникальный степени k полином p ( t ) , удовлетворяющий p (0) = p (1) = ⋯ = p ( k - 1) = 0 и p ( k ) = 1 .

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

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

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

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

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

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

пространства

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

$a_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}p(i).$ ( 4 )

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

Основная статья: Целочисленный полином

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

Пример

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

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

Тождества

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

${\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}$ ( 5 )

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

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

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

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

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

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

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

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

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

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

Суммы

Формула

$\sum _{k=0}^{n}{\binom {n}{k}}=2^{n}$ ( ∗∗ )

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

Формулы

$\sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}$ ( 6 )

и

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

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

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

$\sum _{j=0}^{k}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n}{k}}$ ( 7 )

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

${\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 как $1^{2}+3^{2}+3^{2}+1^{2}=20.$

$\sum _{j=0}^{m}{\binom {m}{j}}^{2}={\binom {2m}{m}},$ ( 8 )

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

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

$\sum _{m=0}^{n}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n+1}{k+1}}.$ ( 9 )

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

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

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

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

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

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

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

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

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

${\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 эти серии имеют особенно красивые формы; например,

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

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

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

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

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

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

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

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

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

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

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

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

с особым случаем

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

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

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

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

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

$\sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(n-j)=n!a_{n}$ ( 10 )

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

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

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

где m и d — комплексные числа. Отсюда следует немедленное применение ( 10 ) к многочлену $Q(x):=P(m+dx)$ вместо $P(x)$, и наблюдая за этим $Q(x)$ все еще имеет степень, меньшую или равную n , и что его коэффициент степени n равен d ^н н _​ .

Серия ​ ${\textstyle {\frac {k-1}{k}}\sum _{j=0}^{\infty }{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}}$ сходится при k ≥ 2. Эта формула используется при анализе немецкой танковой задачи . Это следует из ${\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}}}}$ что доказывается индукцией по M .

с

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

$\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 элементов среди выбранных. Правая часть имеет то же значение, потому что есть ${\tbinom {n}{q}}$ способы выбора набора из q элементов для маркировки и $2^{n-q}$ выбрать, какой из оставшихся элементов [ n ] также принадлежит подмножеству.

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

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

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

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

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

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

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

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

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

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

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

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

См. также: Комбинация § Количество k-комбинаций для всех k.

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

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

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

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

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

$\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 — неотрицательные целые числа.

Непрерывные личности

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

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

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

$\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 простое, то

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

для каждого k с $0\leq k\leq n-1.$В более общем смысле, это остается верным, если n — любое число и k таково, что все числа между 1 и k взаимно просты с n .

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

${\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 обычная производящая функция последовательности ${\tbinom {n}{0}},{\tbinom {n}{1}},{\tbinom {n}{2}},\ldots$ является

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

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

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

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

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

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

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

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

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

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

$\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, делящая ${\tbinom {m+n}{m}}$ равно п ^с , где c — количество переносов при m и n добавлении по основанию p .Эквивалентно, показатель степени простого числа p в ${\tbinom {n}{k}}$равно количеству целых неотрицательных чисел j таких, что дробная часть k / p ^дж больше дробной части n / p ^дж . Из этого можно сделать вывод, что ${\tbinom {n}{k}}$ делится на n / НОД ( n , k ). В частности, отсюда следует, что p делит ${\tbinom {p^{r}}{s}}$ для всех натуральных чисел r и s таких, что s < p ^р . Однако это не относится к высшим степеням p : например, 9 не делит ${\tbinom {9}{6}}$.

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

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

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

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

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

${\binom {n+k}{k}}$ кратно ${\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 является простым тогда и только тогда, когдавсе промежуточные биномиальные коэффициенты

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

делятся на n .

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

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

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

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

и

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

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

Первое неравенство следует из того, что

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

и каждый из этих $k$ Условия в этом продукте ${\textstyle \geq {\frac {n}{k}}}$. Аналогичный аргумент можно привести и для доказательства второго неравенства. Окончательное строгое неравенство эквивалентно ${\textstyle e^{k}>k^{k}/k!}$, это понятно, поскольку правая часть является членом показательного ряда ${\textstyle e^{k}=\sum _{j=0}^{\infty }k^{j}/j!}$.

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

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

где оба равенства могут быть достигнуты.

Следующие границы полезны в теории информации:

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

где $H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)$ — двоичная функция энтропии . Его можно еще ужесточить

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

для всех $1\leq k\leq n-1$.

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

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

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

Поскольку формы неравенства формулы Стирлинга также ограничивают факториалы, небольшие варианты вышеуказанного асимптотического приближения дают точные границы.В частности, когда $n$ достаточно велик, имеется

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

и ${\sqrt {n}}{2n \choose n}\geq 2^{2n-1}$. В более общем смысле, для m ≥ 2 и n ≥ 1 (опять же, применяя формулу Стирлинга к факториалам биномиального коэффициента),

$${\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}}}$. Например, если $|n/2-k|=o(n^{2/3})$ затем

$${\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 знак равно п - 2 k .

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

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

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

Суммы

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

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

Более точные границы даются формулами

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

действительно для всех целых чисел $n>k\geq 1$ с $\varepsilon \doteq k/n\leq 1/2$.

коэффициенты

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

$$(-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}}}}$$

что дает асимптотические формулы

$${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)$$

как $k\to \infty$.

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

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

также. (Здесь $H_{k}$ - номер k -й гармоники и $\gamma$ – постоянная Эйлера–Машерони .)

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

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

оставаться верным, всякий раз, когда $k\to \infty$ и $j/k\to x$ для некоторого комплексного числа $x$.

Обобщения

Обобщение до многочленов

Основная статья: Полиномиальная теорема

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

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

где

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

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

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

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

${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 — номер контейнера.

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

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

и симметрия:

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

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

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

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

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

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

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

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

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

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

Произведения

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

${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- й строке треугольника Паскаля определяется формулой:

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

Разложение частичных дробей

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

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

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

Основная статья: Биномиальный ряд

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

$(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. Альтернативное выражение:

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

где личность

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

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

Мультимножественный (растущий

Основная статья: Multichoose § Подсчет мультимножеств

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

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

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

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

Одна из возможных альтернативных характеристик этой идентичности такова:Мы можем определить падающий факториал как

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

и соответствующий восходящий факториал как

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

так, например,

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

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

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

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

$$\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 любого

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

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

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

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

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

${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)}}.$

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

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

более того,

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

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

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

Обобщение на q -серию

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

на

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

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

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

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

См. также

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

Ссылки

• Эш, Роберт Б. (1990) [1965]. Теория информации . Dover Publications, Inc. ISBN  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 .
• Shilov, G. E. (1977). Linear algebra . Dover Publications. 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 : Биномиальный коэффициент , Верхняя и нижняя границы биномиального коэффициента , Биномиальный коэффициент является целым числом , Обобщенные биномиальные коэффициенты .