Coeficiente binomial

Número de subconjuntos de un tamaño determinado

Los coeficientes binomiales se pueden organizar para formar el triángulo de Pascal , en el que cada entrada es la suma de las dos inmediatamente superiores.

Visualización del desarrollo binomial hasta la 4ª potencia

En matemáticas , los coeficientes binomiales son los números enteros positivos que aparecen como coeficientes en el teorema binomial . Comúnmente, un coeficiente binomial se indexa mediante un par de números enteros n ≥ k ≥ 0 y se escribe Es el coeficiente del término x ^k en la expansión polinómica de la potencia binomial (1 + x ) ⁿ ; este coeficiente se puede calcular mediante la fórmula multiplicativa ${\displaystyle {\tbinom {n}{k}}.}$

${\displaystyle {\binom {n}{k}}={\frac {n\times (n-1)\times \cdots \times (n-k+1)}{k\times (k-1)\times \cdots \times 1}},}$

que utilizando notación factorial se puede expresar de forma compacta como

${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$

Por ejemplo, la cuarta potencia de 1 + x es

${\displaystyle {\begin{aligned}(1+x)^{4}&={\tbinom {4}{0}}x^{0}+{\tbinom {4}{1}}x^{1}+{\tbinom {4}{2}}x^{2}+{\tbinom {4}{3}}x^{3}+{\tbinom {4}{4}}x^{4}\\&=1+4x+6x^{2}+4x^{3}+x^{4},\end{aligned}}}$

y el coeficiente binomial es el coeficiente del término x ² . ${\displaystyle {\tbinom {4}{2}}={\tfrac {4\times 3}{2\times 1}}={\tfrac {4!}{2!2!}}=6}$

Al organizar los números en filas sucesivas para n = 0, 1, 2, ... se obtiene una matriz triangular llamada triángulo de Pascal , que satisface la relación de recurrencia. ${\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},\ldots ,{\tbinom {n}{n}}}$

${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}.}$

Los coeficientes binomiales aparecen en muchas áreas de las matemáticas, y especialmente en la combinatoria . En combinatoria el símbolo suele leerse como " n choose k " porque hay formas de elegir un subconjunto (desordenado) de k elementos de un conjunto fijo de n elementos. Por ejemplo, hay formas de elegir 2 elementos de {1, 2, 3, 4} , a saber: {1, 2} , {1, 3} , {1, 4} , {2, 3} , {2, 4} y {3, 4} . ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {4}{2}}=6}$

La primera forma de los coeficientes binomiales se puede generalizar para cualquier número complejo z y entero k ≥ 0 , y muchas de sus propiedades continúan siendo válidas en esta forma más general. ${\displaystyle {\tbinom {z}{k}}}$

Historia y notación

Andreas von Ettingshausen introdujo la notación en 1826, ^[1] aunque los números ya se conocían siglos antes (véase el triángulo de Pascal ). Hacia 1150, el matemático indio Bhaskaracharya expuso los coeficientes binomiales en su libro Līlāvatī . ^[2] ${\displaystyle {\tbinom {n}{k}}}$

Las notaciones alternativas incluyen C ( n , k ) , _n C _k , ⁿ C _k , C^k-
_n, ^[3] C^no
_k, y C _{n , k} , en todas las cuales la C representa combinaciones u opciones ; la notación C significa el número de maneras de elegir k de n objetos. Muchas calculadoras usan variantes de la notación C porque pueden representarla en una pantalla de una sola línea. En esta forma, los coeficientes binomiales se comparan fácilmente con el número de k permutaciones de n , escrito como P ( n , k ) , etc.

Definición e interpretaciones

Para los números naturales (incluido el 0) n y k , el coeficiente binomial se puede definir como el coeficiente del monomio X ^k en la expansión de (1 + X ) ⁿ . El mismo coeficiente también aparece (si k ≤ n ) en la fórmula binomial ${\displaystyle {\tbinom {n}{k}}}$

(válido para cualquier elemento x , y de un anillo conmutativo ), lo que explica el nombre "coeficiente binomial".

Otra ocurrencia de este número es en combinatoria, donde da el número de maneras, sin tener en cuenta el orden, en que k objetos pueden ser elegidos de entre n objetos; más formalmente, el número de k subconjuntos de elementos (o k combinaciones ) de un conjunto de n elementos . Este número puede verse como igual al de la primera definición, independientemente de cualquiera de las fórmulas siguientes para calcularlo: si en cada uno de los n factores de la potencia (1 + X ) ⁿ uno etiqueta temporalmente el término X con un índice i (que va de 1 a n ), entonces cada subconjunto de k índices da después de la expansión una contribución X ^k , y el coeficiente de ese monomio en el resultado será el número de tales subconjuntos. Esto muestra en particular que es un número natural para cualesquiera números naturales n y k . Existen muchas otras interpretaciones combinatorias de los coeficientes binomiales (problemas de conteo para los cuales la respuesta está dada por una expresión de coeficiente binomial), por ejemplo, el número de palabras formadas por n bits (dígitos 0 o 1) cuya suma es k está dada por , mientras que el número de formas de escribir donde cada a _i es un entero no negativo está dado por ⁠ ⁠ . Se puede demostrar que la mayoría de estas interpretaciones son equivalentes a contar k -combinaciones. ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle k=a_{1}+a_{2}+\cdots +a_{n}}$ ${\displaystyle {\tbinom {n+k-1}{n-1}}}$

Cálculo del valor de los coeficientes binomiales

Existen varios métodos para calcular el valor de sin realmente expandir una potencia binomial o contar k combinaciones. ${\displaystyle {\tbinom {n}{k}}}$

Fórmula recursiva

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

La fórmula se deduce de 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 llenar un lugar en cada grupo, solo necesitamos elegir k − 1 de los n − 1 restantes ) y (b) todas las agrupaciones de k que no incluyen " i "; esto enumera todas las posibles k combinaciones de n elementos. También se deduce de rastrear las contribuciones a X ^k en (1 + X ) ^{n −1} (1 + X ) . Como hay cero X ^{n +1} o X ⁻¹ en (1 + X ) ⁿ , uno podría extender la definición más allá de los límites anteriores para incluir cuando k > n o k < 0 . Esta fórmula recursiva permite entonces la construcción del triángulo de Pascal , rodeado de espacios blancos donde estarían los ceros, o coeficientes triviales. ${\displaystyle {\tbinom {n}{k}}=0}$

Fórmula multiplicativa

