Coeficient binomial

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 què es poden escollir k objectes entre un conjunt de n sense tenir en compte l'ordre.

Definició

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

<math>

{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) </math>

i

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

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

<math> (x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k} y^k. \qquad (2) </math>

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

<math> {n \choose k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots 1}, </math>

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 què s'han triat.

Exemple

<math> {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.</math>