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 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 ${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)ⁿ (odatle i naziv):

$(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}y^{n-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:

ред 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

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 konstatovati:

(x + y)⁵ = 1x⁵ + 5 x⁴y + 10 x³y² + 10 x²y³ + 5 x y⁴ + 1y⁵.

Godine 1303. 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 − 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)ⁿ = (y + x)ⁿ, 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)=n2^{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)ⁿ (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 + 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 polinom 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}\leq {\frac {n^{k}}{k!}}$
• ${n \choose k}\leq \left({\frac {n\cdot e}{k}}\right)^{k}$
• ${n \choose k}\geq \left({\frac {n}{k}}\right)^{k}$

Reference

• Arthur T. Benjamin; Quinn, Jennifer (2003). Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America.
• Bryant, Victor (1993). Aspects of combinatorics. Cambridge University Press. ISBN 978-0-521-41974-1. 
• Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. Arhivirano iz originala 18. 11. 2007. g. Pristupljeno 15. 12. 2011. 
• Fowler, David (1996). „The Binomial Coefficient Function”. The American Mathematical Monthly. Mathematical Association of America. 103 (1): 1—17. JSTOR 2975209. doi:10.2307/2975209. 
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics (Second izd.). Addison-Wesley. str. 153–256. ISBN 978-0-201-55802-9. 
• Higham, Nicholas J. (1998). Handbook of writing for the mathematical sciences. Society for Industrial and Applied Mathematics. str. 25. ISBN 978-0-89871-420-3. 
• Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (Third izd.). Addison-Wesley. str. 52—74. ISBN 978-0-201-89683-1. 
• Singmaster, David (1974). „Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients”. J. London Math. Soc. (2). 8 (3): 555—560. doi:10.1112/jlms/s2-8.3.555. 
• Shilov, G. E. (1977). Linear algebra. Dover Publications. ISBN 9780486635187.