Un método más eficiente para calcular coeficientes binomiales individuales se da mediante la fórmula donde el numerador de la primera fracción, , es un factorial descendente . Esta fórmula es más fácil de entender para la interpretación combinatoria de 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 en forma recursiva. Usando la notación "C" de arriba, , donde . Se deriva fácilmente evaluando y se puede entender intuitivamente como comenzando en el coeficiente más a la izquierda de la -ésima fila del triángulo de Pascal , cuyo valor es siempre , y calculando recursivamente el siguiente coeficiente a su derecha hasta que se alcanza el -ésimo. $${\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}},}$$ ${\displaystyle n^{\underline {k}}}$ ${\displaystyle C_{n,k}=C_{n,k-1}\cdot (n-k+1)/k}$ ${\displaystyle C_{n,0}=1}$ ${\displaystyle C_{n,k}/C_{n,k-1}}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle k}$

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 pueden optimizar estableciendo su límite superior en el menor de k y n − k .

Fórmula factorial

Por último, aunque no es adecuada desde el punto de vista computacional, existe la forma compacta, que se utiliza a menudo en demostraciones y derivaciones, y que hace un uso repetido de la conocida función factorial : donde n ! denota el factorial de n . Esta fórmula se deduce de la fórmula multiplicativa anterior al multiplicar numerador y denominador por ( n − k )! ; como consecuencia, implica 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 se cancelen primero los factores comunes (en particular porque los valores factoriales crecen muy rápidamente). La fórmula sí presenta una simetría que es menos evidente a partir de la fórmula multiplicativa (aunque sí lo es a partir de las definiciones). $${\displaystyle {\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{for }}\ 0\leq k\leq n,}$$

lo que conduce a una rutina computacional multiplicativa más eficiente. Utilizando 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}}.}$$

Generalización y conexión con la serie binomial

La fórmula multiplicativa permite ampliar 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 números 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 fijada en 1), lo que justifica seguir llamando a los coeficientes binomiales: ${\displaystyle {\tbinom {\alpha }{k}}}$

Esta fórmula es válida para todos los números complejos α y X con | X | < 1. También se puede interpretar como una identidad de serie 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; el punto es que con esta definición se cumplen todas las identidades que uno espera 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.

Triángulo de Pascal

Fila 1000 del triángulo de Pascal, dispuesta verticalmente, con representaciones en escala de grises de los dígitos decimales de los coeficientes, alineadas a la derecha. El límite izquierdo de la imagen corresponde aproximadamente al gráfico del logaritmo de los coeficientes binomiales e ilustra que forman una secuencia logarítmica-cóncava .

La regla de Pascal es la importante relación de recurrencia

que se puede utilizar para demostrar por inducción matemática que es un número natural para todo entero n ≥ 0 y todo entero k , un hecho que no es inmediatamente obvio a partir de la fórmula (1). A la izquierda y a la derecha del triángulo de Pascal, las entradas (mostradas como espacios en blanco) son todas cero. ${\displaystyle {\tbinom {n}{k}}}$

La regla de Pascal también da lugar al triángulo de Pascal :

La fila número n contiene los números para k = 0, …, n . Se construye colocando primero unos en las posiciones más externas y luego llenando cada posición interna con la suma de los dos números directamente encima. Este método permite el cálculo rápido de coeficientes binomiales sin la necesidad de fracciones o multiplicaciones. Por ejemplo, al observar la fila número 5 del triángulo, uno puede leer rápidamente que ${\displaystyle {\tbinom {n}{k}}}$

${\displaystyle (x+y)^{5}={\underline {1}}x^{5}+{\underline {5}}x^{4}y+{\underline {10}}x^{3}y^{2}+{\underline {10}}x^{2}y^{3}+{\underline {5}}xy^{4}+{\underline {1}}y^{5}.}$

Combinatoria y estadística

Los coeficientes binomiales son importantes en combinatoria porque proporcionan fórmulas fáciles para ciertos problemas de conteo frecuentes:

• Existen formas de elegir k elementos de un conjunto de n elementos. Véase Combinación . ${\displaystyle {\tbinom {n}{k}}}$
• Existen formas de elegir k elementos de un conjunto de n elementos si se permiten repeticiones. Véase Multiset . ${\displaystyle {\tbinom {n+k-1}{k}}}$
• Hay cadenas que contienen k unos y n ceros. ${\displaystyle {\tbinom {n+k}{k}}}$
• Hay cadenas que constan de k unos y n ceros tales que no hay dos unos adyacentes. ^[6] ${\displaystyle {\tbinom {n+1}{k}}}$
• Los números catalanes son ${\displaystyle {\tfrac {1}{n+1}}{\tbinom {2n}{n}}.}$
• La distribución binomial en estadística es ${\displaystyle {\tbinom {n}{k}}p^{k}(1-p)^{n-k}.}$

Coeficientes binomiales como polinomios

Para cualquier entero no negativo k , la expresión se puede escribir como un polinomio con denominador k ! : ${\textstyle {\binom {t}{k}}}$

${\displaystyle {\binom {t}{k}}={\frac {t^{\underline {k}}}{k!}}={\frac {t(t-1)(t-2)\cdots (t-k+1)}{k(k-1)(k-2)\cdots 2\cdot 1}};}$

Esto presenta un polinomio en t con coeficientes racionales .

Como tal, se puede evaluar en cualquier número real o complejo t para definir coeficientes binomiales con dichos primeros argumentos. Estos "coeficientes binomiales generalizados" aparecen en el teorema binomial generalizado de Newton .

Para cada k , el polinomio se puede caracterizar como el único polinomio de grado k p ( t ) que satisface p (0) = p (1) = ⋯ = p ( k − 1) = 0 y p ( k ) = 1 . ${\displaystyle {\tbinom {t}{k}}}$

Sus coeficientes se pueden expresar en términos de números de Stirling del primer tipo :

${\displaystyle {\binom {t}{k}}=\sum _{i=0}^{k}s(k,i){\frac {t^{i}}{k!}}.}$

La derivada de se puede calcular mediante diferenciación logarítmica : ${\displaystyle {\tbinom {t}{k}}}$

${\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}={\binom {t}{k}}\sum _{i=0}^{k-1}{\frac {1}{t-i}}.}$

Esto puede causar un problema cuando se evalúa en números enteros de a , pero utilizando las identidades siguientes podemos calcular la derivada como: ${\displaystyle 0}$ ${\displaystyle t-1}$

${\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}=\sum _{i=0}^{k-1}{\frac {(-1)^{k-i-1}}{k-i}}{\binom {t}{i}}.}$

Coeficientes binomiales como base para el espacio de polinomios

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 es expresable de forma única como una combinación lineal 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] ${\textstyle \sum _{k=0}^{d}a_{k}{\binom {t}{k}}}$

