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

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

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

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

${displaystyle {egin {align} (1 + x) ^ {4} & = {binom {4} {0}} x ^ {0} + {binom {4} {1}} x ^ {1} + {binom {4} {2}} x ^ {2} + {binom {4} {3}} x ^ {3} + {binom {4} {4}} x ^ {4} & = 1 + 4x + 6x ^ {2} + 4x ^ {3} + x ^ {4}, конец {выровнен}}}$

и биномиальный коэффициент ${displaystyle {binom {4} {2}} = {гидроразрыв {4!} {2! 2!}} = 6}$ коэффициент при Икс² срок.

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

${displaystyle {inom {n} {k}} = {inom {n-1} {k}} + {inom {n-1} {k-1}}.}$

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

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

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

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

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

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

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

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

(∗)

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

Другое появление этого числа - в комбинаторике, где оно дает количество способов, не обращая внимания на порядок, которые k объекты можно выбрать из числа п объекты; более формально, количество k-элементные подмножества (или k-комбинации ) из п-элементный набор. Это число можно рассматривать как равное первому определению, независимо от любой из приведенных ниже формул для его вычисления: если в каждом из п факторы власти (1 + Икс)^п один временно обозначает термин Икс с индексом я (бег от 1 до п), то каждое подмножество k индексы дают после расширения вклад Икс^k, а коэффициент этого одночлена в результате будет количеством таких подмножеств. Это, в частности, показывает, что ${displaystyle {binom {n} {k}}}$ натуральное число для любых натуральных чисел п и k. Есть много других комбинаторных интерпретаций биномиальных коэффициентов (задачи подсчета, для которых ответ дается выражением биномиальных коэффициентов), например, количество слов, образованных из п биты (цифры 0 или 1), сумма которых равна k дан кем-то ${displaystyle {binom {n} {k}}}$, а количество способов записи ${displaystyle k = a_ {1} + a_ {2} + cdots + a_ {n}}$ где каждый а_я неотрицательное целое число ${displaystyle {binom {n + k-1} {n-1}}}$. Большинство из этих интерпретаций, как легко заметить, эквивалентны подсчету k-комбинации.

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

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

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

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

${displaystyle {inom {n} {k}} = {inom {n-1} {k-1}} + {inom {n-1} {k}} quad {ext {для всех целых чисел}} n, k: 1leq kleq n-1,}$

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

${displaystyle {inom {n} {0}} = {inom {n} {n}} = 1quad {ext {для всех целых чисел}} ngeq 0,}$

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

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

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

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

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

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

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

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

${displaystyle {inom {n} {k}} = {frac {n!} {k!, (n-k)!}} quad {ext {for}} 0leq kleq n,}$

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

${displaystyle {inom {n} {k}} = {inom {n} {n-k}} quad {ext {for}} 0leq kleq n,}$

(1)

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

${displaystyle {inom {n} {k}} = {egin {case} n ^ {underline {k}} / k! & {ext {if}} kleq {frac {n} {2}} n ^ {underline {nk}} / (nk)! & {ext {if}} k> {frac {n} {2}} end {cases}}.}$

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

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

