Binomni koeficijent

U matematici, a posebno u kombinatorici, **binomni koeficijent** prirodnog broja *n* i celog broja *k* definisan je kao prirodni broj:
: {n \choose k} = \frac{n!}{k!(n-k)!}
=\prod_{i=1}^k{n+1-i\over i},
\quad n\geq k\geq 0 \qquad \mbox{(1)} 
i
: {n \choose k} = 0 ako je kn.

(Za prirodni broj *m*, *m!* označava faktorijel broja *m*.)

Binomni koeficijent od *n* i *k* se takođe piše i kao C(*n*, *k*) ili C*n**k* i čita kao »*n* nad *k*«. Prema Nikolasu Higamu, notaciju  {n \choose k}  je uveo u upotrebu Albert fon Etinghauzen 1826, iako se za ove brojeve znalo vekovima pre toga (pogledati: Paskalov trougao).

Primer:

: {7 \choose 3} = \frac{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1} = 35.

Binomni koeficijenti su koeficijenti u razvoju binoma (*x* + *y*)*n* (odatle i naziv):

: (x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k} y^k \qquad (2) 

Ovo je generalizovano binomnom teoremom koja dozvoljava da *n* bude negativan ili realan broj.

## Paskalov trougao
Važna rekurzivna relacija
:C(n,k) + C(n,k+1) = C(n+1,k+1) \qquad (3) 
sledi direktno iz definicije binomnog koeficijenta. Ovom relacijom, i matematičkom indukcijom se može dokazati da je C(*n*, *k*) prirodni broj, za svako *n* i *k* (što nije najočiglednije odmah iz definicije).

Na taj način se konstruiše Paskalov trougao:
red 0 1
red 1 1 1
red 2 1 2 1
red 3 1 3 3 1
red 4 1 4 6 4 1
red 5 1 5 10 10 5 1
red 6 1 6 15 20 15 6 1
red 7 1 7 21 35 35 21 7 1
red 8 1 8 28 56 70 56 28 8 1
n.-ti red sadrži brojeve C(*n*, *k*) za *k* = 0,...,*n*. Paskalov trougao se konstruiše tako da se kreće od 1, a novi broj se dobija sabiranjem suseda iz prethodnog reda. Ovako se brzo mogu izračunati binomni koeficijenti bez potrebe za množenjem i deljenjem. Npr. samo gledajući 5. red, možemo konstantovati:
:(*x* + *y*)5 = **1***x*5 + **5** *x*4*y* + **10** *x*3*y*2 + **10** *x*2*y*3 + **5** *x* *y*4 + **1***y*5.

1303. godine u delu *Dragoceno ogledalo četiri elementa (Precious Mirror of the Four Elements)* Cu Šiđe (Zhu Shijie) pominje ovaj trougao za rešavanje binomnih koeficijenata, što ukazuje da je ovaj metod bio poznat kineskim matematičarima pet vekova pre Blez Paskala.

## Kombinatorika i statistika
Binomni koeficijenti su od velike važnosti u kombinatorici jer nude gotove formule za česte probleme prebrojavanja:
* Svaki skup sa *n* poseduje tačno {n\choose k} različitih podskupova koji imaju *k* elemenata
* Broj binarnih brojeva dužine *n* koje sadrže *k* jedinica i *n*&nbsp;−&nbsp;*k* nula je {n\choose k}.
* Broj binarnih brojeva koji sadrže *k* jedinica i *n* nula tako da nikoje dve nisu susedne je {n+1\choose k}.
* Broj različitih sekvenci od *n* prirodnih brojeva čiji je ukupni zbir *k* je {n+k-1\choose k}; ovo je takođe broj različitih načina da se iz skupa sa *n* elemenata izabere *k* elemenata ukoliko je dozvoljeno ponavljanje.

Binomni koeficijenti se pojavljuju i u formuli za binomnu raspodelu u statistici, kao i u formuli za Bezijerovu krivu.

## Formule sa binomnim koeficijentima
Sledeće formule mogu biti korisne:

:C(n,k)=C(n, n-k)\qquad\qquad(4)\,

Ovo sledi iz razvoja (2) koristeći (*x* + *y*)*n* = (*y* + *x*)*n*, i ogleda se u numeričkoj simetričnosti Paskalovog trougla.

: \sum_{k=0}^{n} \mathrm{C}(n,k) = 2^n \qquad (5) 

Iz razvoja (2) stavljajući *x* = *y* = 1. Vidi se i iz Paskalovog trougla da je suma svih članova jednog reda jednaka stepenu dvojke.

: \sum_{k=1}^{n} k \mathrm{C}(n,k) = n 2^{n-1} \qquad (6) 

Iz razvoja (2) posle diferenciranja i zamenjujući *x* = *y* = 1.

: \sum_{j=0}^{k} \mathrm{C}(m,j) \mathrm{C}(n,k-j) = \mathrm{C}(m+n,k) \qquad (7) 

Razvijajući (*x* + *y*)*n* (*x* + *y*)*m* = (*x* + *y*)*m*+*n* iz (2) (C(*n*, *k*) je definisano kao 0 za *k* > *n*). Ova jednačina generalizuje (3).

: \sum_{k=0}^{n} \mathrm{C}(n,k)^2 = \mathrm{C}(2n,n) \qquad (8)

Iz razvoja (7) stavljajući *m* = *k* = *n* i koristeći jednačinu (4).

: \sum_{k=0}^{n} \mathrm{C}(n-k,k) = \mathrm{F}(n+1) \qquad (9) 

Ovde, *F*(*n*&nbsp;+&nbsp;1) predstavlja Fibonačijeve brojeve.

: \sum_{j=k}^{n} \mathrm{C}(j,k) = \mathrm{C}(n+1,k+1) \qquad (10) 

Ova jednačina može biti dokazana indukcijom po *n* koristeći (3).

## Generalizacija sa kompleksnim argumentom
Binomni koeficijent {z\choose k} može se definisati za bilo koji kompleksni broj *z* i bilo koji prirodni broj *k*:
:{z\choose k} = {1 \over k!}\prod_{n=0}^{k-1}(z-n)= \frac{z(z-1)(z-2)\cdots (z-k+1)}{k!} \qquad (11) 

Ova generalizacija je poznata kao **uopšteni binomni koeficijent** i koristi se pri formulaciji binomne teoreme, a zadovoljava i svojstva (3) i (7).

Za konstantno *k*, izraz {z\choose k} je polinom po *z* stepena *k* sa racionalnim koeficijentima. Svaki polimom *p*(*z*) stepena *d* može se napisati u formi
: p(z) = \sum_{k=0}^{d} a_k {z\choose k} 

sa odgovarajućim koeficijentima *a**k*. Ovo je naročito važno u teoriji diferencijalnih jednačina i može se posmatrati kao diskretna analogija Tejlorove teoreme.

## Granice binomnih koeficijenata
Za binomni koeficijent C(*n*, *k*) važe sledeće granice:
*  {n \choose k} \le \frac{n^k}{k!} 
*  {n \choose k} \le \left(\frac{n\cdot e}{k}\right)^k 
* {n\choose k}\ge \left(\frac{n}{k}\right)^k