Coeficient binomial

En matemàtiques, un coeficient binomial és qualsevol dels coeficients dels termes del polinomi que resulta de desenvolupar el binomi de Newton, és a dir del desenvolupament de $(x y)^{n}$. El coeficient del terme $k$-èsim d'aquest polinomi, quan $n$ és el grau del polinomi, s'escriu ${n \choose k}$, que es llegeix com "$n$ sobre $k$". Per tant

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

(1)

El seu valor és

${n \choose k}={\frac {n\cdot (n-1)\cdots (n-k 1)}{k\cdot (k-1)\cdots 1}}={\frac {n!}{k!(n-k)!}}\quad {\mbox{per}}\ n\geq k\geq 0,$

on $n!$ significa el factorial de $n$. També podem escriure $(1 y)^{n}=\sum _{k=0}^{n}{n \choose k}y^{k}.$

Els coeficients binomials poden ordenar-se formant el Triangle de Pascal.

Si es disposen aquests coeficients binomials en files centrades per successius valors de $n$, començant per $n=0$ i de manera que en aquestes files els valors de $k$ variïn entre $0$ i $n$, s'obté l'anomenat triangle de Pascal (o triangle de Tartaglia, o triangle aritmètic), que pot generar-se recursivament de manera molt senzilla, ja que cada coeficient és la suma dels dos que te a sobre.

Interpretació combinatòria

Des del punt de vista combinatori el coeficient binomial es pot entendre com el nombre de formes en què es poden escollir $k$ objectes entre un conjunt de $n$ sense tenir en compte l'ordre. Per veure-ho només cal fixar-se que a l'expressió

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

el numerador dona el nombre de possibilitats d'escollir $k$ objectes entre un total de $n$. El primer es pot escollir de $n$ formes, en tenir $n$ objectes per agafar. Un cop escollit el primer, només en queden $n-1$ i per tant el segon es pot escollir de $n-1$ maneres. Com que per cada possibilitat d'escollir el primer hi ha $n-1$ formes d'escollir el segon, en total per als dos primers n'hi ha $n\cdot (n-1)$ i així successivament fins a $k$. Però en escollir les formes d'aquesta manera s'han considerat diferents les col·leccions triades en diferent ordre. Com que per cada conjunt de $k$ objectes hi ha $k!$ formes d'ordenar-los, cal dividir aquest numerador entre $k!$ I així s'obté la quantitat de conjunts diferents, sense importar l'ordre en què s'han triat.

Per aquesta raó el nombre ${n \choose k}$, que nosaltres llegim com "$n$ sobre $k$", es llegeix en anglès com "$n$ choose $k$".

Exemple

${7 \choose 3}={\frac {7!}{3!(7-3)!}}={\frac {7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{(3\cdot 2\cdot 1)(4\cdot 3\cdot 2\cdot 1)}}={\frac {7\cdot 6\cdot 5}{3\cdot 2\cdot 1}}=35.$

El mateix valor s'obté mirant a la fila $n=7$ en el lloc $k=3$ al triangle de Pascal.

Historia i notació

Andreas von Ettingshausen va introduir la notació ${\tbinom {n}{k}}$ el 1826, encara que aquests nombres ja eren coneguts des de centenars d'anys abans (veure Triangle de Pascal). La primera discussió detallada dels coeficients binomials de la que es té notícia és del segle deu i és el comentari, per Halayudha, sobre un antic text Sànscrit, el Chandaḥśāstra, de Pingala. Al voltant del 1150, el matemàtic indi Bhaskaracharya va donar una exposició dels coeficients binomials en el seu llibre Līlāvatī.

Notacions alternatives també utilitzades poden ser C(n, k), _nC_k, ⁿC_k, C^k_n, Cⁿ_k, i C_n,k. En totes elles la lletra C prové de combinacions o choices (eleccions). Diverses calculadores electròniques utilitzen variants de les notacions basades en la C, perquè així poden representar-se en una única línia de text. En aquesta forma, els coeficients binomials es comparen fàcilment amb altres nombres combinatoris com les k-permutacions de n elements, P(n,k). Els coeficients binomils apareixen en moltes àrees de les matemàtiques, especialment en combinatòria.

La fórmula multiplicativa i les generalitzacions dels coeficients binomials

Una forma prou eficient per a calcular el valor de ${\tbinom {n}{k}}$ sense usar ni la fórmula recursiva del Triangle de Pascal ni els nombres factorials és l'anomenada formula multiplicativa:

${\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-(k-1))}{k(k-1)(k-2)\cdots 1}}=\prod _{i=1}^{k}{\frac {n 1-i}{i}},$

que es recorda fàcilment perquè hi ha k factors al numerador i k factors al denominador. Però s'ha de recordar que el producte de k=0 factors s'entén que dona 1. Aquesta forma permet que la definició dels coeficients binomials s'estengui substituint n per un nombre arbitrari α (també negatiu, real o complex):

${\binom {\alpha }{k}}={\frac {\alpha (\alpha -1)(\alpha -2)\cdots (\alpha -k 1)}{k(k-1)(k-2)\cdots 1}}.$