${displaystyle {inom {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 {ext {for}} kin mathbb {N} {ext {и произвольно}} alpha.}$

С этим определением можно получить обобщение биномиальной формулы (с одной из переменных, установленной в 1), что оправдывает все еще вызов ${displaystyle {binom {alpha} {k}}}$ биномиальные коэффициенты:

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

(2)

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

${displaystyle (1 + X) ^ {alpha} (1 + X) ^ {eta} = (1 + X) ^ {alpha + eta} quad {ext {and}} quad ((1 + X) ^ {альфа} ) ^ {эта} = (1 + X) ^ {альфа эта}.}$

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

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

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

${Displaystyle {n выбрать k} + {n выбрать k + 1} = {n + 1 выбрать k + 1},}$

(3)

что может быть использовано для доказательства математическая индукция который ${displaystyle {binom {n} {k}}}$ натуральное число для всех целых п ≥ 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

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

${displaystyle (x + y) ^ {5} = {underline {1}} x ^ {5} + {underline {5}} x ^ {4} y + {underline {10}} x ^ {3} y ^ { 2} + {подчеркивание {10}} x ^ {2} y ^ {3} + {подчеркивание {5}} xy ^ {4} + {подчеркивание {1}} y ^ {5}.}$

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

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

• Есть ${displaystyle {binom {n} {k}}}$ способы выбрать k элементы из набора п элементы. Видеть Комбинация.
• Есть ${displaystyle {binom {n + k-1} {k}}}$ способы выбрать k элементы из набора п элементы, если разрешены повторы. Видеть Multiset.
• Есть ${displaystyle {binom {n + k} {k}}}$ струны содержащий k те и п нули.
• Есть ${displaystyle {binom {n + 1} {k}}}$ струны, состоящие из k те и п нули такие, что нет двух смежных.^[4]
• В Каталонские числа находятся ${displaystyle {frac {1} {n + 1}} {binom {2n} {n}}.}$
• В биномиальное распределение в статистика является ${displaystyle {binom {n} {k}} p ^ {k} (1-p) ^ {n-k} !.}$

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

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

${displaystyle {inom {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 2cdot 1}};}$

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

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

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

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

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

В производная из ${displaystyle {binom {t} {k}}}$ можно рассчитать по логарифмическое дифференцирование:

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

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

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

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

(4)

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

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

Пример

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

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

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

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

${displaystyle {inom {n} {k}} = {frac {n} {k}} {inom {n-1} {k-1}}}$

(5)

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

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

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

${displaystyle {inom {n} {h}} {inom {n-h} {k}} = {inom {n} {k}} {inom {n-k} {h}}.}$

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

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

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

Формула

${displaystyle sum _ {k = 0} ^ {n} {inom {n} {k}} = 2 ^ {n}}$

(∗∗)

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

Формулы

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

(6)

и

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

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

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

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

(7)

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

${displaystyle sum _ {j = 0} ^ {m} {inom {m} {j}} ^ {2} = {inom {2m} {m}},}$

(8)

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

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

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

(9)

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

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

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

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

Позволять F(п) обозначают п-го Число Фибоначчи.Потом

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

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

Множественные суммы сумм

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

${displaystyle {inom {n} {t}} + {inom {n} {t + s}} + {inom {n} {t + 2s}} + ldots = {frac {1} {s}} sum _ { j = 0} ^ {s-1} влево (2cos {frac {pi j} {s}} ight) ^ {n} cos {frac {pi (n-2t) j} {s}}.}$

Для малых sу этих серий особенно красивые формы; Например,^[6]

${displaystyle {inom {n} {0}} + {inom {n} {3}} + {inom {n} {6}} + cdots = {frac {1} {3}} left (2 ^ {n}) + 2cos {frac {npi} {3}} ight)}$

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

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

${displaystyle {inom {n} {0}} + {inom {n} {4}} + {inom {n} {8}} + cdots = {frac {1} {2}} left (2 ^ {n- 1} + 2 ^ {frac {n} {2}} cos {frac {npi} {4}} ight)}$

${displaystyle {inom {n} {1}} + {inom {n} {5}} + {inom {n} {9}} + cdots = {frac {1} {2}} left (2 ^ {n- 1} + 2 ^ {frac {n} {2}} sin {frac {npi} {4}} ight)}$

${displaystyle {inom {n} {2}} + {inom {n} {6}} + {inom {n} {10}} + cdots = {frac {1} {2}} left (2 ^ {n- 1} -2 ^ {frac {n} {2}} cos {frac {npi} {4}} ight)}$

${displaystyle {inom {n} {3}} + {inom {n} {7}} + {inom {n} {11}} + cdots = {frac {1} {2}} left (2 ^ {n- 1} -2 ^ {frac {n} {2}} sin {frac {npi} {4}} ight)}$

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

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

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

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

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

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

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

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

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

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

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

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

(10)

куда ${displaystyle a_ {n}}$ коэффициент степени п в п(Икс).

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

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

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

В серии${displaystyle {frac {k-1} {k}} sum _ {j = 0} ^ {infty} {frac {1} {inom {j + x} {k}}} = {frac {1} {inom { x-1} {k-1}}}}$ сходится для k ≥ 2. Эта формула используется при анализе Проблема с немецким танком. Это следует из ${displaystyle {frac {k-1} {k}} sum _ {j = 0} ^ {M} {frac {1} {inom {j + x} {k}}} = {frac {1} {inom { x-1} {k-1}}} - {гидроразрыв {1} {inom {M + x} {k-1}}}}$что доказано индукция на M.

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

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

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

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

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

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

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

Личность (8) также имеет комбинаторное доказательство. В удостоверении написано

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

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

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

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

Если обозначить через F(я) последовательность Числа Фибоначчи, проиндексировано так, чтобы F(0) = F(1) = 1, то тождество

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

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

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

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

Личность Диксона является

${displaystyle sum _ {k = -a} ^ {a} (- 1) ^ {k} {2a выберите k + a} ^ {3} = {frac {(3a)!} {(a!) ^ {3 }}}}$

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

${displaystyle sum _ {k = -a} ^ {a} (- 1) ^ {k} {a + b выбрать a + k} {b + c выбрать b + k} {c + a выбрать c + k} = {гидроразрыв {(a + b + c)!} {a!, b!, c!}} ,,}$

куда а, б, и c неотрицательные целые числа.

Непрерывная идентичность

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

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

${displaystyle int _ {- pi} ^ {pi} sin ((2m-n) x) sin ^ {n} (x) dx = {egin {case} (- 1) ^ {m + (n + 1) / 2 } {frac {pi} {2 ^ {n-1}}} {inom {n} {m}}, & n {ext {odd}} 0, & {ext {else}} end {case}}}$

${displaystyle int _ {- pi} ^ {pi} cos ((2m-n) x) sin ^ {n} (x) dx = {egin {cases} (- 1) ^ {m + (n / 2)} { frac {pi} {2 ^ {n-1}}} {inom {n} {m}}, & n {ext {even}} 0, & {ext {else}} end {case}}}$

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

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

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

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

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

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

${displaystyle sum _ {n = k} ^ {infty} {n выбрать k} y ^ {n} = {frac {y ^ {k}} {(1-y) ^ {k + 1}}}.}$

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

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

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

${displaystyle sum _ {n = 0} ^ {infty} sum _ {k = 0} ^ {infty} {n + k выбрать k} x ^ {k} y ^ {n} = {frac {1} {1- xy}}.}$

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

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

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

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

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

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

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

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

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

${displaystyle {inom {n + k} {k}}}$ разделяет ${displaystyle {frac {{ext {lcm}} (n, n + 1, ldots, n + k)} {n}}}$.

${displaystyle {inom {n + k} {k}}}$ кратно ${displaystyle {frac {{ext {lcm}} (n, n + 1, ldots, n + k)} {ncdot {ext {lcm}} ({inom {k} {0}}, {inom {k} { 1}}, ldots, {inom {k} {k}})}}}$.

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

${displaystyle {inom {n} {1}}, {inom {n} {2}}, ldots, {inom {n} {n-1}}}$

делятся на п.

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

${displaystyle {inom {p} {k}} = {frac {pcdot (p-1) cdots (p-k + 1)} {kcdot (k-1) cdots 1}}}$ для всех 0 < k < п

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

${displaystyle {inom {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)!}} от эквивалента 0 {pmod {n}}}$

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

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

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