Polinomios con valores enteros

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

Ejemplo

El polinomio de valor entero 3 t (3 t + 1) / 2 se puede reescribir como

${\displaystyle 9{\binom {t}{2}}+6{\binom {t}{1}}+0{\binom {t}{0}}.}$

Identidades que involucran coeficientes binomiales

La fórmula factorial facilita la relación de coeficientes binomiales cercanos. Por ejemplo, si k es un entero positivo y n es arbitrario, entonces

y, con un poco más de trabajo,

${\displaystyle {\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.}$

También podemos conseguir

${\displaystyle {\binom {n-1}{k}}={\frac {n-k}{n}}{\binom {n}{k}}.}$

Además, puede resultar útil lo siguiente:

${\displaystyle {\binom {n}{k}}{\binom {k}{j}}={\binom {n}{j}}{\binom {n-j}{k-j}}={\binom {n}{k-j}}{\binom {n-k+j}{j}}.}$

Para n constante , tenemos la siguiente recurrencia:

${\displaystyle {\binom {n}{k}}={\frac {n-k+1}{k}}{\binom {n}{k-1}}.}$

En resumen, tenemos

${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}={\frac {n-k+1}{k}}{\binom {n}{k-1}}={\frac {n}{n-k}}{\binom {n-1}{k}}}$

${\displaystyle ={\frac {n}{k}}{\binom {n-1}{k-1}}={\frac {n}{n-2k}}{\Bigg (}{\binom {n-1}{k}}-{\binom {n-1}{k-1}}{\Bigg )}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}.}$

Sumas de los coeficientes binomiales

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 ( ∗ ) al establecer 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 opciones binarias independientes (cadenas de bits) permiten un total de opciones. Los lados izquierdo y derecho son dos formas de contar la misma colección de subconjuntos, por lo que son iguales. ${\displaystyle 2^{n}}$

Las fórmulas

y

${\displaystyle \sum _{k=0}^{n}k^{2}{\binom {n}{k}}=(n+n^{2})2^{n-2}}$

se sigue del teorema del binomio después de derivar con respecto a x (dos veces para este último) y luego sustituir x = y = 1 .

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

y se puede encontrar examinando el coeficiente de 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 x^{k}}$

${\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 cualquier número entero j , k y n que satisfaga 0 ≤ j ≤ k ≤ n , es

La prueba es similar, pero utiliza la expansión de la 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 pariente

${\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 por la representación de Zeckendorf . A continuación se ofrece una prueba combinatoria.

Multisecciones de sumas

Para los números enteros s y t tales que la multisección en serie da la siguiente identidad para la suma de los coeficientes binomiales: ${\displaystyle 0\leq t<s,}$

${\displaystyle {\binom {n}{t}}+{\binom {n}{t+s}}+{\binom {n}{t+2s}}+\ldots ={\frac {1}{s}}\sum _{j=0}^{s-1}\left(2\cos {\frac {\pi j}{s}}\right)^{n}\cos {\frac {\pi (n-2t)j}{s}}.}$

Para números pequeños , estas series tienen formas particularmente agradables; por ejemplo, ^[8]

${\displaystyle {\binom {n}{0}}+{\binom {n}{3}}+{\binom {n}{6}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {n\pi }{3}}\right)}$

${\displaystyle {\binom {n}{1}}+{\binom {n}{4}}+{\binom {n}{7}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-2)\pi }{3}}\right)}$

${\displaystyle {\binom {n}{2}}+{\binom {n}{5}}+{\binom {n}{8}}+\cdots ={\frac {1}{3}}\left(2^{n}+2\cos {\frac {(n-4)\pi }{3}}\right)}$

${\displaystyle {\binom {n}{0}}+{\binom {n}{4}}+{\binom {n}{8}}+\cdots ={\frac {1}{2}}\left(2^{n-1}+2^{\frac {n}{2}}\cos {\frac {n\pi }{4}}\right)}$

${\displaystyle {\binom {n}{1}}+{\binom {n}{5}}+{\binom {n}{9}}+\cdots ={\frac {1}{2}}\left(2^{n-1}+2^{\frac {n}{2}}\sin {\frac {n\pi }{4}}\right)}$

${\displaystyle {\binom {n}{2}}+{\binom {n}{6}}+{\binom {n}{10}}+\cdots ={\frac {1}{2}}\left(2^{n-1}-2^{\frac {n}{2}}\cos {\frac {n\pi }{4}}\right)}$

${\displaystyle {\binom {n}{3}}+{\binom {n}{7}}+{\binom {n}{11}}+\cdots ={\frac {1}{2}}\left(2^{n-1}-2^{\frac {n}{2}}\sin {\frac {n\pi }{4}}\right)}$

Sumas parciales

Aunque no existe una fórmula cerrada para sumas parciales

${\displaystyle \sum _{j=0}^{k}{\binom {n}{j}}}$

de coeficientes binomiales, ^[9] se puede usar nuevamente ( 3 ) y la inducción para demostrar que para k = 0, …, n − 1 ,

${\displaystyle \sum _{j=0}^{k}(-1)^{j}{\binom {n}{j}}=(-1)^{k}{\binom {n-1}{k}},}$

con caso especial ^[10]

${\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}=0}$

para n > 0 . Este último resultado es también un caso especial del resultado de la teoría de diferencias finitas de que para cualquier polinomio P ( x ) de grado menor que n , ^[11]

${\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(j)=0.}$

Diferenciando ( 2 ) k veces y fijando x = −1 obtenemos esto para , cuando 0 ≤ k < n , y el caso general se deduce tomando combinaciones lineales de estos. ${\displaystyle P(x)=x(x-1)\cdots (x-k+1)}$

Cuando P ( x ) es de grado menor o igual a n ,

donde es el coeficiente de grado n en P ( x ). ${\displaystyle a_{n}}$

De manera más general, para ( 10 ),

${\displaystyle \sum _{j=0}^{n}(-1)^{j}{\binom {n}{j}}P(m+(n-j)d)=d^{n}n!a_{n}}$

donde m y d son números complejos. Esto se deduce inmediatamente de aplicar ( 10 ) al polinomio ⁠ ⁠ ${\displaystyle Q(x):=P(m+dx)}$ en lugar de ⁠ ⁠ ${\displaystyle P(x)}$ , y observar que ⁠ ⁠ ${\displaystyle Q(x)}$ todavía tiene grado menor o igual a n , y que su coeficiente de grado n es d ⁿ a _n .

