Coeficiente binomial

Un método utiliza la fórmula recursiva y puramente aditiva.$${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}}$$para todos los números enteros${\displaystyle n,k}$de tal manera que${\displaystyle 1\leq k<n}$, con valores límite $${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1}$$ para todos los enteros n ≥ 0 .

La fórmula se deduce al considerar el conjunto {1, 2, 3, ..., n } y contar por separado (a) las agrupaciones de k elementos que incluyen un elemento particular del conjunto, digamos " i ", en cada grupo (ya que " i " ya está elegido para ocupar un lugar en cada grupo, solo necesitamos elegir k − 1 de los n − 1 restantes ) y (b) todas las agrupaciones de k elementos que no incluyen " i "; esto enumera todas las posibles combinaciones de k elementos de n . También se deduce al rastrear las contribuciones a X ^k en (1 + X ) ^{n −1} (1 + X ) . Como no hay ningún X ^{n +1} ni X ⁻¹ en (1 + X ) ⁿ , se podría extender la definición más allá de los límites anteriores para incluir${\displaystyle {\tbinom {n}{k}}=0}$cuando k > n o k < 0. Esta fórmula recursiva permite entonces la construcción del triángulo de Pascal , rodeado de espacios en blanco donde estarían los ceros o los coeficientes triviales.

Un método más eficiente para calcular los coeficientes binomiales individuales viene dado por la fórmula $${\displaystyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}={\frac {n(n-1)(n-2)\cdots (n-(k-1))}{k(k-1)(k-2)\cdots 1}}=\prod _{i=1}^{k}{\frac {n+1-i}{i}},}$$ donde el numerador de la primera fracción ,${\displaystyle n^{\underline {k}}}$⁠ , es un factorial descendente . Esta fórmula es más fácil de entender para la interpretación combinatoria de los coeficientes binomiales. El numerador da el número de maneras de seleccionar una secuencia de k objetos distintos, conservando el orden de selección, de un conjunto de n objetos. El denominador cuenta el número de secuencias distintas que definen la misma k -combinación cuando se ignora el orden. Esta fórmula también se puede expresar de forma recursiva. Usando la notación "C" de arriba, ⁠${\displaystyle C_{n,k}=C_{n,k-1}\cdot (n-k+1)/k}$, donde​${\displaystyle C_{n,0}=1}$Se obtiene fácilmente evaluando${\displaystyle C_{n,k}/C_{n,k-1}}$y puede entenderse intuitivamente como comenzando en el coeficiente más a la izquierda del ⁠${\displaystyle n}$-ésima fila del triángulo de Pascal , cuyo valor es siempre${\displaystyle 1}$⁠ , y calculando recursivamente el siguiente coeficiente a su derecha hasta que el ⁠${\displaystyle k}$Se ha alcanzado el -ésimo.

Debido a la simetría de los coeficientes binomiales con respecto a k y n − k , el cálculo del producto anterior, así como la relación recursiva, se puede optimizar estableciendo su límite superior al menor de k y n − k .

Finalmente, está la forma compacta, que se usa a menudo en demostraciones y derivaciones, y que hace un uso repetido de la conocida función factorial : $${\displaystyle {\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{for }}\ 0\leq k\leq n,}$$ donde n ! denota el factorial de n . Esta fórmula se deduce de la fórmula multiplicativa anterior multiplicando el numerador y el denominador por ( n − k )!; en consecuencia, involucra muchos factores comunes al numerador y al denominador. Es menos práctica para el cálculo explícito (en el caso de que k sea pequeño y n sea grande) a menos que primero se cancelen los factores comunes (en particular, dado que los valores factoriales crecen muy rápidamente). La fórmula sí presenta una simetría que es menos evidente en la fórmula multiplicativa (aunque sí en las definiciones).

lo que conduce a una rutina de cálculo multiplicativa más eficiente. Usando la notación factorial descendente , $${\displaystyle {\binom {n}{k}}={\begin{cases}n^{\underline {k}}/k!&{\text{if }}\ k\leq {\frac {n}{2}}\\n^{\underline {n-k}}/(n-k)!&{\text{if }}\ k>{\frac {n}{2}}\end{cases}}.}$$

La fórmula multiplicativa permite extender la definición de coeficientes binomiales ^{[ 4 ]} reemplazando n por un número arbitrario α (negativo, real, complejo) o incluso un elemento de cualquier anillo conmutativo en el que todos los enteros positivos sean invertibles: $${\displaystyle {\binom {\alpha }{k}}={\frac {\alpha ^{\underline {k}}}{k!}}={\frac {\alpha (\alpha -1)(\alpha -2)\cdots (\alpha -k+1)}{k(k-1)(k-2)\cdots 1}}\quad {\text{for }}k\in \mathbb {N} {\text{ and arbitrary }}\alpha .}$$

