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

donde ${displaystyle {n choose k}}$ es un coeficiente binomial. Esto también puede ser comúnmente escrito como

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

Prueba. Recordemos que ${displaystyle {n choose k}}$es igual al número de subconuntos 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 ${displaystyle {n-1 choose 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 ${displaystyle {n-1 choose 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, ${displaystyle {n-1 choose k-1}+{n-1 choose k}}$.

Por lo tanto, ${displaystyle {n choose k}={n-1 choose k-1}+{n-1 choose k}}$.

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

${displaystyle {egin{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)!}} ight]\&=(n-1)!{frac {n}{k!(n-k)!}}\&={frac {n!}{k!(n-k)!}}\&={inom {n}{k}}.end{aligned}}}$

La regla de Pascal puede generalizarse a coeficientes multinomiales.^[2]​ Para cualquier entero p tal que ${displaystyle pgeq 2}$, ${displaystyle k_{1},k_{2},k_{3},dots ,k_{p}in mathbb {N} ^{*}}$, y ${displaystyle n=k_{1}+k_{2}+k_{3}+cdots +k_{p}geq 1}$, ${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}}}$ donde ${displaystyle {n choose k_{1},k_{2},k_{3},dots ,k_{p}}}$ es el coeficiente del término ${displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}dots x_{p}^{k_{p}}}$ en expansión de ${displaystyle (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 ${displaystyle pgeq 2}$, ${displaystyle k_{1},k_{2},k_{3},dots ,k_{p}in mathbb {N} ^{*}}$, y ${displaystyle n=k_{1}+k_{2}+k_{3}+cdots +k_{p}geq 1}$. Entonces: ${displaystyle {egin{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}}}$