Regla de Pascal

En matemáticas, la regla de Pascal es una identidad combinatórica sobre los coeficientes binomiales. La regla dice que para cada número natural n se tiene que

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

donde $(\binom{n}{k})$ es un coeficiente binomial. Esto también puede ser comúnmente escrito como

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

Demostración combinatoria

Archivo:Pascal's rule 4c1 plus 4c2 equals 5c2.svg

Ilustración de demostración combinacional:

(\binom{4}{1}) + (\binom{4}{2}) = (\binom{5}{2}) .

La regla de Pascal tiene un significado combinacional intuitivo, que se expresa claramente en esta prueba de conteo.^[1]

Demostración: Recordemos que $(\binom{n}{k})$ es igual al número de subconjuntos con k elementos de un conjunto con n elementos. Supongamos que un elemento en particular es etiquetado como X en un conjunto con n elementos.

Para construir un subconjunto de k elementos que contenga X, cogemos X y k-1 elementos de los n-1 elementos restantes del conjunto. Entonces habría $(\binom{n - 1}{k - 1})$ de estos subconjuntos.

Para construir un subconjunto de k elementos que no contengan X, cogemos k elementos de los n-1 elementos restantes del conjunto. Entonces habría $(\binom{n - 1}{k})$ de estos subconjuntos.

Cada subconjunto de k elementos puede contener X o no. El número total de subconjuntos con k elementos en un conjunto de n elementos es la suma del número de subconjuntos que contienen X y el número de subconjuntos que no contienen X, $(\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ .

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

Demostración algebraica

Alternativamente, la derivación algebraica del caso binomial es la siguiente:

$\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}$

Generalización

La regla de Pascal puede generalizarse a coeficientes multinomiales.^[2] Para cualquier entero p tal que $p \geq 2$ , $k_{1}, k_{2}, k_{3}, \dots, k_{p} \in ℕ^{*}$ , y $n = k_{1} + k_{2} + k_{3} + \dots + k_{p} \geq 1$ , $(\binom{n - 1}{k_{1} - 1, k_{2}, k_{3}, \dots, k_{p}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, k_{3}, \dots, k_{p}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, k_{3}, \dots, k_{p} - 1}) = (\binom{n}{k_{1}, k_{2}, k_{3}, \dots, k_{p}})$ donde $(\binom{n}{k_{1}, k_{2}, k_{3}, \dots, k_{p}})$ es el coeficiente del término $x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{p}^{k_{p}}$ en expansión de $(x_{1} + x_{2} + \dots + x_{p})^{n}$ .
La derivación algebraica para este caso general es la siguiente. Sea p un entero tal que $p \geq 2$ , $k_{1}, k_{2}, k_{3}, \dots, k_{p} \in ℕ^{*}$ , y $n = k_{1} + k_{2} + k_{3} + \dots + k_{p} \geq 1$ . Entonces: $\begin{matrix} (\binom{n - 1}{k_{1} - 1, k_{2}, k_{3}, \dots, k_{p}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, k_{3}, \dots, k_{p}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, k_{3}, \dots, k_{p} - 1}) \\ = \frac{(n - 1)!}{(k_{1} - 1)! k_{2}! k_{3}! \dots k_{p}!} + \frac{(n - 1)!}{k_{1}! (k_{2} - 1)! k_{3}! \dots k_{p}!} + \dots + \frac{(n - 1)!}{k_{1}! k_{2}! k_{3}! \dots (k_{p} - 1)!} \\ = \frac{k_{1} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} + \frac{k_{2} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} + \dots + \frac{k_{p} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = \frac{(k_{1} + k_{2} + \dots + k_{p}) (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} \\ = \frac{n (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = \frac{n!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = (\binom{n}{k_{1}, k_{2}, k_{3}, \dots, k_{p}}) . \end{matrix}$

Véase también

Triángulo de Pascal

Referencias

↑ Brualdi, Richard A. (2010), Introductory Combinatorics (5th edición), Prentice-Hall, p. 44, ISBN 978-0-13-602040-0 .
↑ Brualdi, Richard A. (2010), Introductory Combinatorics (5th edición), Prentice-Hall, p. 144, ISBN 978-0-13-602040-0 .

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

Enlaces externos

Pascal's rule en PlanetMath.
Central binomial coefficient en PlanetMath.
Binomial coefficient en PlanetMath.
Pascal's triangle en PlanetMath.

[1] Brualdi, Richard A. (2010), Introductory Combinatorics (5th edición), Prentice-Hall, p. 44, ISBN 978-0-13-602040-0 .

[Brualdi-2] Brualdi, Richard A. (2010), Introductory Combinatorics (5th edición), Prentice-Hall, p. 144, ISBN 978-0-13-602040-0 .

[1]

[2]