Regla de Pascal

En matemàtiques, la regla de Pascal és una identitat combinatórica sobre els coeficients binomiales. La regla diu que per a cada número natural n es té que

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

a on $(\binom{n}{k})$ és un coeficient binomial. Açò també pot ser comunament escrit com

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

Demostració combinatòria

La regla de Pascal té un significat combinacional intuïtiu, que s'expressa clarament en esta prova de conteo.^[1]

Demostració: Recordem que $(\binom{n}{k})$ és igual al número de subconjunts en k elements d'un conjunt en n elements. Supongam que un element en particular és etiquetat com a X en un conjunt en n elements.

Per a construir un subconjunt de k elements que continga X, agarrem X i k-1 elements dels n-1 elements restants del conjunt. Llavors hi hauria $(\binom{n - 1}{k - 1})$ d'estos subconjunts.

Per a construir un subconjunt de k elements que no continguen X, agarrem k elements dels n-1 elements restants del conjunt. Llavors hi hauria $(\binom{n - 1}{k})$ d'estos subconjunts.

Cada subconjunt de k elements pot contindre X o no. El número total de subconjunts en k elements en un conjunt de n elements és la suma del número de subconjunts que contenen X i el número de subconjunts que no contenen X, $(\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ .

Per lo tant, $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ .

Demostració algebraica

Alternativament, la derivació algebraica del cas binomial és la següent:

$\begin{matrix} (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) & = \frac{(n - 1)!}{k! (n - 1 - k)!} + \frac{(n - 1)!}{(k - 1)! (n - k)!} \\ = (n - 1)! [\frac{n - k}{k! (n - k)!} + \frac{k}{k! (n - k)!}] \\ = (n - 1)! \frac{n}{k! (n - k)!} \\ = \frac{n!}{k! (n - k)!} \\ = (\binom{n}{k}) . \end{matrix}$

Vore també

Triàngul de Pascal

Referències

↑ (2010).«Introductory Combinatorics».Prentice-Hall.

Merris, Russell. Combinatorics. John Wiley & Sons. 2003 ISBN 978-0-471-26296-1

Referències

Este artícul conté una traducció derivada de «Regla de Pascal» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] (2010).«Introductory Combinatorics».Prentice-Hall.

[1]