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

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

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

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

${\ displaystyle {\ begin {align} (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 {align}}}$

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

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

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

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

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

История и обозначения [ править ]

Андреас фон Эттингсгаузен ввел обозначение в 1826 году, ^[1] хотя числа были известны столетия назад (см . Треугольник Паскаля ). Самое раннее известный подробное обсуждение биномиальных коэффициентов в комментарии десятого века по Халейудху , на древнем санскрите тексте, Пингал «s Chandaḥśāstra . Примерно в 1150 году индийский математик Бхаскарачарья представил биномиальные коэффициенты в своей книге Līlāvatī . ^[2]${\displaystyle {\tbinom {n}{k}}}$

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

Определение и толкования [ править ]

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

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

( * )

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

Другое использование этого числа - в комбинаторике, где оно дает количество способов, без учета порядка, что k объектов могут быть выбраны из числа n объектов; более формально, число K - элементных подмножеств (или к - комбинаций ) в качестве п - элементного множества. Это число можно рассматривать как равное первому определению, независимо от любой из приведенных ниже формул для его вычисления: если в каждом из n факторов степени (1 + X ) ⁿ кто-то временно помечает член X знаком индекс i (от 1 до n ), затем каждое подмножествоk индексов дает после разложения вклад X ^k , и коэффициент этого монома в результате будет числом таких подмножеств. Это, в частности, показывает, что это натуральное число для любых натуральных чисел n и k . Есть много других комбинаторных интерпретаций биномиальных коэффициентов (задачи подсчета, для которых ответ дается выражением биномиальных коэффициентов), например, количество слов, состоящих из n битов (цифры 0 или 1), сумма которых равна k , определяется как , в то время как количество способов записать, где каждое a _i является неотрицательным целым числом, определяется как${\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- комбинаций.

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

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

Рекурсивная формула [ править ]

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

${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}\quad {\text{for all integers }}n,k:1\leq k\leq n-1,}$

с начальными / граничными значениями

${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1\quad {\text{for all integers }}n\geq 0,}$

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

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

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

Факториальная формула [ править ]

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

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

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

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

( 1 )

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

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

Обобщение и связь с биномиальным рядом [ править ]

Мультипликативная формула позволяет расширить определение биномиальных коэффициентов ^[3] , заменив 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}}}$

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

( 2 )

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

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

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

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

( 3 )

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

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

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

Строка номер 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 нулей, что нет двух смежных единиц. ^[4]${\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 !:${\displaystyle \scriptstyle {\binom {t}{k}}}$

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

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

Таким образом, его можно вычислить при любом действительном или комплексном числе 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}}.}$

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

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

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

( 4 )

Целочисленные многочлены [ править ]

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

Пример [ править ]

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

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

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

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

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

( 5 )

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

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

Кроме того, может быть полезно следующее:

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

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

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

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

Формула

${\displaystyle \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 ; пнезависимые двоичные варианты выбора (битовые строки) допускают полный выбор. Левая и правая части - это два способа подсчета одного и того же набора подмножеств, поэтому они равны.${\displaystyle 2^{n}}$

Формулы

${\displaystyle \sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}}$

( 6 )

и

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

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

Идентичность Чу-Вандермонда , которое имеет место для любых комплексных значений- м и п и любое неотрицательное целое число K , является

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

( 7 )

и может быть найден путем изучения коэффициента при разложении (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 \sum _{j=0}^{m}{\binom {m}{j}}^{2}={\binom {2m}{m}},}$

( 8 )

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

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

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

( 9 )

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

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

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

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

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

в частном случае ^[8]

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

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

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

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

( 10 )

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

В более общем плане для ( 10 ),

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

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

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

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

Строка суммы коэффициентов [ править ]

Количество k - комбинаций для всех k , является суммой n- й строки (считая от 0) биномиальных коэффициентов. Эти комбинации нумеруются цифрами 1 набора чисел с основанием 2, считая от 0 до , где каждая позиция цифры является элементом из набора n .${\displaystyle \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}}}$

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

Генерация функций [ править ]

Обычные производящие функции [ править ]

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

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

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

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

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

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

делятся на n .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

И n, и k большие [ править ]

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

и, вообще говоря, при m  ≥ 2 и n  ≥ 1 ^{[ почему? ]}

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

Еще одно полезное асимптотическое приближение, когда оба числа растут с одинаковой скоростью ^{[ требуется пояснение ]} :

${\displaystyle \log _{2}{n \choose k}\sim nH(k/n)=k\log _{2}(n/k)+(n-k)\log _{2}(n/(n-k))}$

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

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

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

где d = n - 2 k . ^[12]

n намного больше k [ править ]

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

где снова o - небольшое обозначение o . ^[13]

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

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

${\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\epsilon (1-\epsilon )}}}\cdot 2^{H(\epsilon )\cdot n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\epsilon )\cdot n}.}$

который действителен для всех целых чисел с . ^[14]${\displaystyle n\geq k\geq 1}$${\displaystyle \epsilon \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 {(1+{\frac {1}{j}})^{-z-1}}{1-{\frac {z+1}{j}}}}}$

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

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