La serie es convergente para k ≥ 2. Esta fórmula se utiliza en el análisis del problema del tanque alemán . Se deduce de lo cual se demuestra por inducción sobre M . ${\textstyle {\frac {k-1}{k}}\sum _{j=0}^{\infty }{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}}$ ${\textstyle {\frac {k-1}{k}}\sum _{j=0}^{M}{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}-{\frac {1}{\binom {M+x}{k-1}}}}$

Identidades con pruebas combinatorias

Muchas identidades que involucran coeficientes binomiales pueden probarse por medios combinatorios . Por ejemplo, para números enteros no negativos , la identidad ${\displaystyle {n}\geq {q}}$

${\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 dar una prueba de doble conteo , como sigue. El lado izquierdo cuenta el número de formas 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 formas de elegir un conjunto de q elementos para marcar, y de elegir cuáles de los elementos restantes de [ n ] también pertenecen al subconjunto. ${\displaystyle {\tbinom {n}{q}}}$ ${\displaystyle 2^{n-q}}$

En la identidad de Pascal

${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose 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.

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 tiene cuadrados vacíos dispuestos en una fila y desea marcar (seleccionar) n de ellos. Hay formas de hacerlo. Por otro lado, puede seleccionar sus n cuadrados seleccionando k cuadrados de entre los primeros n y cuadrados de los n cuadrados restantes; cualquier k de 0 a n funcionará. Esto da ${\displaystyle 2n}$ ${\displaystyle {\tbinom {2n}{n}}}$ ${\displaystyle n-k}$

${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}{\binom {n}{n-k}}={\binom {2n}{n}}.}$

Ahora aplique ( 1 ) para obtener el resultado.

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

Fila de suma de coeficientes

El número de k combinaciones para todos los k , , es la suma de la fila n ésima (contando desde 0) de los coeficientes binomiales. Estas combinaciones se enumeran mediante los dígitos 1 del conjunto de números de base 2 contando desde 0 hasta , donde cada posición de dígito es un elemento del conjunto de n . ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ ${\displaystyle 2^{n}-1}$

La identidad de Dixon

La identidad de Dixon es

${\displaystyle \sum _{k=-a}^{a}(-1)^{k}{2a \choose k+a}^{3}={\frac {(3a)!}{(a!)^{3}}}}$

o, más generalmente,

${\displaystyle \sum _{k=-a}^{a}(-1)^{k}{a+b \choose a+k}{b+c \choose b+k}{c+a \choose c+k}={\frac {(a+b+c)!}{a!\,b!\,c!}}\,,}$

donde a , b y c son números enteros no negativos.

Identidades continuas

Ciertas integrales trigonométricas tienen valores expresables 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, expandiendo utilizando el teorema binomial e integrando término por término.

Congruencias

Si n es primo, entonces para cada k con 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 . $${\displaystyle {\binom {n-1}{k}}\equiv (-1)^{k}\mod n}$$ ${\displaystyle 0\leq k\leq n-1.}$

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

Funciones generadoras

Funciones generadoras ordinarias

Para un n fijo , la función generadora ordinaria de la secuencia es ${\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},{\tbinom {n}{2}},\ldots }$