Con esta definición se tiene una generalización de la fórmula binomial (con una de las variables establecida en 1), lo que justifica seguir llamándola${\displaystyle {\tbinom {\alpha }{k}}}$coeficientes binomiales:

Esta fórmula es válida para todos los números complejos α y X con | X | < 1. También puede interpretarse como una identidad de series de potencias formales en X , donde en realidad puede servir como definición de potencias arbitrarias de series de potencias con coeficiente constante igual a 1; la cuestión es que con esta definición se cumplen todas las identidades que se esperan para la exponenciación , en particular    $${\displaystyle (1+X)^{\alpha }(1+X)^{\beta }=(1+X)^{\alpha +\beta }\quad {\text{and}}\quad ((1+X)^{\alpha })^{\beta }=(1+X)^{\alpha \beta }.}$$

Si α es un entero no negativo n , entonces todos los términos con k > n son cero, ^{[ 5 ]} y la serie infinita se convierte en una suma finita, recuperando así la fórmula binomial. Sin embargo, para otros valores de α , incluidos los enteros negativos y los números racionales, la serie es realmente infinita.

Sobre cualquier cuerpo de característica 0 (es decir, cualquier cuerpo que contenga los números racionales ), cada polinomio p ( t ) de grado como máximo d se puede expresar de forma única como una combinación lineal.${\textstyle \sum _{k=0}^{d}a_{k}{\binom {t}{k}}}$de coeficientes binomiales, porque los coeficientes binomiales consisten en un polinomio de cada grado. El coeficiente a _k es la k -ésima diferencia de la secuencia p (0), p (1), ..., p ( k ). Explícitamente, ^{[ 7 ]}

Cada polinomio${\displaystyle {\tbinom {t}{k}}}$es de valor entero : tiene un valor entero en todas las entradas enteras .${\displaystyle t}$⁠ . (Una forma de demostrar esto es por inducción sobre k usando la identidad de Pascal .) Por lo tanto, cualquier combinación lineal entera de polinomios con coeficientes binomiales también es de valor entero. Recíprocamente, ( 4 ) muestra que cualquier polinomio de valor entero es una combinación lineal entera de estos polinomios con coeficientes binomiales. De manera más general, para cualquier subanillo R de un cuerpo de característica 0 K , un polinomio en K [ t ] toma valores en R en todos los enteros si y solo si es una combinación lineal R de polinomios con coeficientes binomiales.

El polinomio de valores enteros 3 t (3 t + 1) / 2 se puede reescribir como $${\displaystyle 9{\binom {t}{2}}+6{\binom {t}{1}}+0{\binom {t}{0}}.}$$

La fórmula

dice que los elementos en la n -ésima fila del triángulo de Pascal siempre suman 2 elevado a la n -ésima potencia. Esto se obtiene del teorema del binomio ( ∗ ) estableciendo x = 1 e y = 1 . La fórmula también tiene una interpretación combinatoria natural: el lado izquierdo suma el número de subconjuntos de {1, ..., n } de tamaños k = 0, 1, ..., n , dando el número total de subconjuntos. (Es decir, el lado izquierdo cuenta el conjunto potencia de {1, ..., n }.) Sin embargo, estos subconjuntos también se pueden generar eligiendo o excluyendo sucesivamente cada elemento 1, ..., n ; las n elecciones binarias independientes (cadenas de bits) permiten un total de${\displaystyle 2^{n}}$opciones. Los lados izquierdo y derecho son dos maneras de contar la misma colección de subconjuntos, por lo que son iguales.

Las fórmulas

y $${\displaystyle \sum _{k=0}^{n}k^{2}{\binom {n}{k}}=(n+n^{2})2^{n-2}}$$ se deduce del teorema del binomio después de diferenciar con respecto a x (dos veces para este último) y luego sustituir x = y = 1 .

La identidad de Chu-Vandermonde , que se cumple para cualesquiera valores complejos m y n y cualquier entero no negativo k , es

y se puede encontrar examinando el coeficiente de${\displaystyle x^{k}}$en la expansión de (1 + x ) ^m (1 + x ) ^{n − m} = (1 + x ) ⁿ usando la ecuación ( 2 ). Cuando m = 1 , la ecuación ( 7 ) se reduce a la ecuación ( 3 ). En el caso especial n = 2 m , k = m , usando ( 1 ), la expansión ( 7 ) se convierte en (como se ve en el triángulo de Pascal a la derecha)