Amb aquesta definició val la generalització següent de la fórmula del binomi (amb una de les variables amb valor 1), que dona encara més raons perquè els nombres ${\tbinom {\alpha }{k}}$ siguin anomenats coeficients binomials:

$(1 X)^{\alpha }=\sum _{k=0}^{\infty }{\alpha \choose k}X^{k}.$

(2)

Aquesta fórmula és vàlida per a tots els nombres complexos α i X amb |X| < 1. Si α és un sencer no negatiu n, aleshores tots els termes amb k > n són zero, la sèrie infinita esdevé una suma finita, i es recupera la fórmula binomial.

La regla de Pascal és la important relació de recurrència

${\alpha \choose k} {\alpha \choose k 1}={\alpha 1 \choose k 1},$

(3)

que pot ser usada, per exemple, per demostrar, usant inducció matemàtica, que ${\tbinom {n}{k}}$ és un nombre natural per tot n i tot k, un fet que no és immediatament obvi a partir de la fórmula (1). També és molt important la identitat de simetria

$\quad {n \choose k}={n \choose n-k}$,

que és vàlida per a qualssevol sencers no negatius $n$ i $k$ amb $n\geq k$.

Combinatòria i estadística

Els coeficients binomials son importants en combinatòria, perquè donen lloc a formes breus d'expressar el resultats de problemes freqüents de comptatge (veure Combinatòria):

• Hi ha ${\tbinom {n}{k}}$ maneres d'escollir k elements d'un conjunt de n elements.
• Hi ha ${\tbinom {n k-1}{k}}$ maneres d'escollir k elements d'un conjunt de n elements si s'admeten repeticions (veure Multiconjunt).
• Hi ha ${\tbinom {n k}{k}}$ cadenes de caràcters que continguin k uns i n zeros (veure Cadena (informàtica)).
• Hi ha ${\tbinom {n 1}{k}}$ cadenes de caràcters que consisteixin en k uns i n zeros de manera que no hi hagi dos uns adjacents.
• Els nombres de Catalan son ${\tfrac {1}{n 1}}{\tbinom {2n}{n}}.$
• La distribució binomial en estadística és ${\tbinom {n}{k}}p^{k}(1-p)^{n-k}\!.$

Els coeficients binomials com a polinomis

Per a cada índex enter no negatiu k, l'expressió $\scriptstyle {\binom {t}{k}}$ pot ser simplificada i vista com un polinomi en la variable t de grau k i amb coeficients racionals:

${\binom {t}{k}}={\frac {t(t-1)(t-2)\cdots (t-k 1)}{k(k-1)(k-2)\cdots 2\cdot 1}}.$

Per a cada k, el polinomi ${\tbinom {t}{k}}$ pot ser caracteritzat com l'únic polinomi p(t) de grau k, que satisfà p(0) = p(1) = ... = p(k − 1) = 0 i p(k) = 1. Els seus coeficients poden expressar-se en termes dels nombres de Strirling de primera classe:

${\binom {t}{k}}=\sum _{i=0}^{k}\left[{k \atop i}\right]{\frac {t^{i}}{k!}}.$

La derivada de ${\tbinom {t}{k}}$ pot ser calculada usant la derivada logarítmica (veure regles de derivació):

${\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}={\binom {t}{k}}\sum _{i=0}^{k-1}{\frac {1}{t-i}}\,.$

Qualsevol polinomi q(t) de grau menor o igual que d pot expressar-se de manera única com una combinació lineal $\sum _{k=0}^{d}a_{k}{\binom {t}{k}}$ de polinomis que son coeficients binomials. El coeficient a_k és precisament la k-èssima diferència de la successió q(0), q(1), …, q(k). Explícitament,

$a_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}p(i).$

(4)

Qualsevol polinomi ${\tbinom {t}{k}}$ és a valors sencers: pren valors sencers sobre tots els valors sencers de la variables $t$.

(Una manera de demostrar-ho és per inducció sobre k, usant la regla de Pascal). Per tant, tota combinació lineal de polinomis ${\tbinom {t}{k}}$ és també un polinomi a valors sencers. Recíprocament, (4) mostra que tot polinomi a valors sencers és una combinació lineal d'aquests polinomis ${\tbinom {t}{k}}$.

Més generalment, per a qualsevol subanell R d'un cos K de característica 0, un polinomi de K[t] pren valors a R sobre tots els sencers si i sols si és una combinació lineal a coeficients a R de polinomis que siguin coeficients binomials.

Per exemple, el polinomi a valors sencers 3t(3t  1)/2 pot ser reescrit com $9{\tbinom {t}{2}} 6{\tbinom {t}{1}} 0{\tbinom {t}{0}}.$

Identitats que involucren coeficients binomials

- La fórmula factorial facilita relacionar coeficients binomials propers. Per exemple, si k és un enter positiu i n és arbitrari, aleshores

${\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}.$

- I, amb una mica més de feina,