${\displaystyle \sum _{k=0}^{\infty }{n \choose 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 ,}$

${\displaystyle \sum _{n=0}^{\infty }{n \choose 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}{n \choose 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 }{n+k \choose 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}$

Función generadora exponencial

Una función generadora bivariada exponencial simétrica de los coeficientes binomiales es:

${\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{n+k \choose k}{\frac {x^{k}y^{n}}{(n+k)!}}=e^{x+y}.}$

Propiedades de divisibilidad

En 1852, Kummer demostró que si m y n son números enteros no negativos y p es un número primo, entonces la mayor potencia de p que divide es igual a p ^c , donde c es el número de acarreos cuando m y n se suman en base p . Equivalentemente, el exponente de un primo p en es igual al número de números enteros no negativos j tales que la parte fraccionaria de k / p ^j es mayor que la parte fraccionaria de n / p ^j . De esto se puede deducir que es divisible por n / mcd ( n , k ). En particular, por lo tanto, se deduce que p divide para todos los números enteros positivos r y s tales que s < p ^r . Sin embargo, esto no es cierto para potencias mayores de p : por ejemplo, 9 no divide a . ${\displaystyle {\tbinom {m+n}{m}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {p^{r}}{s}}}$ ${\displaystyle {\tbinom {9}{6}}}$

Un resultado algo sorprendente de David Singmaster (1974) es que cualquier entero divide a casi todos los coeficientes binomiales. Más precisamente, fijemos un entero d y sea f ( N ) el número de coeficientes binomiales con n < N tales que d divide a . Entonces ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$

${\displaystyle \lim _{N\to \infty }{\frac {f(N)}{N(N+1)/2}}=1.}$

Dado que el número de coeficientes binomiales con n < N es N ( N + 1) / 2, esto implica que la densidad de coeficientes binomiales divisibles por d tiende a 1. ${\displaystyle {\tbinom {n}{k}}}$

Los coeficientes binomiales tienen propiedades de divisibilidad relacionadas con los mínimos comunes múltiplos de números enteros consecutivos. Por ejemplo: ^[13]

${\displaystyle {\binom {n+k}{k}}}$divide . ${\displaystyle {\frac {\operatorname {lcm} (n,n+1,\ldots ,n+k)}{n}}}$

${\displaystyle {\binom {n+k}{k}}}$es un múltiplo de . ${\displaystyle {\frac {\operatorname {lcm} (n,n+1,\ldots ,n+k)}{n\cdot \operatorname {lcm} ({\binom {k}{0}},{\binom {k}{1}},\ldots ,{\binom {k}{k}})}}}$

Otro hecho: Un entero n ≥ 2 es primo si y solo si todos los coeficientes binomiales intermedios

${\displaystyle {\binom {n}{1}},{\binom {n}{2}},\ldots ,{\binom {n}{n-1}}}$

son divisibles por n .

Prueba: Cuando p es primo, p divide

${\displaystyle {\binom {p}{k}}={\frac {p\cdot (p-1)\cdots (p-k+1)}{k\cdot (k-1)\cdots 1}}}$para todos 0 < k < p

porque es un número natural y p divide al numerador pero no al denominador. Cuando n es compuesto, sea p el factor primo más pequeño de n y sea k = n / p . Entonces 0 < p < n y ${\displaystyle {\tbinom {p}{k}}}$

${\displaystyle {\binom {n}{p}}={\frac {n(n-1)(n-2)\cdots (n-p+1)}{p!}}={\frac {k(n-1)(n-2)\cdots (n-p+1)}{(p-1)!}}\not \equiv 0{\pmod {n}}}$

de lo contrario el numerador k ( n − 1)( n − 2)⋯( n − p + 1) tiene que ser divisible por n = k × p , esto solo puede ser el caso cuando ( n − 1)( n − 2)⋯( n − p + 1) es divisible por p . Pero n es divisible por p , por lo que p no divide a n − 1, n − 2, …, n − p + 1 y como p es primo, sabemos que p no divide a ( n − 1)( n − 2)⋯( n − p + 1) y por lo tanto el numerador no puede ser divisible por n .

Límites y fórmulas asintóticas

Los siguientes límites para se cumplen para todos los valores de n y k tales que 1 ≤ k ≤ n : La primera desigualdad se deduce del hecho de que y cada uno de estos términos en este producto es . Se puede hacer un argumento similar para demostrar la segunda desigualdad. La desigualdad estricta final es equivalente a , lo cual es claro ya que el lado derecho es un término de la serie exponencial . ${\displaystyle {\tbinom {n}{k}}}$ $${\displaystyle {\frac {n^{k}}{k^{k}}}\leq {n \choose k}\leq {\frac {n^{k}}{k!}}<\left({\frac {n\cdot e}{k}}\right)^{k}.}$$ $${\displaystyle {n \choose k}={\frac {n}{k}}\cdot {\frac {n-1}{k-1}}\cdots {\frac {n-(k-1)}{1}}}$$ ${\displaystyle k}$ ${\textstyle \geq {\frac {n}{k}}}$ ${\textstyle e^{k}>k^{k}/k!}$ ${\textstyle e^{k}=\sum _{j=0}^{\infty }k^{j}/j!}$

De las propiedades de divisibilidad podemos inferir que donde se pueden lograr ambas igualdades. ^[13] $${\displaystyle {\frac {\operatorname {lcm} (n-k,\ldots ,n)}{(n-k)\cdot \operatorname {lcm} \left({\binom {k}{0}},\ldots ,{\binom {k}{k}}\right)}}\leq {\binom {n}{k}}\leq {\frac {\operatorname {lcm} (n-k,\ldots ,n)}{n-k}},}$$

Los siguientes límites son útiles en la teoría de la información: ^{[14] : 353} donde es la función de entropía binaria . Puede ajustarse aún más a para todo . ^{[15] : 309} $${\displaystyle {\frac {1}{n+1}}2^{nH(k/n)}\leq {n \choose k}\leq 2^{nH(k/n)}}$$ ${\displaystyle H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)}$ $${\displaystyle {\sqrt {\frac {n}{8k(n-k)}}}2^{nH(k/n)}\leq {n \choose k}\leq {\sqrt {\frac {n}{2\pi k(n-k)}}}2^{nH(k/n)}}$$ ${\displaystyle 1\leq k\leq n-1}$

Ambosnorteyagrande

La aproximación de Stirling produce la siguiente aproximación, válida cuando ambas tienden a infinito: Debido a que las formas de desigualdad de la fórmula de Stirling también limitan los factoriales, ligeras variantes de la aproximación asintótica anterior dan límites exactos. En particular, cuando es suficientemente grande, se tiene y . De manera más general, para m ≥ 2 y n ≥ 1 (de nuevo, aplicando la fórmula de Stirling a los factoriales en el coeficiente binomial), ${\displaystyle n-k,k}$ $${\displaystyle {n \choose k}\sim {\sqrt {n \over 2\pi k(n-k)}}\cdot {n^{n} \over k^{k}(n-k)^{n-k}}}$$ ${\displaystyle n}$ $${\displaystyle {2n \choose n}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}}$$ ${\displaystyle {\sqrt {n}}{2n \choose n}\geq 2^{2n-1}}$ $${\displaystyle {\sqrt {n}}{mn \choose 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 . Por ejemplo, si entonces donde d = n − 2 k . ^[16] ${\textstyle {\binom {n}{k}}}$ ${\displaystyle |n/2-k|=o(n^{2/3})}$ $${\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)}}$$

nortemucho más grande quea

Si n es grande y k es o ( n ) (es decir, si k / n → 0 ), entonces donde nuevamente o es la notación o pequeña . ^[17] $${\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)}$$

Sumas de coeficientes binomiales

Se puede obtener un límite superior simple y aproximado para la suma de coeficientes binomiales utilizando el teorema binomial : Se proporcionan límites más precisos mediante válidos para todos los números enteros con . ^[18] $${\displaystyle \sum _{i=0}^{k}{n \choose i}\leq \sum _{i=0}^{k}n^{i}\cdot 1^{k-i}\leq (1+n)^{k}}$$ $${\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},}$$ ${\displaystyle n>k\geq 1}$ ${\displaystyle \varepsilon \doteq k/n\leq 1/2}$

Coeficientes binomiales generalizados

La fórmula del producto infinito para la función gamma también da una expresión para los coeficientes binomiales que produce las fórmulas asintóticas como . $${\displaystyle (-1)^{k}{z \choose k}={-z+k-1 \choose 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}}}}}$$ $${\displaystyle {z \choose k}\approx {\frac {(-1)^{k}}{\Gamma (-z)k^{z+1}}}\qquad {\text{and}}\qquad {z+k \choose k}={\frac {k^{z}}{\Gamma (z+1)}}\left(1+{\frac {z(z+1)}{2k}}+{\mathcal {O}}\left(k^{-2}\right)\right)}$$ ${\displaystyle k\to \infty }$

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

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

Generalizaciones

Generalización a multinomios

Los coeficientes binomiales se pueden generalizar a coeficientes multinomiales definidos como el número:

${\displaystyle {n \choose 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.}$

Mientras que los coeficientes binomiales representan los coeficientes de ( x + y ) ⁿ , los coeficientes multinomiales representan los coeficientes del polinomio

${\displaystyle (x_{1}+x_{2}+\cdots +x_{r})^{n}.}$

El caso r = 2 da coeficientes binomiales:

${\displaystyle {n \choose k_{1},k_{2}}={n \choose k_{1},n-k_{1}}={n \choose k_{1}}={n \choose k_{2}}.}$

La interpretación combinatoria de coeficientes multinomiales es la distribución de n elementos distinguibles entre r contenedores (distinguibles), cada uno de los cuales contiene exactamente k _i elementos, donde i es el índice del contenedor.

Los coeficientes multinomiales tienen muchas propiedades similares a las de los coeficientes binomiales, por ejemplo la relación de recurrencia:

${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{r}}={n-1 \choose k_{1}-1,k_{2},\ldots ,k_{r}}+{n-1 \choose k_{1},k_{2}-1,\ldots ,k_{r}}+\ldots +{n-1 \choose k_{1},k_{2},\ldots ,k_{r}-1}}$

