Binomi de Newton
El binomi de Newton és un algoritme que permet calcular una potència qualsevol d'un binomi. Per fer-ho, s'usen els coeficients binomials, que no són més que una successió de nombres combinatoris. La fórmula general del binomi de Newton és:
$$$(a+b)^n = \begin{pmatrix} n \\ 0 \end{pmatrix} a^n + \begin{pmatrix} n \\ 1 \end{pmatrix} a^{n-1} b + \begin{pmatrix} n \\ 2 \end{pmatrix} a^{n-2} b^2 + \ldots +$$$
$$$ \begin{pmatrix} n \\ n-1 \end{pmatrix} a b^{n-1} + \begin{pmatrix} n \\ n \end{pmatrix} b^{n} $$$
Els nombres combinatoris que apareixen a la fórmula són precisament els anomenats coeficients binomials.
Per exemple:
$$$\begin{array}{rl} (a+b)^4 =& \begin{pmatrix} 4 \\ 0 \end{pmatrix} a^4 + \begin{pmatrix} 4 \\ 1 \end{pmatrix} a^3 b + \begin{pmatrix} 4 \\ 2 \end{pmatrix} a^2 b^2 + \begin{pmatrix} 4 \\ 3 \end{pmatrix} a b^3 + \begin{pmatrix} 4 \\ 4 \end{pmatrix} b^4 \\ =& a^4+4a^3b+6a^2b^2+4ab^3+b^4 \end{array}$$$
(En el cas que en el binomi figuri un signe menys, els signes del desenvolupament han d'anar-se alternant de la forma $$+ \ -\ +\ -\ +\ -\ \ldots$$)
Triangle de Pascal
Pascal va idear una manera senzilla de calcular nombres combinatoris (encara que en alguns textos aquesta idea s'atribueix a Tartaglia):
$$$\begin{array}{ccccccccccc} & & & & & 1 & & & & & \\ & & & & 1 & & 1 & & & & \\ & & & 1 & & 2 & & 1 & & & \\ & & 1 & & 3 & & 3 & & 1 & & \\ & 1 & & 4 & & 6 & & 4 & & 1 & \\ 1& & 5 & & 10 & & 10 & & 5 & & 1 \end{array}$$$
El mètode rep el nom de triangle de Pascal i es construeix de la següent manera (per files i de dalt a baix):
- En el vèrtex es col·loca un $$1$$.
- Cada fila comença i acaba en $$1$$.
- Els altres números de la fila són sempre la suma dels dos que té just a sobre.
L'última fila, per exemple, ens donaria el valor dels nombres combinatoris consecutius:
$$$\begin{pmatrix} 5 \\ 0 \end{pmatrix}, \quad \begin{pmatrix} 5 \\ 1 \end{pmatrix}, \quad \begin{pmatrix} 5 \\ 2 \end{pmatrix}, \quad \begin{pmatrix} 5 \\ 3 \end{pmatrix}, \quad \begin{pmatrix} 5 \\ 4 \end{pmatrix}, \quad \begin{pmatrix} 5 \\ 5 \end{pmatrix}$$$
El terme general del desenvolupament de $$(a+b)^n$$ ve donat per la fórmula:
$$$\begin{pmatrix} n \\ k \end{pmatrix} a^{n-k}b^k$$$
Segons això, en l'exemple del principi tindríem que el tercer terme seria (substituint $$k = 2$$, ja que la sèrie comença sempre per $$k = 0$$):
$$$\begin{pmatrix} 4 \\ 2 \end{pmatrix} a^2 b^2=6a^2b^2$$$
Aquesta fórmula permet calcular el valor d'un terme qualsevol sense necessitat d'efectuar tot el desenvolupament.
Per exemple, volem calcular el 20è terme del desenvolupament de $$(x+y)^{30}$$. Aplicant la fórmula:
$$$ \begin{pmatrix} 30 \\ 19 \end{pmatrix} x^{30-19} y^{19} = 54627300 x^{11}y^{19}$$$