${\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.$

- També la identitat següent pot ser útil:

${\binom {n}{h}}{\binom {n-h}{k}}={\binom {n}{k}}{\binom {n-k}{h}}.$

- Mantenint n constant, tenim la següent recurrència:

${\binom {n}{k}}={\frac {n 1-k}{k}}{\binom {n}{k-1}}.$

- La fórmula

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

s'obté a partir de (1) posant x = 1 i y = 1.

- Les fórmules

$\sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}$

i

$\sum _{k=0}^{n}k^{2}{\binom {n}{k}}=(n n^{2})2^{n-2}$

es dedueixen de (2) derivant respecte de X (una i dues vegades, respectivament) i després substituint X = 1.

- La identitat anomenada de Chu-Vandermonde, que val per a qualssevol valors complexos $\alpha$ i $\beta$ i qualsevol sencer no negatiu k, és

$\sum _{j=0}^{k}{\binom {\alpha }{j}}{\binom {\beta -\alpha }{k-j}}={\binom {\beta }{k}}$

i pot ser provada examinant el coeficient de $x^{k}$ a l'expansió de (1 x) (1 x)^{n − m} = (1 x)ⁿ usant l'equació (2).

- Si F(n) denota el n-èssim nombre de Fibonacci, aleshores tenim la igualtat

$\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n-k}{k}}=F(n 1),$

on $\lfloor x\rfloor$ significa el més gran sencer que és menor o igual que $x$. Aquesta identitat pot ser provada per inducció usant (3).

- La relació entre els coeficients binomials i certes integrals trigonomètriques dona lloc a les igualtats següents, per $\textstyle n,k-1\in \mathbb {N} ,\ k\leq n$ :

${\binom {n}{k}}={\frac {2^{n-1}}{\pi }}\int _{-\pi }^{\pi }\cos((2k-n)x)\cos ^{n}x\ dx$,

${\binom {n}{k}}=(-1)^{k (n 1)/2}{\frac {2^{n-1}}{\pi }}\int _{-\pi }^{\pi }\sin((2k-n)x)\sin ^{n}x\ dx$, si $n$ és senar (quan $n$ és parell la integral dona zero),

${\binom {n}{k}}=(-1)^{k (n/2)}{\frac {2^{n-1}}{\pi }}\int _{-\pi }^{\pi }\cos((2k-n)x)\sin ^{n}x\ dx$, si $n$ és parell (quan $n$ és senar la integral dona zero).

Poden demostrar-se usant la fórmula d'Euler per a convertir les funcions trigonomètriques en exponencials complexes, expandint usant del binomi de Newton i integrant terme a terme.

Bibliografia

• Ash, Robert B. Information Theory. Dover Publications, Inc., 1990. ISBN 0-486-66521-6. 
• Benjamin, Arthur T.; Quinn, Jennifer (2003). Proofs that Really Count: The Art of Combinatorial Proof Arxivat 2011-06-05 a Wayback Machine., Mathematical Association of America.
• Bryant, Victor. Aspects of combinatorics. Cambridge University Press, 1993. ISBN 0-521-41974-3. 
• Flum, Jörg; Grohe, Martin. Parameterized Complexity Theory. Springer, 2006. ISBN 978-3-540-29952-3.  Arxivat 2007-11-18 a Wayback Machine.
• Fowler, David «The Binomial Coefficient Function». The American Mathematical Monthly. Mathematical Association of America, 103, 1, 1-1996, pàg. 1-17. DOI: 10.2307/2975209. JSTOR: 2975209.
• Goetgheluck, P. «Computing Binomial Coefficients». American Math. Monthly, 94, 1987, pàg. 360–365. DOI: 10.2307/2323099.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren. Concrete Mathematics. 2a edició. Addison-Wesley, 1994, p. 153–256. ISBN 0-201-55802-5. 
• Gradshteyn, I. S.; Ryzhik, I. M.. Table of Integrals, Series, and Products. 8th. Academic Press, 2014. ISBN 978-0-12-384933-5. 
• Grinshpan, A. Z. «Weighted inequalities and negative binomials». Advances in Applied Mathematics, 45, 4, 2010, p. 564–606. DOI: 10.1016/j.aam.2010.04.004.
• Higham, Nicholas J. Handbook of writing for the mathematical sciences. SIAM, 1998, p. 25. ISBN 0-89871-420-6. 
• Knuth, Donald E. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Third. Addison-Wesley, 1997, p. 52–74. ISBN 0-201-89683-4. 
• Mateu, R.; Torras, M. (coords.). Diccionari de matemàtiques i estadística (en català). Universitat Politècnica de Catalunya, Enciclopèdia Catalana, 2002. ISBN 8441227926. 
• Singmaster, David «Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients». Journal of the London Mathematical Society, 8, 3, 1974, pàg. 555–560. DOI: 10.1112/jlms/s2-8.3.555.
• Shilov, G. E.. Linear algebra. Dover Publications, 1977. ISBN 978-0-486-63518-7. 

Vegeu també

• Monomi
• Triangle de Tartaglia
• Binomi de Newton

Enllaços externs

• Andrew Granville «Arithmetic Properties of Binomial Coefficients I. Binomial coefficients modulo prime powers». CMS Conf. Proc, 20, 1997, pàg. 151-162.