y simetría:

${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{r}}={n \choose k_{\sigma _{1}},k_{\sigma _{2}},\ldots ,k_{\sigma _{r}}}}$

donde es una permutación de (1, 2, ..., r ). ${\displaystyle (\sigma _{i})}$

Serie de Taylor

Utilizando números de Stirling del primer tipo, la expansión de la serie alrededor de cualquier punto elegido arbitrariamente es ${\displaystyle z_{0}}$

${\displaystyle {\begin{aligned}{z \choose k}={\frac {1}{k!}}\sum _{i=0}^{k}z^{i}s_{k,i}&=\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{j=i}^{k}{z_{0} \choose j-i}{\frac {s_{k+i-j,i}}{(k+i-j)!}}\\&=\sum _{i=0}^{k}(z-z_{0})^{i}\sum _{j=i}^{k}z_{0}^{j-i}{j \choose i}{\frac {s_{k,j}}{k!}}.\end{aligned}}}$

Coeficiente binomial conn = 1/2

La definición de los coeficientes binomiales se puede extender al caso donde es real y es entero. ${\displaystyle n}$ ${\displaystyle k}$

En particular, la siguiente identidad se cumple para cualquier número entero no negativo : ${\displaystyle k}$

${\displaystyle {{1/2} \choose {k}}={{2k} \choose {k}}{\frac {(-1)^{k+1}}{2^{2k}(2k-1)}}.}$

Esto aparece cuando se expande en una serie de potencias utilizando la serie binomial de Newton: ${\displaystyle {\sqrt {1+x}}}$

${\displaystyle {\sqrt {1+x}}=\sum _{k\geq 0}{\binom {1/2}{k}}x^{k}.}$

Productos de coeficientes binomiales

Se puede expresar el producto de dos coeficientes binomiales como una combinación lineal de coeficientes binomiales:

${\displaystyle {z \choose m}{z \choose n}=\sum _{k=0}^{\min(m,n)}{m+n-k \choose k,m-k,n-k}{z \choose m+n-k},}$

donde los coeficientes de conexión son coeficientes multinomiales . En términos de objetos combinatorios etiquetados, los coeficientes de conexión representan el número de maneras de asignar m + n − k etiquetas a un par de objetos combinatorios etiquetados (de peso m y n respectivamente) que han tenido sus primeras k etiquetas identificadas, o pegadas para obtener un nuevo objeto combinatorio etiquetado de peso m + n − k . (Es decir, separar las etiquetas en tres porciones para aplicarlas a la parte pegada, la parte no pegada del primer objeto y la parte no pegada del segundo objeto). En este sentido, los coeficientes binomiales son a las series generadoras exponenciales lo que los factoriales descendentes son a las series generadoras ordinarias.

El producto de todos los coeficientes binomiales en la n- ésima fila del triángulo de Pascal se da por la fórmula:

${\displaystyle \prod _{k=0}^{n}{\binom {n}{k}}=\prod _{k=1}^{n}k^{2k-n-1}.}$

Descomposición en fracciones parciales

La descomposición en fracciones parciales del recíproco viene dada por

${\displaystyle {\frac {1}{z \choose n}}=\sum _{i=0}^{n-1}(-1)^{n-1-i}{n \choose i}{\frac {n-i}{z-i}},\qquad {\frac {1}{z+n \choose n}}=\sum _{i=1}^{n}(-1)^{i-1}{n \choose i}{\frac {i}{z+i}}.}$

Serie binomial de Newton

La serie binomial de Newton, llamada así en honor a Sir Isaac Newton , es una generalización del teorema binomial a las series infinitas:

${\displaystyle (1+z)^{\alpha }=\sum _{n=0}^{\infty }{\alpha \choose n}z^{n}=1+{\alpha \choose 1}z+{\alpha \choose 2}z^{2}+\cdots .}$

La identidad se puede obtener demostrando que ambos lados satisfacen la ecuación diferencial (1 + z ) f' ( z ) = α f ( z ) .

El radio de convergencia de esta serie es 1. Una expresión alternativa es

${\displaystyle {\frac {1}{(1-z)^{\alpha +1}}}=\sum _{n=0}^{\infty }{n+\alpha \choose n}z^{n}}$

donde la identidad

${\displaystyle {n \choose k}=(-1)^{k}{k-n-1 \choose k}}$

se aplica.

Coeficiente binomial multiconjunto (ascendente)

Los coeficientes binomiales cuentan subconjuntos de tamaño prescrito de un conjunto dado. Un problema combinatorio relacionado es contar multiconjuntos de tamaño prescrito con elementos extraídos de un conjunto dado, es decir, contar el número de formas de seleccionar un cierto número de elementos de un conjunto dado con la posibilidad de seleccionar el mismo elemento repetidamente. Los números resultantes se denominan coeficientes multiconjunto ; ^[19] el número de formas de "multiselección" (es decir, elegir con reemplazo) k elementos de un conjunto de n elementos se denota . ${\textstyle \left(\!\!{\binom {n}{k}}\!\!\right)}$

Para evitar ambigüedad y confusión con la denotación principal de n en este artículo,
sea f = n = r + ( k − 1) y r = f − ( k − 1) .

Los coeficientes multiconjunto se pueden expresar en términos de coeficientes binomiales mediante la regla Una posible caracterización alternativa de esta identidad es la siguiente: Podemos definir el factorial descendente como y el factorial ascendente correspondiente como así, por ejemplo, Entonces los coeficientes binomiales se pueden escribir como mientras que el coeficiente multiconjunto correspondiente se define reemplazando el factorial descendente por el ascendente: $${\displaystyle {\binom {f}{k}}=\left(\!\!{\binom {r}{k}}\!\!\right)={\binom {r+k-1}{k}}.}$$ $${\displaystyle (f)_{k}=f^{\underline {k}}=(f-k+1)\cdots (f-3)\cdot (f-2)\cdot (f-1)\cdot f,}$$ $${\displaystyle r^{(k)}=\,r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1);}$$ $${\displaystyle 17\cdot 18\cdot 19\cdot 20\cdot 21=(21)_{5}=21^{\underline {5}}=17^{\overline {5}}=17^{(5)}.}$$ $${\displaystyle {\binom {f}{k}}={\frac {(f)_{k}}{k!}}={\frac {(f-k+1)\cdots (f-2)\cdot (f-1)\cdot f}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}},}$$ $${\displaystyle \left(\!\!{\binom {r}{k}}\!\!\right)={\frac {r^{(k)}}{k!}}={\frac {r\cdot (r+1)\cdot (r+2)\cdots (r+k-1)}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}}.}$$

