Binomni koeficijent

U matematici, a posebno u kombinatorici, binomni koeficijent prirodnog broja n i celog broja k definisan je kao prirodni broj:

i

ako je k<0 ili k>n.

(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 Cnk i čita kao »n nad k«. Prema Nikolasu Higamu, notaciju je uveo u upotrebu Albert fon Etinghauzen 1826, iako se za ove brojeve znalo vekovima pre toga (pogledati: Paskalov trougao).

Primer:

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

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

Paskalov trougao

uredi

Važna rekurzivna relacija

 

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 = 1x5 + 5 x4y + 10 x3y2 + 10 x2y3 + 5 x y4 + 1y5.

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

uredi

Binomni koeficijenti su od velike važnosti u kombinatorici jer nude gotove formule za česte probleme prebrojavanja:

  • Svaki skup sa n poseduje tačno   različitih podskupova koji imaju k elemenata
  • Broj binarnih brojeva dužine n koje sadrže k jedinica i n − k nula je  .
  • Broj binarnih brojeva koji sadrže k jedinica i n nula tako da nikoje dve nisu susedne je  .
  • Broj različitih sekvenci od n prirodnih brojeva čiji je ukupni zbir k je  ; 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

uredi

Sledeće formule mogu biti korisne:

 

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

 

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

 

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

 

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).

 

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

 

Ovde, F(n + 1) predstavlja Fibonačijeve brojeve.

 

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

Generalizacija sa kompleksnim argumentom

uredi

Binomni koeficijent   može se definisati za bilo koji kompleksni broj z i bilo koji prirodni broj k:

 

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   je polinom po z stepena k sa racionalnim koeficijentima. Svaki polimom p(z) stepena d može se napisati u formi

 

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

Granice binomnih koeficijenata

uredi

Za binomni koeficijent C(n, k) važe sledeće granice:

  •  
  •  
  •