Enmatemáticas , laregla de Pascal es unaidentidad combinatórica sobre loscoeficientes binomiales . La regla dice que para cadanúmero natural n se tiene que
( n − 1 k ) + ( n − 1 k − 1 ) = ( n k ) para 1 ≤ k ≤ n {\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k}\quad {\text{para }}1\leq k\leq n} donde( n k ) {\displaystyle {n \choose k}}
( n k ) + ( n k − 1 ) = ( n + 1 k ) para 1 ≤ k ≤ n + 1 {\displaystyle {n \choose k}+{n \choose k-1}={n+1 \choose k}\quad {\text{para }}1\leq k\leq n+1} [ editar ] Ilustración de demostración combinacional:( 4 1 ) + ( 4 2 ) = ( 5 2 ) . {\displaystyle {\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( n k ) {\displaystyle {n \choose k}} k elementos de un conjunto conn elementos. Supongamos que un elemento en particular es etiquetado comoX en un conjunto conn elementos.
Para construir unsubconjunto dek elementos que contengaX , cogemosX yk-1 elementos de losn-1 elementos restantes del conjunto. Entonces habría( n − 1 k − 1 ) {\displaystyle {n-1 \choose k-1}}
Para construir un subconjunto dek elementos que no contenganX , cogemosk elementos de losn-1 elementos restantes del conjunto. Entonces habría( n − 1 k ) {\displaystyle {n-1 \choose k}}
Cada subconjunto dek elementos puede contenerX o no. El número total de subconjuntos conk elementos en un conjunto den elementos es la suma del número de subconjuntos que contienenX y el número de subconjuntos que no contienenX, ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {n-1 \choose k-1}+{n-1 \choose k}}
Por lo tanto,( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}
[ editar ] Alternativamente, la derivación algebraica del caso binomial es la siguiente:
( n − 1 k ) + ( n − 1 k − 1 ) = ( n − 1 ) ! k ! ( n − 1 − k ) ! + ( n − 1 ) ! ( k − 1 ) ! ( n − k ) ! = ( n − 1 ) ! [ n − k k ! ( n − k ) ! + k k ! ( n − k ) ! ] = ( n − 1 ) ! n k ! ( n − k ) ! = n ! k ! ( n − k ) ! = ( n k ) . {\displaystyle {\begin{aligned}{n-1 \choose k}+{n-1 \choose k-1}&={\frac {(n-1)!}{k!(n-1-k)!}}+{\frac {(n-1)!}{(k-1)!(n-k)!}}\\&=(n-1)!\left[{\frac {n-k}{k!(n-k)!}}+{\frac {k}{k!(n-k)!}}\right]\\&=(n-1)!{\frac {n}{k!(n-k)!}}\\&={\frac {n!}{k!(n-k)!}}\\&={\binom {n}{k}}.\end{aligned}}}
La regla de Pascal puede generalizarse a coeficientes multinomiales.[ 2] p tal quep ≥ 2 {\displaystyle p\geq 2} k 1 , k 2 , k 3 , … , k p ∈ N ∗ {\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{*}} n = k 1 + k 2 + k 3 + ⋯ + k p ≥ 1 {\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1} ( n − 1 k 1 − 1 , k 2 , k 3 , … , k p ) + ( n − 1 k 1 , k 2 − 1 , k 3 , … , k p ) + ⋯ + ( n − 1 k 1 , k 2 , k 3 , … , k p − 1 ) = ( n k 1 , k 2 , k 3 , … , k p ) {\displaystyle {n-1 \choose k_{1}-1,k_{2},k_{3},\dots ,k_{p}}+{n-1 \choose k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \choose k_{1},k_{2},k_{3},\dots ,k_{p}-1}={n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}} ( n k 1 , k 2 , k 3 , … , k p ) {\displaystyle {n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}} x 1 k 1 x 2 k 2 … x p k p {\displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}\dots x_{p}^{k_{p}}} ( x 1 + x 2 + ⋯ + x p ) n {\displaystyle (x_{1}+x_{2}+\dots +x_{p})^{n}} p un entero tal quep ≥ 2 {\displaystyle p\geq 2} k 1 , k 2 , k 3 , … , k p ∈ N ∗ {\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{*}} n = k 1 + k 2 + k 3 + ⋯ + k p ≥ 1 {\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1} ( n − 1 k 1 − 1 , k 2 , k 3 , … , k p ) + ( n − 1 k 1 , k 2 − 1 , k 3 , … , k p ) + ⋯ + ( n − 1 k 1 , k 2 , k 3 , … , k p − 1 ) = ( n − 1 ) ! ( k 1 − 1 ) ! k 2 ! k 3 ! ⋯ k p ! + ( n − 1 ) ! k 1 ! ( k 2 − 1 ) ! k 3 ! ⋯ k p ! + ⋯ + ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ ( k p − 1 ) ! = k 1 ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! + k 2 ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! + ⋯ + k p ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = ( k 1 + k 2 + ⋯ + k p ) ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = n ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = n ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = ( n k 1 , k 2 , k 3 , … , k p ) . {\displaystyle {\begin{aligned}&{}\quad {n-1 \choose k_{1}-1,k_{2},k_{3},\dots ,k_{p}}+{n-1 \choose k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \choose k_{1},k_{2},k_{3},\dots ,k_{p}-1}\\&={\frac {(n-1)!}{(k_{1}-1)!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {(n-1)!}{k_{1}!(k_{2}-1)!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots (k_{p}-1)!}}\\&={\frac {k_{1}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {k_{2}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {k_{p}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={\frac {(k_{1}+k_{2}+\cdots +k_{p})(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}\\&={\frac {n(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={\frac {n!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}.\end{aligned}}}
↑ 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 
Datos:Q17099544