Generalización a números enteros negativosnorte

Coeficientes binomiales C  ( n , k ) extendidos para n negativo y fraccionario , ilustrados con un binomio simple . Se puede observar que el triángulo de Pascal está rotado y los términos alternos son negados. El caso n  = −1 da la serie de Grandi .

Para cualquier n ,

${\displaystyle {\begin{aligned}{\binom {-n}{k}}&={\frac {-n\cdot -(n+1)\dots -(n+k-2)\cdot -(n+k-1)}{k!}}\\&=(-1)^{k}\;{\frac {n\cdot (n+1)\cdot (n+2)\cdots (n+k-1)}{k!}}\\&=(-1)^{k}{\binom {n+k-1}{k}}\\&=(-1)^{k}\left(\!\!{\binom {n}{k}}\!\!\right)\;.\end{aligned}}}$

En particular, los coeficientes binomiales evaluados en números enteros negativos n se dan mediante coeficientes multiconjunto con signo. En el caso especial , esto se reduce a ${\displaystyle n=-1}$ ${\displaystyle (-1)^{k}={\binom {-1}{k}}=\left(\!\!{\binom {-k}{k}}\!\!\right).}$

Por ejemplo, si n = −4 y k = 7, entonces r = 4 y f = 10:

${\displaystyle {\begin{aligned}{\binom {-4}{7}}&={\frac {-10\cdot -9\cdot -8\cdot -7\cdot -6\cdot -5\cdot -4}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=(-1)^{7}\;{\frac {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}}\\&=\left(\!\!{\binom {-7}{7}}\!\!\right)\left(\!\!{\binom {4}{7}}\!\!\right)={\binom {-1}{7}}{\binom {10}{7}}.\end{aligned}}}$

Dos argumentos de valor real o complejo

El coeficiente binomial se generaliza a dos argumentos de valor real o complejo utilizando la función gamma o la función beta mediante

${\displaystyle {x \choose y}={\frac {\Gamma (x+1)}{\Gamma (y+1)\Gamma (x-y+1)}}={\frac {1}{(x+1)\mathrm {B} (y+1,x-y+1)}}.}$

Esta definición hereda las siguientes propiedades adicionales de : ${\displaystyle \Gamma }$

${\displaystyle {x \choose y}={\frac {\sin(y\pi )}{\sin(x\pi )}}{-y-1 \choose -x-1}={\frac {\sin((x-y)\pi )}{\sin(x\pi )}}{y-x-1 \choose y};}$

además,

${\displaystyle {x \choose y}\cdot {y \choose x}={\frac {\sin((x-y)\pi )}{(x-y)\pi }}.}$

La función resultante ha sido poco estudiada, aparentemente se grafica por primera vez en (Fowler 1996). Cabe destacar que muchas identidades binomiales fallan: excepto para n positivo (es decir, negativo). El comportamiento es bastante complejo y marcadamente diferente en varios octantes (es decir, con respecto a los ejes x e y y la línea ), y el comportamiento para x negativo tiene singularidades en valores enteros negativos y un tablero de ajedrez de regiones positivas y negativas: ${\textstyle {\binom {n}{m}}={\binom {n}{n-m}}}$ ${\textstyle {\binom {-n}{m}}\neq {\binom {-n}{-n-m}}}$ ${\displaystyle -n}$ ${\displaystyle y=x}$

• en el octante es una forma suavemente interpolada del binomio habitual, con una cresta ("cresta de Pascal"). ${\displaystyle 0\leq y\leq x}$
• en el octante y en el cuadrante la función es cercana a cero. ${\displaystyle 0\leq x\leq y}$ ${\displaystyle x\geq 0,y\leq 0}$
• En el cuadrante la función es alternativamente muy grande, positiva y negativa en los paralelogramos con vértices. ${\displaystyle x\leq 0,y\geq 0}$ $${\displaystyle (-n,m+1),(-n,m),(-n-1,m-1),(-n-1,m)}$$
• En el octante el comportamiento vuelve a ser alternativamente positivo y negativo muy grande, pero sobre una cuadrícula cuadrada. ${\displaystyle 0>x>y}$
• en el octante es cercano a cero, excepto cerca de las singularidades. ${\displaystyle -1>y>x+1}$

Generalización aq-serie

El coeficiente binomial tiene una generalización q-analógica conocida como coeficiente binomial gaussiano .

Generalización a cardinales infinitos

La definición del coeficiente binomial se puede generalizar a cardinales infinitos definiendo:

${\displaystyle {\alpha \choose \beta }=\left|\left\{B\subseteq A:\left|B\right|=\beta \right\}\right|}$

donde A es un conjunto con cardinalidad . Se puede demostrar que el coeficiente binomial generalizado está bien definido, en el sentido de que no importa qué conjunto elijamos para representar el número cardinal , seguirá siendo el mismo. Para cardinales finitos, esta definición coincide con la definición estándar del coeficiente binomial. ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\textstyle {\alpha \choose \beta }}$

Suponiendo el axioma de elección , se puede demostrar que para cualquier cardinal infinito . ${\textstyle {\alpha \choose \alpha }=2^{\alpha }}$ ${\displaystyle \alpha }$

Véase también

• Transformación binomial
• Número de Delannoy
• Número euleriano
• Función hipergeométrica
• Lista de temas factoriales y binomiales
• Representación de Macaulay de un número entero
• Número de Motzkin
• Multiplicidades de entradas en el triángulo de Pascal
• Número de Narayana
• Teorema de la estrella de David
• La curiosa identidad del sol
• Tabla de series newtonianas
• Expansión trinomial

Notas

