Binomni koeficijent

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

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

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

Primer:

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

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

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

Važna rekurzivna relacija

${\displaystyle 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)⁵ = 1x⁵ + 5 x⁴y + 10 x³y² + 10 x²y³ + 5 x y⁴ + 1y⁵.

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.

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

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

Sledeće formule mogu biti korisne:

${\displaystyle C(n,k)=C(n,n-k)\qquad \qquad (4)\,}$

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

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

${\displaystyle \sum _{k=1}^{n}k\mathrm {C} (n,k)=n2^{n-1}\qquad (6)}$

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

${\displaystyle \sum _{j=0}^{k}\mathrm {C} (m,j)\mathrm {C} (n,k-j)=\mathrm {C} (m+n,k)\qquad (7)}$

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

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

${\displaystyle \sum _{k=0}^{n}\mathrm {C} (n-k,k)=\mathrm {F} (n+1)\qquad (9)}$

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

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

Binomni koeficijent ${\displaystyle {z \choose k}}$ može se definisati za bilo koji kompleksni broj z i bilo koji prirodni broj k:

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

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

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

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