${\displaystyle {\begin{array}{c}1\\1\qquad 1\\1\qquad 2\qquad 1\\{\color {blue}1\qquad 3\qquad 3\qquad 1}\\1\qquad 4\qquad 6\qquad 4\qquad 1\\1\qquad 5\qquad 10\qquad 10\qquad 5\qquad 1\\1\qquad 6\qquad 15\qquad {\color {red}20}\qquad 15\qquad 6\qquad 1\\1\qquad 7\qquad 21\qquad 35\qquad 35\qquad 21\qquad 7\qquad 1\end{array}}}$

Triángulo de Pascal, filas 0 a 7. La ecuación 8 para m = 3 se ilustra en las filas 3 y 6 como${\displaystyle 1^{2}+3^{2}+3^{2}+1^{2}=20}$⁠ .

donde el término del lado derecho es un coeficiente binomial central .

Otra forma de la identidad de Chu-Vandermonde, que se aplica a cualesquiera enteros j , k y n que satisfacen 0 ≤ j ≤ k ≤ n , es

La demostración es similar, pero utiliza el desarrollo en serie binomial ( 2 ) con exponentes enteros negativos. Cuando j = k , la ecuación ( 9 ) da la identidad del palo de hockey.$${\displaystyle \sum _{m=k}^{n}{\binom {m}{k}}={\binom {n+1}{k+1}}}$$ y su relativo $${\displaystyle \sum _{r=0}^{m}{\binom {n+r}{r}}={\binom {n+m+1}{m}}.}$$

Sea F ( n ) el n -ésimo número de Fibonacci . Entonces $${\displaystyle \sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n-k}{k}}=F(n+1).}$$ Esto se puede demostrar por inducción usando ( 3 ) o mediante la representación de Zeckendorf . A continuación se presenta una demostración combinatoria.

Muchas identidades que involucran coeficientes binomiales pueden probarse por medios combinatorios . Por ejemplo, para enteros no negativos${\displaystyle {n}\geq {q}}$⁠ , la identidad $${\displaystyle \sum _{k=q}^{n}{\binom {n}{k}}{\binom {k}{q}}=2^{n-q}{\binom {n}{q}}}$$ (que se reduce a ( 6 ) cuando q = 1) se puede demostrar mediante doble conteo , como sigue. El lado izquierdo cuenta el número de maneras de seleccionar un subconjunto de [ n ] = {1, 2, ..., n } con al menos q elementos y marcar q elementos entre los seleccionados. El lado derecho cuenta lo mismo, porque hay${\displaystyle {\tbinom {n}{q}}}$formas de elegir un conjunto de q elementos para marcar, y${\displaystyle 2^{n-q}}$elegir cuáles de los elementos restantes de [ n ] también pertenecen al subconjunto.

En la identidad de Pascal $${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}$$ Ambos lados cuentan el número de subconjuntos de k elementos de [ n ]: los dos términos del lado derecho los agrupan en aquellos que contienen el elemento n y aquellos que no lo contienen.

La identidad ( 8 ) también tiene una prueba combinatoria. La identidad se lee: $${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}.}$$

Supongamos que tienes${\displaystyle 2n}$cuadrados vacíos dispuestos en una fila y quieres marcar (seleccionar) n de ellos.${\displaystyle {\tbinom {2n}{n}}}$formas de hacerlo. Por otro lado, puede seleccionar sus n cuadrados seleccionando k cuadrados de entre los primeros n y${\displaystyle n-k}$cuadrados de los n cuadrados restantes; cualquier k de 0 a n funcionará. Esto da como resultado $${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}{\binom {n}{n-k}}={\binom {2n}{n}}.}$$ Ahora aplica ( 1 ) para obtener el resultado.

Si denotamos por F ( i ) la secuencia de números de Fibonacci , indexada de modo que F (0) = F (1) = 1 , entonces la identidad $${\displaystyle \sum _{k=0}^{\left\lfloor {\frac {n}{2}}\right\rfloor }{\binom {n-k}{k}}=F(n)}$$ tiene la siguiente demostración combinatoria. ^{[ 12 ]} Se puede demostrar por inducción que F ( n ) cuenta el número de maneras en que una tira de cuadrados de n × 1 puede ser cubierta por teselas de 2 × 1 y 1 × 1. Por otro lado, si tal recubrimiento usa exactamente k de las teselas de 2 × 1 , entonces usa n − 2 k de las teselas de 1 × 1 , y por lo tanto usa n − k teselas en total. Hay${\displaystyle {\tbinom {n-k}{k}}}$formas de ordenar estas baldosas, y por lo tanto, al sumar este coeficiente sobre todos los valores posibles de k se obtiene la identidad.