${displaystyle {frac {n ^ {k}} {k ^ {k}}} leq {n choose k} leq {frac {n ^ {k}} {k!}}$.

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

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

и каждый из этих ${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 {{ext {lcm}} (nk, ldots, n)} {(nk) cdot {ext {lcm}} ({inom {k} {0}}, ldots, {inom {k} {k }})}} leq {inom {n} {k}} leq {frac {{ext {lcm}} (nk, ldots, n)} {nk}}}$,

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

Обе п и k большой

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

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

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

В частности, когда ${displaystyle n}$ достаточно большой:

${displaystyle {2n choose n} sim {frac {2 ^ {2n}} {sqrt {pi n}}}}$и ${displaystyle {sqrt {n}} {2n выберите n} geq 2 ^ {2n-1}}$

и в целом для м ≥ 2 и п ≥ 1,^{[Почему? ]}

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

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

${displaystyle log _ {2} {n выбрать k} sim nH (k / n) = klog _ {2} (n / k) + (n-k) log _ {2} (n / (n-k))}$

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

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

${displaystyle {inom {n} {k}} sim {inom {n} {frac {n} {2}}} e ^ {- d ^ {2} / (2n)} sim {frac {2 ^ {n} } {sqrt {{гидроразрыв {1} {2}} npi}}} e ^ {- d ^ {2} / (2n)}}$