1. Higham (1998)
2. Lilavati Sección 6, Capítulo 4 (ver Knuth (1997)).
3. Uspensky 1937, pág. 18
4. Véase (Graham, Knuth y Patashnik 1994), que también define para . Las generalizaciones alternativas, como por ejemplo para dos argumentos con valores reales o complejos utilizando la función Gamma, asignan valores distintos de cero a para , pero esto hace que la mayoría de las identidades de coeficientes binomiales fallen, y por lo tanto no se usa ampliamente en la mayoría de las definiciones. Una de esas elecciones de valores distintos de cero conduce al estéticamente agradable "molino de viento de Pascal" en Hilton, Holton y Pedersen, Mathematical reflections: in a room with many mirrors , Springer, 1997, pero hace que incluso la identidad de Pascal falle (en el origen). ${\displaystyle {\tbinom {n}{k}}=0}$ ${\displaystyle k<0}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle k<0}$
5. Cuando es un entero no negativo, porque el factor -ésimo del numerador es . Por lo tanto, el término -ésimo es un producto cero para todos los . ${\displaystyle \alpha =n}$ ${\displaystyle \textstyle {\binom {n}{k}}=0}$ ${\displaystyle k>n}$ ${\displaystyle (k=n+1)}$ ${\displaystyle n-(n+1)+1=0}$ ${\displaystyle k}$ ${\displaystyle k\geq n+1}$
6. Muir, Thomas (1902). "Nota sobre combinaciones seleccionadas". Actas de la Royal Society de Edimburgo .
7. Esto puede verse como un análogo discreto del teorema de Taylor . Está estrechamente relacionado con el polinomio de Newton . Las sumas alternadas de esta forma pueden expresarse como la integral de Nörlund–Rice .
8. Gradshteyn y Ryzhik (2014, págs. 3-4).
9. Boardman, Michael (2004), "The Egg-Drop Numbers", Mathematics Magazine , 77 (5): 368–372, doi :10.2307/3219201, JSTOR  3219201, MR  1573776, es bien sabido que no existe una forma cerrada (es decir, una fórmula directa) para la suma parcial de los coeficientes binomiales.
10. ver la inducción desarrollada en la ecuación (7) p. 1389 en Aupetit, Michael (2009), "Multipartición casi homogénea con un generador determinista", Neurocomputing , 72 (7–9): 1379–1389, doi :10.1016/j.neucom.2008.12.024, ISSN  0925-2312.
11. Ruiz, Sebastian (1996). "Una identidad algebraica que conduce al teorema de Wilson". The Mathematical Gazette . 80 (489): 579–582. arXiv : math/0406086 . doi :10.2307/3618534. JSTOR  3618534. S2CID  125556648.
12. Benjamin y Quinn 2003, págs. 4-5
13. Farhi, Bakir (2007). "Límites inferiores no triviales para el mínimo común múltiplo de alguna secuencia finita de números enteros". Journal of Number Theory . 125 (2): 393–411. arXiv : 0803.0290 . doi :10.1016/j.jnt.2006.10.017. S2CID  115167580.
14. Thomas M. Cover; Joy ​​A. Thomas (18 de julio de 2006). Elementos de la teoría de la información . Hoboken, Nueva Jersey: Wiley. ISBN 0-471-24195-4.
15. FJ MacWilliams; NJA Sloane (1981). La teoría de los códigos de corrección de errores . Vol. 16 (3.ª ed.). Holanda Septentrional. ISBN 0-444-85009-0.
16. Spencer, Joel ; Florescu, Laura (2014). Asymptopia . Biblioteca matemática estudiantil. Vol. 71. AMS . p. 66. ISBN 978-1-4704-0904-3.OCLC 865574788  .
17. Spencer, Joel ; Florescu, Laura (2014). Asymptopia . Biblioteca matemática estudiantil. Vol. 71. AMS . p. 59. ISBN 978-1-4704-0904-3.OCLC 865574788  .
18. Véase, por ejemplo, Ash (1990, pág. 121) o Flum y Grohe (2006, pág. 427).
19. Munarini, Emanuele (2011), "Matrices de Riordan y sumas de números armónicos" (PDF) , Análisis Aplicable y Matemáticas Discretas , 5 (2): 176–200, doi :10.2298/AADM110609014M, MR  2867317.

Referencias

• Ash, Robert B. (1990) [1965]. Teoría de la información . Dover Publications, Inc. ISBN 0-486-66521-6.
• Benjamin, Arthur T. ; Quinn, Jennifer J. (2003). Pruebas que realmente cuentan: el arte de la prueba combinatoria . Dolciani Mathematical Expositions. Vol. 27. Asociación Matemática de Estados Unidos . ISBN 978-0-88385-333-7.
• Bryant, Victor (1993). Aspectos de la combinatoria . Cambridge University Press. ISBN 0-521-41974-3.
• Flum, Jörg; Grohe, Martín (2006). Teoría de la Complejidad Parametrizada. Saltador. ISBN 978-3-540-29952-3Archivado desde el original el 18 de noviembre de 2007. Consultado el 28 de agosto de 2017 .
• Fowler, David (enero de 1996). "La función de coeficiente binomial". The American Mathematical Monthly . 103 (1). Asociación Matemática de América: 1–17. doi :10.2307/2975209. JSTOR  2975209.
• Goetgheluck, P. (1987). "Cálculo de coeficientes binomiales". American Mathematical Monthly . 94 (4): 360–365. doi :10.2307/2323099. JSTOR  2323099.
• Graham, Ronald L. ; Knuth, Donald E. ; Patashnik, Oren (febrero de 1994). Matemáticas concretas: una base para la informática (2.ª ed.). Reading, MA, EE. UU.: Addison-Wesley Professional . pp. 154–155. ISBN 0-201-55802-5.Señor 1397498  .
• Gradshteyn, IS; Ryzhik, IM (2014). Tabla de integrales, series y productos (8.ª ed.). Academic Press. ISBN 978-0-12-384933-5.
• Grinshpan, AZ (2010), "Desigualdades ponderadas y binomios negativos", Advances in Applied Mathematics , 45 (4): 564–606, doi : 10.1016/j.aam.2010.04.004
• Higham, Nicholas J. (1998). Manual de redacción para las ciencias matemáticas . SIAM . pág. 25. ISBN. 0-89871-420-6.
• Knuth, Donald E. (1997). El arte de la programación informática, volumen 1: Algoritmos fundamentales(Tercera edición). Addison-Wesley. Págs. 52–74. ISBN 0-201-89683-4.
• Singmaster, David (1974). "Notas sobre coeficientes binomiales. III. Cualquier entero divide a casi todos los coeficientes binomiales". Journal of the London Mathematical Society . 8 (3): 555–560. doi :10.1112/jlms/s2-8.3.555.
• Shilov, GE (1977). Álgebra lineal . Publicaciones de Dover. ISBN 978-0-486-63518-7.
• Uspensky, James (1937), Introducción a la probabilidad matemática, McGraw-Hill

Enlaces externos

• "Coeficientes binomiales", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Andrew Granville (1997). "Propiedades aritméticas de los coeficientes binomiales I. Coeficientes binomiales módulo potencias primos". CMS Conf. Proc . 20 : 151–162. Archivado desde el original el 23 de septiembre de 2015. Consultado el 3 de septiembre de 2013 .

Este artículo incorpora material de los siguientes artículos de PlanetMath , que están licenciados bajo la Licencia Creative Commons Atribución/Compartir-Igual : Coeficiente binomial, Límites superior e inferior del coeficiente binomial, El coeficiente binomial es un número entero, Coeficientes binomiales generalizados.