La identidad de Dixon es $${\displaystyle \sum _{k=-a}^{a}(-1)^{k}{\binom {2a}{k+a}}^{3}={\frac {(3a)!}{(a!)^{3}}}}$$ o, más generalmente, $${\displaystyle \sum _{k=-a}^{a}(-1)^{k}{\binom {a+b}{a+k}}{\binom {b+c}{b+k}}{\binom {c+a}{c+k}}={\frac {(a+b+c)!}{a!\,b!\,c!}}\,,}$$ donde a , b y c son números enteros no negativos.

Ciertas integrales trigonométricas tienen valores que se pueden expresar en términos de coeficientes binomiales: Para cualquier ⁠${\displaystyle m,n\in \mathbb {N} }$⁠ , $${\displaystyle \int _{-\pi }^{\pi }\cos((2m-n)x)\cos ^{n}(x)\ dx={\frac {\pi }{2^{n-1}}}{\binom {n}{m}}}$$$${\displaystyle \int _{-\pi }^{\pi }\sin((2m-n)x)\sin ^{n}(x)\ dx={\begin{cases}(-1)^{m+(n+1)/2}{\frac {\pi }{2^{n-1}}}{\binom {n}{m}},&n{\text{ odd}}\\0,&{\text{otherwise}}\end{cases}}}$$$${\displaystyle \int _{-\pi }^{\pi }\cos((2m-n)x)\sin ^{n}(x)\ dx={\begin{cases}(-1)^{m+(n/2)}{\frac {\pi }{2^{n-1}}}{\binom {n}{m}},&n{\text{ even}}\\0,&{\text{otherwise}}\end{cases}}}$$

Esto se puede demostrar utilizando la fórmula de Euler para convertir funciones trigonométricas en exponenciales complejas, desarrollando mediante el teorema del binomio e integrando término a término.

Si n es primo, entonces$${\displaystyle {\binom {n-1}{k}}\equiv (-1)^{k}\mod n}$$para cada k con ⁠${\displaystyle 0\leq k\leq n-1}$⁠ . De manera más general, esto sigue siendo cierto si n es cualquier número y k es tal que todos los números entre 1 y k son coprimos con n .

De hecho, tenemos $${\displaystyle {\binom {n-1}{k}}={(n-1)(n-2)\cdots (n-k) \over 1\cdot 2\cdots k}=\prod _{i=1}^{k}{n-i \over i}\equiv \prod _{i=1}^{k}{-i \over i}=(-1)^{k}\mod n.}$$

Para un n fijo , la función generadora ordinaria de la secuencia${\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},{\tbinom {n}{2}},\ldots }$es $${\displaystyle \sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}=(1+x)^{n}.}$$

Para un k fijo , la función generadora ordinaria de la secuencia es${\displaystyle {\tbinom {0}{k}},{\tbinom {1}{k}},{\tbinom {2}{k}},\ldots }$⁠ , es $${\displaystyle \sum _{n=0}^{\infty }{\binom {n}{k}}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}.}$$

La función generadora bivariada de los coeficientes binomiales es $${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}.}$$

Una función generadora bivariada simétrica de los coeficientes binomiales es $${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{\binom {n+k}{k}}x^{k}y^{n}={\frac {1}{1-x-y}}.}$$ que es la misma que la función generadora anterior después de la sustitución .${\displaystyle x\to xy}$⁠ .

Una función generadora bivariada exponencial simétrica de los coeficientes binomiales es: $${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{\binom {n+k}{k}}{\frac {x^{k}y^{n}}{(n+k)!}}=e^{x+y}.}$$

La aproximación de Stirling produce la siguiente aproximación, válida cuando${\displaystyle n-k,k}$ambos tienden al infinito: $${\displaystyle {\binom {n}{k}}\sim {\sqrt {n \over 2\pi k(n-k)}}\cdot {n^{n} \over k^{k}(n-k)^{n-k}}}$$ Debido a que las formas de desigualdad de la fórmula de Stirling también acotan los factoriales, ligeras variantes de la aproximación asintótica anterior proporcionan cotas exactas. En particular, cuando${\displaystyle n}$es suficientemente grande, uno tiene $${\displaystyle {\binom {2n}{n}}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}}$$y​${\displaystyle {\sqrt {n}}{\binom {2n}{n}}\geq 2^{2n-1}}$⁠ . De manera más general, para m ≥ 2 y n ≥ 1 (nuevamente, aplicando la fórmula de Stirling a los factoriales en el coeficiente binomial), $${\displaystyle {\sqrt {n}}{\binom {mn}{n}}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}.}$$