куда d = п − 2k.

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

Если п большой и k является о(п) (то есть, если k/п → 0), тогда

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

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

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

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

Более точные оценки даются

${displaystyle {frac {1} {sqrt {8nepsilon (1-epsilon)}}} cdot 2 ^ {H (epsilon) cdot n} leq sum _ {i = 0} ^ {k} {inom {n} {i} } leq 2 ^ {H (эпсилон) cdot n}.}$

который действителен для всех целых чисел ${displaystyle ngeq kgeq 1}$ с ${displaystyle epsilon doteq k / nleq 1/2}$.^[14]

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

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

${displaystyle (-1) ^ {k} {z select 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 select k} приблизительно {frac {(-1) ^ {k}} {Gamma (-z) k ^ {z + 1}}} qquad mathrm {и} qquad {z + k choose k} = { frac {k ^ {z}} {Gamma (z + 1)}} left (1+ {frac {z (z + 1)} {2k}} + {mathcal {O}} left (k ^ {- 2}) ight) ight)}$

в качестве ${displaystyle k o infty}$.

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

${displaystyle {z + k выбрать k} приблизительно {frac {e ^ {z (H_ {k} -gamma)}} {Gamma (z + 1)}}}$

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

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

${displaystyle {frac {z + k choose j} {k choose j}} o left (1- {frac {j} {k}} ight) ^ {- z} quad {ext {and}} quad {frac {j choose jk} {jz choose jk}} o left ({frac {j} {k}} ight) ^ {z}}$

верен, когда ${displaystyle k o infty}$ и ${displaystyle j / k o 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.}$

Хотя биномиальные коэффициенты представляют собой коэффициенты при (Икс+у)^п, полиномиальные коэффициенты представляют собой коэффициенты полинома

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

Дело р = 2 дает биномиальные коэффициенты:

${Displaystyle {n выбрать k_ {1}, k_ {2}} = {n выбрать k_ {1}, n-k_ {1}} = {n выбрать k_ {1}} = {n выбрать k_ {2}}. }$

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

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

${displaystyle {n выбрать k_ {1}, k_ {2}, ldots, k_ {r}} = {n-1 выбрать k_ {1} -1, k_ {2}, ldots, k_ {r}} + {n -1 выберите k_ {1}, k_ {2} -1, ldots, k_ {r}} + ldots + {n-1 выберите 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 _) {р}}}}$

куда ${displaystyle (sigma _ {i})}$ это перестановка из (1, 2, ..., р).

Серия Тейлор

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

${displaystyle {egin {align} {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 ji} {frac {s_ {k + ij, i}) } {(k + ij)!}} & = sum _ {i = 0} ^ {k} (z-z_ {0}) ^ {i} sum _ {j = i} ^ {k} z_ {0 } ^ {ji} {j выберите i} {frac {s_ {k, j}} {k!}}. конец {выровнено}}}$

Биномиальный коэффициент с п = 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 _ {kgeq 0} {inom {1/2} {k}} x ^ {k}.}$

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

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

${displaystyle {z select m} {z select n} = sum _ {k = 0} ^ {m} {m + n-k choose k, m-k, n-k} {z choose m + n-k},}$

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

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

