Regla de Pascal
Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat. |
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é:
On i és un coeficient binomial.
Demostració combinatòria
[modifica]La regla de Pascal té un significat combinatori intuïtiu. Recardent que é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 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 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 formes.
En conlusió el nombre de formes d'agafar un subconjunt de k objectes a partir d'un conjunt de n objectes, (que és ), també és igual a .
Demostració algebraica
[modifica]S'ha de demostrar
Es comença escrivint el cantó de la dreta com a
Reduint a comú denominador i simplificant s'obté