как .${\displaystyle k\to \infty }$

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

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

также. (Здесь находится в K -го номер гармоники и является постоянной Эйлера-Mascheroni .)${\displaystyle H_{k}}$${\displaystyle \gamma }$

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

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

верно, когда и для некоторого комплексного числа .${\displaystyle k\to \infty }$${\displaystyle j/k\to x}$${\displaystyle x}$

Обобщения [ править ]

Обобщение на многочлены [ править ]

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

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

куда

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

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

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

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

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

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

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

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

и симметрия:

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

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

Серия Тейлор [ править ]

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

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

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

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

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

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

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

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

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

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

${\displaystyle {z \choose m}{z \choose n}=\sum _{k=0}^{m}{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}}$

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

Множественный (восходящий) биномиальный коэффициент [ править ]

Биномиальные коэффициенты подсчитывают подмножества заданного размера из заданного набора. Связанная комбинаторная проблема состоит в том, чтобы подсчитать мультимножества заданного размера с элементами, взятыми из данного набора, то есть подсчитать количество способов выбора определенного количества элементов из данного набора с возможностью повторного выбора одного и того же элемента. Полученные числа называются коэффициентами мультимножества ; ^[15] обозначено количество способов «множественного выбора» (т. Е. Выбора с заменой) k элементов из набора n элементов .${\displaystyle \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 {\color {white}{\big |}}r^{(k)}=\,r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1)}$;

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

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

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

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

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

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

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

Для любого п ,

${\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} (x-y+1,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 имеет сингулярности при отрицательных целочисленных значениях и шахматную доску положительных и отрицательных областей:${\displaystyle \textstyle {{n \choose m}={n \choose n-m}}}$${\displaystyle \textstyle {{-n \choose m}\neq {-n \choose -n-m}}}$${\displaystyle -n}$${\displaystyle y=x}$

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

${\displaystyle (-n,m+1),(-n,m),(-n-1,m-1),(-n-1,m)}$

• в октанте поведение снова попеременно очень большое положительное и отрицательное, но на квадратной сетке.${\displaystyle 0>x>y}$
• в октанте она близка к нулю, за исключением вблизи особенностей.${\displaystyle -1>y>x+1}$

Обобщение на q- серию [ править ]

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

Обобщение на бесконечные кардиналы [ править ]

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

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

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

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

Биномиальный коэффициент в языках программирования [ править ]

Обозначения удобны для рукописного ввода, но неудобны для пишущих машинок и компьютерных терминалов . Многие языки программирования не предлагают стандартной подпрограммы для вычисления биномиального коэффициента, но, например, как язык программирования APL, так и (связанный) язык программирования J используют восклицательный знак: k! п.${\displaystyle {n \choose k}}$

Наивные реализации факториальной формулы, такие как следующий фрагмент на Python :

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

(В Python диапазон (k) создает список от 0 до k – 1.)

Правило Паскаля предоставляет рекурсивное определение, которое также может быть реализовано в Python, хотя оно менее эффективно:

Упомянутый выше пример также может быть написан в функциональном стиле. В следующем примере схемы используется рекурсивное определение

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

Рациональной арифметики можно легко избежать с помощью целочисленного деления

${\displaystyle {n \choose k+1}=\left[(n-k){n \choose k}\right]\div (k+1)}$

Следующая реализация использует все эти идеи

При вычислениях на языке с целыми числами фиксированной длины умножение на может быть переполнено, даже если результат подходит. Переполнения можно избежать, разделив сначала и зафиксировав результат с помощью остатка:${\displaystyle \textstyle {n \choose k+1}=\left[(n-k){n \choose k}\right]\div (k+1)}$${\displaystyle (n-k)}$

${\displaystyle {n \choose k+1}=\left[\textstyle {n \choose k}\div (k+1)\right](n-k)+{\left[{n \choose k}\ \mathrm {mod} \ (k+1)\right](n-k) \over (k+1)}}$

Реализация на языке C:

Другой способ вычислить биномиальный коэффициент при использовании больших чисел - признать, что

${\displaystyle {n \choose k}={\frac {n!}{k!\,(n-k)!}}={\frac {\Gamma (n+1)}{\Gamma (k+1)\,\Gamma (n-k+1)}}=\exp(\ln \Gamma (n+1)-\ln \Gamma (k+1)-\ln \Gamma (n-k+1)),}$

где обозначает натуральный логарифм от гамма - функции в . Это специальная функция, которая легко вычисляется и является стандартной для некоторых языков программирования, таких как использование log_gamma в Maxima , LogGamma в Mathematica , gammaln в MATLAB и в модуле Python SciPy , lngamma в PARI / GP или lgamma в C, R , ^[16] и Юля . Ошибка округления может привести к тому, что возвращаемое значение не будет целым числом.${\displaystyle \ln }$ ${\displaystyle \Gamma (n)}$${\displaystyle n}$

См. Также [ править ]

Примечания [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

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

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