Coeficient binomial

De Viquipèdia

En matemàtiques, concretament en combinatòria, un coeficient binomial és un coeficient de qualsevol dels termes del polinomi que resulta de desenvolupar el binomi de Newton, es a dir el desenvolupament de (x+y)ⁿ. Resulta que els coeficient del terme k-èssim d’aquest polinomi, (si n és el grau del polinomi) és el nombre de formes en que es poden escollir k objectes entre un conjunt de n sense tenir en compte l’ordre.

[edita] Definició

Donat un enter no negatiu n i un enter k, el coeficient binomial es defineix com el nombre natural:

${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{si}\ n\geq k\geq 0 \qquad (1)$

${n \choose k} = 0 \quad \mbox{if } k<0 \mbox{ or } k>n$

on n! significa el factorial def n.

Els coeficients binomials són els coeficients del desenvolupament del binomi (x + y)ⁿ (d’aquí els hi ve el nom):

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

[edita] Interpretació combinatòria

Des de el punt de vista combinatori el coeficient binomial es pot entendre com el nombre de formes en que 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 formes 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, per tant el segon es pot escollir de n-1 formes, com per cada forma d’escollir el primer hi ha n-1 formes d’escollir el segon en total per als dos primers n’hi ha n*(n-1) i així sucessivament fins a k. Però en escollir els elements d’aquesta forma 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 que s’han triat.

[edita] 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.$