Биномен коефициент

Биномен коефициент на естествените числа k и n е броят на всички възможни k-елементни подмножества на дадено n-елементно множество. Биномният коефициент е естествено число и се дефинира като:

за 0 ≤ k ≤ n

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

и за k > n, k < 0

${n \choose k}=0.$

Символът ${n \choose k}$ се чете „n над k“.

Също така за 1 ≤ k ≤ n важи следното:

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

където с m! е означен факториелът на m.

Биномните коефициенти получават името си от развитието на бинома

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

Формули, свързани с биномните коефициенти

Тези формули се използват често в задачи от комбинаториката и теорията на вероятностите.

${n \choose k}={n \choose n-k}.$

Това следва директно от дефиницията. Други формули са

$\sum _{k=0}^{n}{n \choose k}=2^{n},$

$\sum _{k=1}^{n}{k}{n \choose k}={n}2^{n-1}.$

Следва формулата на Вандермонд

$\sum _{j}{m \choose j}{{n-m} \choose {k-j}}={n \choose k}$

Сродни са формулите

$\sum _{m}{m \choose j}{n-m \choose k-j}={n+1 \choose k+1},$

$\sum _{j=0}^{m}{m \choose j}^{2}={{2m} \choose m}.$

Като означим числата на Фибоначи с F(n + 1), получаваме формула за диагоналите на триъгълника на Паскал

$\sum _{k=0}^{n}{{n-k} \choose k}=\mathrm {F} (n+1).$

Това може да се докаже с индукция.

Триъгълник на Паскал

Триъгълникът на Паскал съдържа биномните коефициенти. Носи името на Блез Паскал, който го открива през XVII век. Намерен е и в китайски писмени източници от XI век.

Всеки елемент – в n-ти ред на k-та позиция – в триъгълника притежава аритметично и комбинаторно тълкуване и в зависимост от това се означава с ${n \choose k}$ – чете се (биномен коефициент) n над k, или $C_{k}^{n}$ – комбинация (без повторение) на k от n елемента.

Всяко число от вътрешността на триъгълника е сума от двете числа, непосредствено разположени над него. Математически това свойство се записва по следния начин:

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

и се нарича правило на Паскал.

Тази формула лесно се обобщава за пирамида в тримерното пространство, както и за други n-мерни обобщения на триъгълника.

Коефициенти до десети ред

На долната фигура са показани елементите на триъгълника до n = 10:

Триъгълник на Паскал

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

Дефиницията на биномните коефициенти може да бъде разширена за отрицателни числа по следния начин:

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

за r ≥ 0, n ≥ 0,

${-n \choose -r}={\begin{cases}0\quad {\mbox{if}}r<n,\\{-n \choose r-n}\quad {\mbox{if }}r\geq n,\end{cases}}n>0,r>0$

и

${n \choose r}=0$

ако n ≥ 0, r < 0 или r > n.

Обобщение за реален и комплексен аргумент

Биномният коефициент ${z \choose k}$ може да бъде дефиниран за всяко комплексно число z и за всяко естествено число k по следния начин:

${z \choose k}=\prod _{n=1}^{k}{z-k+n \over n}={\frac {z(z-1)(z-2)\cdots (z-k+1)}{k!}}.$

Това обобщение е известно като обобщен биномен коефициент и се използва при формулирането на биномната теорема.

Източници

Binomial coefficient – статия в Уикипедия на английски език [16 февруари 2008].

Вижте също

Триъгълник на Паскал

Външни препратки

• Онлайн изчисляване – Биномен коефициент