Regla de Pascal

No s'ha de confondre amb Principi 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é:

<math>{n-1\choose k} + {n-1\choose k-1} = {n\choose k} </math>

On <math>1 \leq k < n</math> i <math>{n\choose k}</math> és un coeficient binomial.

Demostració combinatòria

La regla de Pascal té un significat combinatori intuitiu. Recardent que <math>{a\choose b}</math> é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 <math>{n\choose k}</math> 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 <math>n-1\choose k-1</math> formes.

Quan X no és al subconjunt, cal triat tots els k elements a partir del subconjunt format pels n-1 objectes que no són X. Això es pot fer de <math>n-1\choose k</math> formes.

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

Demostració algebraica

S'ha de demostrar

<math> { n \choose k } + { n \choose k-1 }</math> <math> =</math> <math> { n+1 \choose k }</math>

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

<math> \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-(k-1))!}</math>

Reduint a comú denominador i simplificant s'obté

<math> \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!}</math>

<math> =</math> <math> \frac{(n-k+1)n!}{(n-k+1)k!(n-k)!}+\frac{kn!}{k(k-1)!(n-k+1)!}</math>

<math> =</math> <math> \frac{(n-k+1)n!+kn!}{k!(n-k+1)!}</math>

<math> =</math> <math> \frac{(n+1)n!}{k!((n+1)-k)!}</math>

<math> =</math> <math> \frac{(n+1)!}{k!((n+1)-k)!}</math>

<math> =</math> <math> { n+1 \choose k }</math>

Vegeu també

• Triangle de Pascal