${displaystyle prod _ {k = 0} ^ {n} {inom {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 {ni} { zi}}, 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) = α ж(z).

В радиус схождения этой серии равно 1. Альтернативное выражение

${displaystyle {frac {1} {(1-z) ^ {alpha +1}}} = sum _ {n = 0} ^ {infty} {n + alpha выберите n} z ^ {n}}$

где личность

${displaystyle {n выбрать k} = (- 1) ^ {k} {k-n-1 выбрать k}}$

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

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

Биномиальные коэффициенты подсчитывают подмножества заданного размера из заданного набора. Связанная с этим комбинаторная задача - подсчитать мультимножества заданного размера с элементами, взятыми из заданного набора, то есть для подсчета количества способов выбрать определенное количество элементов из заданного набора с возможностью повторного выбора одного и того же элемента. Полученные числа называются коэффициенты мультимножества;^[15] количество способов "множественного выбора" (т. е. выбора с заменой) k предметы из п набор элементов обозначен ${displaystyle left (!! {inom {n} {k}} !! ight)}$.

Чтобы избежать двусмысленности и путаницы с п 'основной смысл в этой статье,
позволять ж = п = р + (k - 1) и р = ж – (k – 1).

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

${displaystyle {inom {f} {k}} = left (!! {inom {r} {k}} !! ight) = {inom {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} {ig |}} r ^ {(k)} =, r ^ {overline {k}} =, rcdot (r + 1) cdot (r + 2) cdot (r + 3) cdots (г + к-1)}$;

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

${displaystyle 17cdot 18cdot 19cdot 20cdot 21 = (21) _ {5} = 21 ^ {подчеркивание {5}} = 17 ^ {overline {5}} = 17 ^ {(5)}}$.

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

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

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

${displaystyle left (!! {inom {r} {k}} !! ight) = {frac {r ^ {(k)}} {k!}} = {frac {rcdot (r + 1) cdot (r + 2) cdots (r + k-1)} {1cdot 2cdot 3cdot 4cdot 5cdots k}}}$.

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

Для любого п,

${displaystyle {egin {align} {inom {-n} {k}} & = {frac {-ncdot - (n + 1) dots - (n + k-2) cdot - (n + k-1)} { k!}} & = (- 1) ^ {k}; {frac {ncdot (n + 1) cdot (n + 2) cdots (n + k-1)} {k!}} & = (- 1) ^ {k} {inom {n + k-1} {k}} & = (- 1) ^ {k} left (!! {inom {n} {k}} !! ight); конец {выровнено}}}$

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

Например, если п = −4 и k = 7, тогда р = 4 и ж = 10:

${displaystyle {egin {align} {inom {-4} {7}} & = {frac {-10cdot -9cdot -8cdot -7cdot -6cdot -5cdot -4} {1cdot 2cdot 3cdot 4cdot 5cdot 6cdot 7}} & = (-1) ^ {7}; {frac {4cdot 5cdot 6cdot 7cdot 8cdot 9cdot 10} {1cdot 2cdot 3cdot 4cdot 5cdot 6cdot 7}} & = left (!! {inom {-7} {7}} !! ight ) left (!! {inom {4} {7}} !! ight) = {inom {-1} {7}} {inom {10} {7}}. конец {выровнено}}}$

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

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

${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 (ypi)} {sin (xpi)}} {- y-1 choose -x-1} = {frac {sin ((xy) pi)} {sin (xpi) )}} {yx-1 choose y};}$

более того,

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

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

• в октанте ${displaystyle 0leq yleq x}$ это плавно интерполированная форма обычного бинома с гребнем («гребень Паскаля»).
• в октанте ${displaystyle 0leq xleq y}$ и в квадранте ${displaystyle xgeq 0, yleq 0}$ функция близка к нулю.
• в квадранте ${displaystyle xleq 0, ygeq 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 eta} = | {Bsubseteq A: | B | = eta} |}$

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

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

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

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

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

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

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

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

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

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

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

${displaystyle {n выбрать k + 1} = left [(n-k) {n выбрать k} ight] div (k + 1)}$

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

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

${displaystyle {n select k + 1} = left [extstyle {n choose k} div (k + 1) ight] (nk) + {left [{n choose k} mathrm {mod} (k + 1) ight] ( nk) над (k + 1)}}$

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

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

${displaystyle {n choose k} = {frac {n!} {k!, (nk)!}} = {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)),}$

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

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

Примечания

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

внешняя ссылка

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

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