Regla de Pascal

Plantilla:Falten referències Plantilla:Confusió 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é:

(\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) = (\binom{n}{k})

On $1 \leq k < n$ i $(\binom{n}{k})$ és un coeficient binomial.

Demostració combinatòria

La regla de Pascal té un significat combinatori intuïtiu. Recardent que $(\binom{a}{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 $(\binom{n}{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 $(\binom{n - 1}{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 $(\binom{n - 1}{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 $(\binom{n}{k})$ ), també és igual a $(\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ .

Demostració algebraica

S'ha de demostrar

(\binom{n}{k}) + (\binom{n}{k - 1})

=

(\binom{n + 1}{k})

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

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

Reduint a comú denominador i simplificant s'obté

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

=

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

=

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

=

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

=

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

=

(\binom{n + 1}{k})

Vegeu també

Triangle de Pascal

Regla de Pascal

Demostració combinatòria

Demostració algebraica

Vegeu també

Menú de navegació

Cerca