Si n es grande y k es lineal en n , existen varias estimaciones asintóticas precisas para el coeficiente binomial .${\displaystyle {\binom {n}{k}}}$⁠ . Por ejemplo, si${\displaystyle |n/2-k|=o(n^{2/3})}$entonces $${\displaystyle {\binom {n}{k}}\sim {\binom {n}{\frac {n}{2}}}e^{-d^{2}/(2n)}\sim {\frac {2^{n}}{\sqrt {{\frac {1}{2}}n\pi }}}e^{-d^{2}/(2n)}}$$ donde d = n − 2 k . ^{[ 17 ]}

Si n es grande y k es o ( n ) (es decir, si k / n → 0 ), entonces $${\displaystyle {\binom {n}{k}}\sim \left({\frac {ne}{k}}\right)^{k}\cdot (2\pi k)^{-1/2}\cdot \exp \left(-{\frac {k^{2}}{2n}}(1+o(1))\right)}$$ donde nuevamente o es la notación o minúscula . ^{[ 18 ]}

Se puede obtener una cota superior simple para la suma de los coeficientes binomiales utilizando una estimación aproximada para la fórmula multiplicativa para${\displaystyle {\binom {m}{i}}}$y luego el teorema del binomio : $${\displaystyle \sum _{i=0}^{k}{\binom {n}{i}}\leq \sum _{i=0}^{k}n^{i}\leq \sum _{i=0}^{k}{\binom {k}{i}}\,n^{i}\cdot 1^{k-i}=(n+1)^{k}.}$$ Se proporcionan límites más precisos mediante $${\displaystyle {\frac {1}{\sqrt {8n\varepsilon (1-\varepsilon )}}}\cdot 2^{H(\varepsilon )\cdot n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\varepsilon )\cdot n},}$$ válido para todos los números enteros${\displaystyle n>k\geq 1}$con​${\displaystyle \varepsilon \doteq k/n\leq 1/2}$⁠ . ^{[ 19 ]}

La fórmula del producto infinito para la función gamma también proporciona una expresión para los coeficientes binomiales. $${\displaystyle (-1)^{k}{\binom {z}{k}}={\binom {-z+k-1}{k}}={\frac {1}{\Gamma (-z)}}{\frac {1}{(k+1)^{z+1}}}\prod _{j=k+1}{\frac {\left(1+{\frac {1}{j}}\right)^{-z-1}}{1-{\frac {z+1}{j}}}}}$$ lo que produce las fórmulas asintóticas $${\displaystyle {\binom {z}{k}}\approx {\frac {(-1)^{k}}{\Gamma (-z)k^{z+1}}}\qquad {\text{and}}\qquad {\binom {z+k}{k}}={\frac {k^{z}}{\Gamma (z+1)}}\left(1+{\frac {z(z+1)}{2k}}+{\mathcal {O}}\left(k^{-2}\right)\right)}$$ como​${\displaystyle k\to \infty }$⁠ .

Este comportamiento asintótico está contenido en la aproximación. $${\displaystyle {\binom {z+k}{k}}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}}$$ también. (Aquí)${\displaystyle H_{k}}$es el k -ésimo número armónico y${\displaystyle \gamma }$es la constante de Euler-Mascheroni .

Además, la fórmula asintótica $${\displaystyle {\frac {\binom {z+k}{j}}{\binom {k}{j}}}\to \left(1-{\frac {j}{k}}\right)^{-z}\quad {\text{and}}\quad {\frac {\binom {j}{j-k}}{\binom {j-z}{j-k}}}\to \left({\frac {j}{k}}\right)^{z}}$$ ser cierto, siempre${\displaystyle k\to \infty }$y${\displaystyle j/k\to x}$para algún número complejo${\displaystyle x}$⁠ .

Los coeficientes binomiales se pueden generalizar a coeficientes multinomiales definidos como el número: $${\displaystyle {\binom {n}{k_{1},k_{2},\ldots ,k_{r}}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{r}!}}}$$ dónde $${\displaystyle \sum _{i=1}^{r}k_{i}=n.}$$