Regla de Pascal

En matemàtiques, la regla de Pascal és una identitat combinatòria entre coeficients binomials. Estableix que per a qualsevol nombre natural n es té:^[1]

${\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k}}$

No s'ha de confondre amb Principi de Pascal.

On ${\displaystyle 1\leq k<n}$ i ${\displaystyle {n \choose k}}$ és un coeficient binomial.

Demostració combinatòria

La regla de Pascal té un significat combinatori intuïtiu.^[2] Recardent que ${\displaystyle {a \choose b}}$ és el nombre de formes en què es pot triar un subconjunt de b elements a partir d'un conjunt de a elements. Per tant, el cantó dret de la identitat ${\displaystyle {n \choose k}}$ indica el nombre de formes en què es pot formar un subconjunt de k elements a partir d'un conjunt de n elements.

Ara, suposeu que es distingeix un element particular 'X' del conjunt de n elements. Així, cada cop que es trien k elements per a formar un subconjunt, hi ha dues possibilitats: X pertany al subconjunt escollit o no.

Si X pertany al subconjunt, en realitat només es necessiten triar k-1 objectes més dels n-1 objectes restants (donat que X serà segur al subconjunt). Això es pot fer de ${\displaystyle n-1 \choose k-1}$ formes.

Quan X no és al subconjunt, cal triar tots els k elements a partir del subconjunt format pels n-1 objectes que no són X. Això es pot fer de ${\displaystyle n-1 \choose k}$ formes.

En conlusió el nombre de formes d'agafar un subconjunt de k objectes a partir d'un conjunt de n objectes, (que és ${\displaystyle {n \choose k}}$), també és igual a ${\displaystyle {n-1 \choose k-1}+{n-1 \choose k}}$.

Demostració algebraica

S'ha de demostrar

${\displaystyle {n \choose k}+{n \choose k-1}}$ ${\displaystyle =}$ ${\displaystyle {n+1 \choose k}}$

Es comença escrivint el cantó de la dreta com a

${\displaystyle {\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k-1)!(n-(k-1))!}}}$

Reduint a comú denominador i simplificant s'obté

${\displaystyle {\frac {n!}{k!(n-k)!}}+{\frac {n!}{(k-1)!(n-k+1)!}}}$

${\displaystyle =}$ ${\displaystyle {\frac {(n-k+1)n!}{(n-k+1)k!(n-k)!}}+{\frac {kn!}{k(k-1)!(n-k+1)!}}}$

${\displaystyle =}$ ${\displaystyle {\frac {(n-k+1)n!+kn!}{k!(n-k+1)!}}}$

${\displaystyle =}$ ${\displaystyle {\frac {(n+1)n!}{k!((n+1)-k)!}}}$

${\displaystyle =}$ ${\displaystyle {\frac {(n+1)!}{k!((n+1)-k)!}}}$

${\displaystyle =}$ ${\displaystyle {n+1 \choose k}}$