Identidad combinatoria sobre coeficientes binomiales.
En matemáticas , la regla de Pascal (o fórmula de Pascal ) es una identidad combinatoria sobre coeficientes binomiales . Afirma que para números naturales positivos n y k ,
( norte − 1 k ) + ( norte − 1 k − 1 ) = ( norte k ) , {\displaystyle {n-1 \elegir k}+{n-1 \elegir k-1}={n \elegir k},} x k expansión (1 + x ) n n k [1] n < k ( norte k ) {\displaystyle {\tbinom {n}{k}}} La regla de Pascal también puede verse como una afirmación de que la fórmula
( X + y ) ! X ! y ! = ( X + y X ) = ( X + y y ) {\displaystyle {\frac {(x+y)!}{x!y!}}={x+y \choose x}={x+y \choose y}} N x , y = N x − 1 , y + N x , y − 1 , N 0 , y = N x , 0 = 1 {\displaystyle N_{x,y}=N_{x-1,y}+N_{x,y-1},\quad N_{0,y}=N_{x,0}=1} triángulo de Pascal La regla de Pascal también se puede generalizar para aplicarla a coeficientes multinomiales .
Prueba combinatoria Ilustra la prueba combinatoria: ( 4 1 ) + ( 4 2 ) = ( 5 2 ) . {\displaystyle {\binom {4}{1}}+{\binom {4}{2}}={\binom {5}{2}}.} La regla de Pascal tiene un significado combinatorio intuitivo, que se expresa claramente en esta prueba de conteo. [2] : 44
Prueba . Recuerde que es igual al número de subconjuntos con k elementos de un conjunto con n elementos. Supongamos que un elemento en particular tiene la etiqueta exclusiva X en un conjunto con n elementos. ( n k ) {\displaystyle {\tbinom {n}{k}}}
Para construir un subconjunto de k elementos que contengan X , incluya X y elija k − 1 elementos de los n − 1 elementos restantes del conjunto. Existen tales subconjuntos. ( n − 1 k − 1 ) {\displaystyle {\tbinom {n-1}{k-1}}}
Para construir un subconjunto de k elementos que no contengan X , elija k elementos de los n − 1 elementos restantes del conjunto. Existen tales subconjuntos. ( n − 1 k ) {\displaystyle {\tbinom {n-1}{k}}}
Cada subconjunto de k elementos contiene 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 ,. ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}
Esto equivale a ; por lo tanto, . ( n k ) {\displaystyle {\tbinom {n}{k}}} ( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}
prueba algebraica Alternativamente, sigue la derivación algebraica del caso binomial.
( 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}}} Generalización La regla de Pascal se puede generalizar a coeficientes multinomiales. [2] : 144 Para cualquier número entero p tal que , y , p ≥ 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}}\cdots x_{p}^{k_{p}}} ( x 1 + x 2 + ⋯ + x p ) n {\displaystyle (x_{1}+x_{2}+\dots +x_{p})^{n}} La derivación algebraica para este caso general es la siguiente. [2] : 144 Sea p un número entero tal que , y . Entonces p ≥ 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}}} Ver también Referencias ^ Mazur, David R. (2010), Combinatoria / Una visita guiada , Asociación Matemática de América, p. 60, ISBN 978-0-88385-762-5 ^ abc Brualdi, Richard A. (2010), Combinatoria introductoria (5ª ed.), Prentice-Hall, ISBN 978-0-13-602040-0 Bibliografía enlaces externos Este artículo incorpora material del triángulo de Pascal en PlanetMath , que tiene la licencia Creative Commons Attribution/Share-Alike License .
Este artículo incorpora material de la prueba de reglas de Pascal en PlanetMath , que tiene la licencia Creative Commons Attribution/Share-Alike License .