Coeficiente binomial

Positive integers that occur as coefficients in the binomial theorem

"nCk" vuelve a dirigir aquí. Para otros usos, consulte NCK (desambiguación) .

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 anteriores.

Visualización de expansión binomial hasta la 4a 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 está indexado por un par de números enteros n ≥ k ≥ 0 y se escribe Es el coeficiente del término x ^k en la expansión polinomial de la potencia binomial (1 + x ) ⁿ , y está dado por la fórmula${\displaystyle {\tbinom {n}{k}}.}$

${\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!}{2!2!}}=6}$

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

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

Los coeficientes binomiales ocurren en muchas áreas de las matemáticas, y especialmente en la combinatoria . El símbolo generalmente se lee como " n elige 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 a saber y${\displaystyle {\tbinom {n}{k}}}$${\displaystyle {\tbinom {n}{k}}}$${\displaystyle {\tbinom {4}{2}}=6}$${\displaystyle \{1,2,3,4\},}$${\displaystyle \{1,2\}{\text{, }}\{1,3\}{\text{, }}\{1,4\}{\text{, }}\{2,3\}{\text{, }}\{2,4\}{\text{,}}}$${\displaystyle \{3,4\}.}$

Los coeficientes binomiales se pueden 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 se conocían siglos antes (ver el triángulo de Pascal ). La primera discusión detallada conocido de los coeficientes binomiales es en un comentario del siglo X, por Halayudha , sobre un antiguo sánscrito texto, Pingala 's Chandaḥśāstra . Aproximadamente en 1150, el matemático indio Bhaskaracharya dio una exposición de 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 , C ⁿ _k y C _{n , k} en todas las cuales la C significa combinaciones u opciones . Muchas calculadoras usan variantes de la notación C porque pueden representarla en una pantalla de una sola línea. De esta forma, los coeficientes binomiales se comparan fácilmente con k -permutaciones de n, escrito como P ( n , k ) , etc.

Definición e interpretaciones

k norte	0	1	2	3	4	⋯
0	1	0	0	0	0	⋯
1	1	1	0	0	0	⋯
2	1	2	1	0	0	⋯
3	1	3	3	1	0	⋯
4	1	4	6	4	1	⋯
⋮	⋮	⋮	⋮	⋮	⋮	⋱
Los primeros coeficientes binomiales en un triángulo de Pascal alineado a la izquierda

Para números naturales (tomados para incluir 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 ocurre (si k ≤ n ) en la fórmula binomial${\displaystyle {\tbinom {n}{k}}}$

${\displaystyle (x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{n-k}y^{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 formas, sin tener en cuenta el orden, en que se pueden elegir k objetos entre n objetos; más formalmente, el número de subconjuntos de k 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 an ), luego cada subconjunto dek í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 cualquier número natural n y k . Hay muchas otras interpretaciones combinatorias de coeficientes binomiales (problemas de conteo para los cuales la respuesta viene 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 viene dada por , mientras el número de formas de escribir donde cada a _i es un entero no negativo viene dado por${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$${\displaystyle k=a_{1}+a_{2}+\cdots +a_{n}}$${\displaystyle {\tbinom {n+k-1}{n-1}}}$. La mayoría de estas interpretaciones se consideran fácilmente equivalentes a contar k combinaciones.

Calcular el 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

${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}}$para todos los enteros tales que${\displaystyle n,k}$${\displaystyle 1\leq k\leq n-1,}$

con valores iniciales / límite

${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1}$ para todos los enteros ${\displaystyle n\geq 0.}$

La fórmula se deriva de considerar el conjunto {1, 2, 3, ..., n } y contar por separado (a) las agrupaciones de k -elementos que incluyen un elemento de conjunto particular, digamos " i ", en cada grupo (desde " i "ya está elegido para llenar un lugar en cada grupo, solo necesitamos elegir k  - 1 de los n  - 1) restantes y (b) todos los k -grupos que no incluyen" i "; esto enumera todas las k posibles combinaciones de n elementos. También se sigue 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 la construcción de Pascal triángulo , rodeado de espacios en blanco donde estarían los ceros, o los coeficientes triviales.${\displaystyle {\tbinom {n}{k}}=0}$

Fórmula multiplicativa

Un método más eficiente para calcular 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 se expresa como una potencia 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 formas 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 combinación k cuando se ignora el orden.${\displaystyle n^{\underline {k}}}$

Debido a la simetría del coeficiente binomial con respecto a k y n - k , el cálculo se puede optimizar estableciendo el límite superior del producto anterior al menor de k y n - k .

Fórmula factorial

Finalmente, aunque computacionalmente inadecuada, existe la forma compacta, que se usa a menudo en demostraciones y derivaciones, que hace 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 sigue de la fórmula multiplicativa anterior al multiplicar el numerador y el denominador por ( n - k )! ; como consecuencia, involucra muchos factores comunes al numerador y al denominador. Es menos práctico para el cálculo explícito (en el caso de que k sea ​​pequeño yn grande) a menos que primero se cancelen los factores comunes (en particular porque los valores factoriales crecen muy rápidamente). La fórmula muestra una simetría que es menos evidente en la fórmula multiplicativa (aunque lo es en las definiciones)

${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}\quad {\text{for }}\ 0\leq k\leq n,}$

( 1 )

lo que conduce a una rutina computacional 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}}.}$

Generalización y conexión con la serie binomial

Artículo principal: Serie binomial

La fórmula multiplicativa permite extender la definición de coeficientes binomiales ^[3] 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 son 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 puesta a 1), lo que justifica aún llamar a los coeficientes binomiales:${\displaystyle {\tbinom {\alpha }{k}}}$

${\displaystyle (1+X)^{\alpha }=\sum _{k=0}^{\infty }{\alpha \choose k}X^{k}.}$

( 2 )

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 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; el punto es que con esta definición todas las identidades sostienen que uno espera exponenciación , notablemente

${\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 número entero no negativo n , entonces todos los términos con k  >  n son cero y la serie infinita se convierte en una suma finita, recuperando así la fórmula binomial. Sin embargo, para otros valores de α , incluidos los números enteros negativos y los números racionales, la serie es realmente infinita.

Triángulo de Pascal

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

Artículos principales: triángulo de Pascal y regla de Pascal

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

${\displaystyle {n \choose k}+{n \choose k+1}={n+1 \choose k+1},}$

( 3 )

que puede usarse 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 :

0:									1
1:								1		1
2:							1		2		1
3:						1		3		3		1
4:					1		4		6		4		1
5:				1		5		10		10		5		1
6:			1		6		15		20		15		6		1
7:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

El número de fila n contiene los números para k = 0, ..., n . Se construye colocando primero 1 en las posiciones más externas y luego llenando cada posición interna con la suma de los dos números directamente arriba. Este método permite el cálculo rápido de coeficientes binomiales sin necesidad de fracciones o multiplicaciones. Por ejemplo, al mirar 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 la combinatoria , porque proporcionan fórmulas listas para ciertos problemas frecuentes de conteo:

• Hay formas de elegir k elementos de un conjunto de n elementos. Ver combinación .${\displaystyle {\tbinom {n}{k}}}$
• Hay formas de elegir k elementos de un conjunto de n elementos si se permiten repeticiones. Ver 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 de modo que no hay dos unos adyacentes. ^[4]${\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 número entero no negativo k , la expresión se puede simplificar y definir como un polinomio dividido por k !:${\displaystyle \scriptstyle {\binom {t}{k}}}$

${\displaystyle {\binom {t}{k}}={\frac {(t)_{k}}{k!}}={\frac {(t)_{k}}{(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 polinomio de grado k único 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 usando 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 campo de característica 0 (es decir, cualquier campo 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 de coeficientes binomiales. El coeficiente a _k es la k- ésima diferencia de la secuencia p (0), p (1), ..., p ( k ). Explícitamente, ^[5]${\textstyle \sum _{k=0}^{d}a_{k}{\binom {t}{k}}}$

${\displaystyle a_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}p(i).}$

( 4 )

Polinomios con valores enteros

Artículo principal: polinomio con valores enteros

Cada polinomio es número entero valora- : tiene un valor entero en todas las entradas de número entero . (Una forma de demostrar 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 se valora como números enteros. Por el contrario, ( 4 ) muestra que cualquier polinomio con valores enteros es una combinación lineal de números enteros de estos polinomios de coeficientes binomiales. De manera más general, para cualquier subanillo R de un campo característico 0 K , un polinomio en K [ t ] toma valores en R en todos los números enteros si y solo si es un R${\displaystyle {\tbinom {t}{k}}}$${\displaystyle t}$-Combinación lineal de polinomios de coeficientes binomiales.

Ejemplo

El polinomio con 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}}.}$

Identidades que involucran coeficientes binomiales

La fórmula factorial facilita relacionar coeficientes binomiales cercanos. Por ejemplo, si k es un número entero positivo yn es arbitrario, entonces

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

( 5 )

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

Además, lo siguiente puede resultar útil:

${\displaystyle {\binom {n}{h}}{\binom {n-h}{k}}={\binom {n}{k}}{\binom {n-k}{h}}.}$

Para n constante , tenemos la siguiente recurrencia:

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

Sumas de los coeficientes binomiales

La formula

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

( ∗∗ )

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 de potencias de {1, ..., n }). Sin embargo, estos subconjuntos también se pueden generar eligiendo o excluyendo sucesivamente cada elemento 1, ..., n ; el nLas 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

${\displaystyle \sum _{k=0}^{n}k{\binom {n}{k}}=n2^{n-1}}$

( 6 )

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 diferenciar con respecto a x (dos veces para este último) y luego sustituir x = y = 1 .

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

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

( 7 )

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

${\displaystyle \sum _{j=0}^{m}{\binom {m}{j}}^{2}={\binom {2m}{m}},}$

( 8 )

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

Otra forma de la identidad Chu-Vandermonde, que se aplica a cualquier número entero j , k y n que satisfaga 0 ≤ j ≤ k ≤ n , es

${\displaystyle \sum _{m=0}^{n}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n+1}{k+1}}.}$

( 9 )

La demostración es similar, pero usa 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 . Luego

${\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 proporciona una prueba combinatoria.

Multisecciones de sumas

Para enteros s y t Obra de tal manera que la serie multicorte 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 las pequeñas s , estas series tienen formas particularmente agradable; por ejemplo, ^[6]

${\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, ^[7] se puede usar nuevamente ( 3 ) y la inducción para mostrar que para k = 0, ..., n - 1 ,

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

con estuche especial ^[8]

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

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

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

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

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

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

( 10 )

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

Más generalmente 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 sigue inmediatamente aplicando ( 10 ) al polinomio en lugar de , y observando que todavía tiene un grado menor o igual que n , y que su coeficiente de grado n es d ⁿ a _n .${\displaystyle Q(x):=P(m+dx)}$${\displaystyle P(x)}$${\displaystyle Q(x)}$

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 que se demuestra por inducción en M .${\displaystyle {\frac {k-1}{k}}\sum _{j=0}^{\infty }{\frac {1}{\binom {j+x}{k}}}={\frac {1}{\binom {x-1}{k-1}}}}$${\displaystyle {\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 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 conteo doble , 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 marcando q elementos entre los seleccionados. El lado derecho cuenta lo mismo, porque hay formas de elegir un conjunto de q elementos para marcar, y elegir cuál 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 elementos k de [ n ]: los dos términos del lado derecho los agrupan en aquellos que contienen el elemento ny los que no.

La identidad ( 8 ) también tiene una prueba combinatoria. La identidad lee

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

Suponga que tiene cuadrados vacíos dispuestos en una fila y desea marcar (seleccionar) n de ellos. Hay formas de hacer esto. 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 an 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 uno denota por F ( i ) la secuencia de números de Fibonacci , indexados 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 prueba combinatoria. ^[10] Se puede demostrar por inducción que F ( n ) cuenta el número de formas en que una franja de cuadrados de n × 1 puede estar cubierta por baldosas de 2 × 1 y 1 × 1 . Por otro lado, si tal mosaico usa exactamente k de los mosaicos de 2 × 1 , entonces usa n - 2 k de los mosaicos de 1 × 1 , por lo que usa n - k mosaicos en total. Hay formas de ordenar estos mosaicos, y así sumar este coeficiente sobre todos los valores posibles de k${\displaystyle {\tbinom {n-k}{k}}}$ da la identidad.

Fila de suma de coeficientes

Ver también: Combinación § Número de k-combinaciones para todos los k

El número de k - combinaciones para todo k , , es la suma de la n º fila (contando desde 0) de los coeficientes binomiales. Estas combinaciones se enumeran por 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 .${\displaystyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$${\displaystyle 2^{n}-1}$

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, de manera más general,

${\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 una , 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}}}$

Estos se pueden probar usando la fórmula de Euler para convertir funciones trigonométricas en exponenciales complejas, expandiendo usando el teorema del binomio e integrando término por término.

Generando funciones

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

Artículos principales: teorema de Kummer y teorema de Lucas

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 divisoria es igual a p ^c , donde c es el número de acarreos cuando m y n se añaden en la base p . De manera equivalente, el exponente de un primo p en es igual al número de enteros no negativos j tal que la parte fraccionaria de k / p ^j es mayor que la parte fraccionaria de n /${\displaystyle {\tbinom {m+n}{m}}}$${\displaystyle {\tbinom {n}{k}}}$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 tal que s < p ^r . Sin embargo, esto no es cierto para las potencias superiores de p : por ejemplo, 9 no divide .${\displaystyle {\tbinom {n}{k}}}$${\displaystyle {\tbinom {p^{r}}{s}}}$${\displaystyle {\tbinom {9}{6}}}$

Un resultado algo sorprendente de David Singmaster (1974) es que cualquier número entero divide casi todos los coeficientes binomiales. Más precisamente, fije un número entero d y sea f ( N ) el número de coeficientes binomiales con n < N tales que d divide . Luego${\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 va a 1.${\displaystyle {\tbinom {n}{k}}}$

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

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

${\displaystyle {\binom {n+k}{k}}}$es un múltiplo de .${\displaystyle {\frac {{\text{lcm}}(n,n+1,\ldots ,n+k)}{n\cdot {\text{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 se divide

${\displaystyle {\binom {p}{k}}={\frac {p\cdot (p-1)\cdots (p-k+1)}{k\cdot (k-1)\cdots 1}}}$para todo 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 , este solo puede ser el caso cuando ( n - 1) ( n - 2) × ... × ( n - p + 1) es divisible por p . Pero n es divisible por p , entonces p no divide n - 1, n - 2, ..., n - p + 1 y porque pes primo, sabemos que p no divide ( n - 1) ( n - 2) × ... × ( n - p + 1) por lo que el numerador no puede ser divisible por n .

Límites y fórmulas asintóticas

Los siguientes límites se mantienen para todos los valores de n y k tales que 1 ≤  k  ≤  n :${\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}}$.

La primera desigualdad se deriva del hecho de que

${\displaystyle {n \choose k}={\frac {n}{k}}\cdot {\frac {n-1}{k-1}}\cdots {\frac {n-(k-1)}{1}}}$

y cada uno de estos términos en este producto es . Se puede hacer un argumento similar para mostrar la segunda desigualdad. La desigualdad estricta final es equivalente a , eso está claro ya que el RHS es un término de la serie exponencial .${\displaystyle k}$${\displaystyle \geq {\frac {n}{k}}}$${\displaystyle e^{k}>k^{k}/k!}$${\displaystyle e^{k}=\sum _{j=0}^{\infty }k^{j}/j!}$

De las propiedades de divisibilidad podemos inferir que

${\displaystyle {\frac {{\text{lcm}}(n-k,\ldots ,n)}{(n-k)\cdot {\text{lcm}}({\binom {k}{0}},\ldots ,{\binom {k}{k}})}}\leq {\binom {n}{k}}\leq {\frac {{\text{lcm}}(n-k,\ldots ,n)}{n-k}}}$,

donde se pueden lograr ambas igualdades. ^[11]

Tanto n como k grandes

La aproximación de Stirling produce la siguiente aproximación, válida cuando ambos tienden al infinito:${\displaystyle n,k}$

${\displaystyle {n \choose 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 unen los factoriales, ligeras variantes en la aproximación asintótica anterior dan límites exactos.

En particular, cuando es suficientemente grande:${\displaystyle n}$

${\displaystyle {2n \choose n}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}}$y ${\displaystyle {\sqrt {n}}{2n \choose n}\geq 2^{2n-1}}$

y, en general, para m  ≥ 2 yn  ≥ 1, ^{[ ¿por qué? ]}

${\displaystyle {\sqrt {n}}{mn \choose n}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}}$

Otra aproximación asintótica útil para cuando ambos números crecen al mismo ritmo ^{[ aclaración necesaria ]} es

${\displaystyle \log _{2}{n \choose k}\sim nH(k/n)=k\log _{2}(n/k)+(n-k)\log _{2}(n/(n-k))}$

donde es la función de entropía binaria .${\displaystyle H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)}$

Si n es grande y k es lineal en n , existen varias estimaciones asintóticas precisas para el coeficiente binomial . Por ejemplo, si entonces${\displaystyle {\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)}}$

donde d = n - 2 k . ^[12]

n mucho más grande que k

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 de nuevo o es la notación o pequeña . ^[13]

Sumas de coeficientes binomiales

Se puede obtener un límite superior simple y aproximado para la suma de coeficientes binomiales usando el teorema del binomio :

${\displaystyle \sum _{i=0}^{k}{n \choose i}\leq \sum _{i=0}^{k}n^{i}\cdot 1^{k-i}\leq (1+n)^{k}}$

Los límites más precisos están dados por

${\displaystyle {\frac {1}{\sqrt {8n\epsilon (1-\epsilon )}}}\cdot 2^{H(\epsilon )\cdot n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\epsilon )\cdot n}.}$

que es válido para todos los enteros con . ^[14]${\displaystyle n>k\geq 1}$${\displaystyle \epsilon \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

${\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 {(1+{\frac {1}{j}})^{-z-1}}{1-{\frac {z+1}{j}}}}}$

que produce las fórmulas asintóticas

${\displaystyle {z \choose k}\approx {\frac {(-1)^{k}}{\Gamma (-z)k^{z+1}}}\qquad \mathrm {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)}$

como .${\displaystyle k\to \infty }$

Este comportamiento asintótico está contenido en la aproximación

${\displaystyle {z+k \choose k}\approx {\frac {e^{z(H_{k}-\gamma )}}{\Gamma (z+1)}}}$

también. (Aquí está el número armónico k -ésimo y es la constante de Euler-Mascheroni ).${\displaystyle H_{k}}$${\displaystyle \gamma }$

Además, la fórmula asintótica

${\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}}$

es cierto, cuando sea y para algún número complejo .${\displaystyle k\to \infty }$${\displaystyle j/k\to x}$${\displaystyle x}$

Generalizaciones

Generalización a multinomios

Artículo principal: teorema multinomial

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 sobre 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 Taylor

Usando 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 con n = 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 es válida 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 usando 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}^{m}{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 marcados, los coeficientes de conexión representan el número de formas de asignar m + n - k etiquetas a un par de objetos-de combinatorias marcadas peso m y n , respectivamente, que han tenido sus primera k etiquetas identificadas, o pegadas entre sí para obtener un nuevo objeto combinatorio etiquetado de peso m + n - k. (Es decir, separar las etiquetas en tres porciones para aplicar a la parte pegada, la parte despegada del primer objeto y la parte despegada del segundo objeto). En este sentido, los coeficientes binomiales son para series generadoras exponenciales qué factoriales descendentes son a series generadoras ordinarias.

El producto de todos los coeficientes binomiales en el n º fila del triángulo de Pascal está dada por la fórmula:

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

Descomposición de fracciones parciales

La descomposición de la fracción parcial del recíproco está 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

Artículo principal: Serie binomial

La serie binomial de Newton, que lleva el nombre de Sir Isaac Newton , es una generalización del teorema del binomio a 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 mostrando 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}}$

Está aplicado.

Coeficiente binomial multiset (ascendente)

Artículo principal: Multichoose § Contando multijuegos

Los coeficientes binomiales cuentan subconjuntos de tamaño prescrito de un conjunto dado. Un problema combinatorio relacionado es contar conjuntos múltiples 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 de conjuntos múltiples ; ^{[15] se} indica el número de formas de "elegir de forma múltiple" (es decir, elegir con reemplazo) k elementos de un conjunto de n elementos .${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)}$

Para evitar la ambigüedad y la confusión con n' s denotación principal en este artículo,
dejar que f = n = r + ( k - 1) y r = f - ( k - 1).

Los coeficientes de conjuntos múltiples se pueden expresar en términos de coeficientes binomiales mediante la regla

${\displaystyle {\binom {f}{k}}=\left(\!\!{\binom {r}{k}}\!\!\right)={\binom {r+k-1}{k}}.}$

Una posible caracterización alternativa de esta identidad es la siguiente: Podemos definir el factorial descendente como

${\displaystyle (f)_{k}=f^{\underline {k}}=(f-k+1)\cdots (f-3)\cdot (f-2)\cdot (f-1)\cdot f}$,

y el factorial ascendente correspondiente como

${\displaystyle {\color {white}{\big |}}r^{(k)}=\,r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1)}$;

así por ejemplo,

${\displaystyle 17\cdot 18\cdot 19\cdot 20\cdot 21=(21)_{5}=21^{\underline {5}}=17^{\overline {5}}=17^{(5)}}$.

Entonces los coeficientes binomiales se pueden escribir como

${\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}}}$,

mientras que el coeficiente multiset correspondiente se define reemplazando el factorial descendente por el ascendente:

${\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 negativos n

Coeficientes binomiales C  ( n , k ) extendidos para n negativos y fraccionarios , ilustrados con un binomio simple . Se puede observar que el triángulo de Pascal se rota y los términos alternativos se niegan. 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 vienen dados por coeficientes multiset 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 valiosos reales o complejos

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} (x-y+1,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};}$

es má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 ( Fowler 1996 ). En particular, muchas identidades binomiales fallan: pero para n positivo (tan negativo). El comportamiento es bastante complejo, y marcadamente diferente en varios octantes (es decir, con respecto a la x y Y ejes y la línea ), con el comportamiento de negativos x que tienen singularidades en valores enteros negativos y un tablero de ajedrez de las regiones positivas y negativas:${\displaystyle \textstyle {{n \choose m}={n \choose n-m}}}$${\displaystyle \textstyle {{-n \choose m}\neq {-n \choose -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 es de nuevo alternativamente muy grande positivo y negativo, pero en una cuadrícula cuadrada.${\displaystyle 0>x>y}$
• en el octante está cerca de cero, excepto cerca de las singularidades.${\displaystyle -1>y>x+1}$

Generalización a q -series

El coeficiente binomial tiene una generalización análoga q conocida como coeficiente binomial gaussiano .

Generalización a infinitos cardenales

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

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

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 los cardinales finitos, esta definición coincide con la definición estándar del coeficiente binomial.${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle {\alpha \choose \beta }}$

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

Coeficiente binomial en lenguajes de programación

La notación es conveniente para la escritura a mano, pero inconveniente para máquinas de escribir y terminales de computadora . Muchos lenguajes de programación no ofrecen un estándar subrutina para calcular el coeficiente binomial, pero por ejemplo tanto en el lenguaje de programación APL y la (relacionado) lenguaje de programación J uso el signo de exclamación: . El coeficiente binomial se implementa en SciPy como scipy.special.comb . ^[dieciséis]${\displaystyle {n \choose k}}$k ! n

Implementaciones ingenuas de la fórmula factorial, como el siguiente fragmento en Python :

from  math  import  factorial def  binomial_coefficient ( n :  int ,  k :  int )  ->  int :  return  factorial ( n )  //  ( factorial ( k )  *  factorial ( n  -  k ))

son muy lentos e inútiles para calcular factoriales de números muy elevados (en lenguajes como C o Java sufren errores de desbordamiento por este motivo). Una implementación directa de la fórmula multiplicativa funciona bien:

def  binomial_coefficient ( n :  int ,  k :  int )  ->  int :  si  k  <  0  o  k  >  n :  devuelve  0  si  k  ==  0  o  k  ==  n :  devuelve  1  k  =  min ( k ,  n  -  k )  # Aproveche la simetría  c  =  1  para  i  en el  rango (k ):  c  =  c  *  ( n  -  i )  /  ( i  +  1 )  return  c

(En Python, el rango (k) produce una lista de 0 a k – 1).

La regla de Pascal proporciona una definición recursiva que también se puede implementar en Python, aunque es menos eficiente:

def  binomial_coefficient ( n :  int ,  k :  int )  ->  int :  si  k  <  0  o  k  >  n :  devuelve  0  si  k  >  n  -  k :  # Aprovecha la simetría  k  =  n  -  k  si  k  ==  0  o  n  <=  1 :  return  1  return  binomial_coefficient ( n  - 1 ,  k )  +  coeficiente_binomial ( n  -  1 ,  k  -  1 )

El ejemplo mencionado anteriormente también se puede escribir en estilo funcional. El siguiente ejemplo de esquema usa la definición recursiva

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

La aritmética racional se puede evitar fácilmente mediante la división de enteros

${\displaystyle {n \choose k+1}=\left[(n-k){n \choose k}\right]\div (k+1)}$

La siguiente implementación usa todas estas ideas

( define ( binomial  n  k ) ;; Función auxiliar para calcular C (n, k) mediante recursividad hacia adelante  ( define ( binomial-iter  n  k  i  prev )  ( if ( > = i  k )  prev  ( binomial-iter  n  k  ( + i  1 )  ( / ( * ( - n  i )  anterior )  ( + i  1 )))));; Utilice la propiedad de simetría C (n, k) = C (n, nk)  ( if ( < k  ( -  n  k ))  ( binomial-iter  n  k  0  1 )  ( binomial-iter  n  ( - n  k )  0  1 )) )

Al calcular en un idioma con números enteros de longitud fija, la multiplicación por puede desbordarse incluso cuando el resultado encaja. El desbordamiento se puede evitar dividiendo primero y fijando el resultado usando el resto:${\displaystyle \textstyle {n \choose k+1}=\left[(n-k){n \choose k}\right]\div (k+1)}$${\displaystyle (n-k)}$

${\displaystyle {n \choose k+1}=\left[\textstyle {n \choose k}\div (k+1)\right](n-k)+{\left[{n \choose k}\ \mathrm {mod} \ (k+1)\right](n-k) \over (k+1)}}$

Implementación en lenguaje C:

#include  <limits.h> binomio largo  unsigned ( unsigned long n , unsigned long k ) { unsigned long c = 1 , i ;              if  ( k  >  n - k )  // aprovecha la simetría  k  =  n - k ;  for  ( i  =  1 ;  i  <=  k ;  i ++ ,  n - )  {  if  ( c / i  >  UINT_MAX / n )  // devuelve 0 en caso de desbordamiento  return  0 ;  c  =  c  /  i  *  n  +  c  %  i  *  n  /  i ;  // divide c * n / i en (c / i * i + c% i) * n / i  }  return  c ; }

Otra forma de calcular el coeficiente binomial cuando se utilizan números grandes es reconocer que

${\displaystyle {n \choose k}={\frac {n!}{k!\,(n-k)!}}={\frac {\Gamma (n+1)}{\Gamma (k+1)\,\Gamma (n-k+1)}}=\exp(\ln \Gamma (n+1)-\ln \Gamma (k+1)-\ln \Gamma (n-k+1)),}$

donde denota el logaritmo natural de la función gamma en . Es una función especial que se calcula fácilmente y es estándar en algunos lenguajes de programación como el uso de log_gamma en Maxima , LogGamma en Mathematica , gammaln en MATLAB y el módulo SciPy de Python , lngamma en PARI / GP o lgamma en C, R , ^[17] y Julia . El error de redondeo puede hacer que el valor devuelto no sea un número entero.${\displaystyle \ln \Gamma (n)}$${\displaystyle n}$

Ver también

• Transformada 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 (véase Knuth (1997) ).
3. Ver ( Graham, Knuth & Patashnik 1994 ), que también definepara. Las generalizaciones alternativas, como dos argumentos con valores reales o complejos que utilizan la función Gamma, asignan valores distintos de cero afor, pero esto hace que la mayoría de las identidades de coeficientes binomiales fallen y, por lo tanto, no se utilizan ampliamente en la mayoría de las definiciones. Una de estas opciones de valores distintos de cero conduce al estéticamente agradable "molino de viento de Pascal" en Hilton, Holton y Pedersen, Reflexiones matemáticas: en una habitación con muchos espejos , 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}$
4. Muir, Thomas (1902). "Nota sobre combinaciones seleccionadas" . Actas de la Royal Society of Edinburgh .
5. Esto puede verse como un análogo discreto del teorema de Taylor . Está estrechamente relacionado con el polinomio de Newton . Las sumas alternas de esta forma se pueden expresar como la integral de Nörlund-Rice .
6. Gradshteyn y Ryzhik (2014 , págs. 3-4).
7. 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, fórmula directa) para la suma parcial de coeficientes binomiales  .
8. ver inducción desarrollada en la ecuación (7) p. 1389 en Aupetit, Michael (2009), "Partición múltiple casi homogénea con un generador determinista", Neurocomputing , 72 (7-9): 1379-1389, doi : 10.1016 / j.neucom.2008.12.024 , ISSN 0925-2312 .
9. Ruiz, Sebastian (1996). "Una identidad algebraica que conduce al teorema de Wilson". La Gaceta Matemática . 80 (489): 579–582. arXiv : matemáticas / 0406086 . doi : 10.2307 / 3618534 . JSTOR 3618534 . 
10. Benjamin y Quinn 2003 , págs. 4-5
11. Farhi, Bakir (2007). "Límites inferiores no triviales para el mínimo común múltiplo de alguna secuencia finita de enteros". Revista de teoría de números . 125 (2): 393–411. arXiv : 0803.0290 . doi : 10.1016 / j.jnt.2006.10.017 .
12. Spencer, Joel ; Florescu, Laura (2014). Asimtopía . Biblioteca de matemáticas para estudiantes. 71 . AMS . pag. 66. ISBN 978-1-4704-0904-3. OCLC  865574788 .
13. Spencer, Joel ; Florescu, Laura (2014). Asimtopía . Biblioteca de matemáticas para estudiantes. 71 . AMS . pag. 59. ISBN 978-1-4704-0904-3. OCLC  865574788 .
14. ver, por ejemplo, Ash (1990 , p. 121) o Flum & Grohe (2006 , p. 427).
15. 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  .
16. "scipy.special.comb" . Guía de referencia de SciPy . 2021-02-18 . Consultado el 2 de marzo de 2021 .
17. Bloomfield, Victor A. (2016). Uso de R para análisis numérico en ciencia e ingeniería . Prensa CRC. pag. 74. ISBN 978-1-4987-8662-1.

Referencias

• Ash, Robert B. (1990) [1965]. Teoría de la información . Publicaciones de Dover, Inc. ISBN 0-486-66521-6.
• Benjamin, Arthur T .; Quinn, Jennifer J. (2003). Pruebas que realmente cuentan: el arte de la prueba combinatoria . Exposiciones Matemáticas Dolciani. 27 . Asociación Matemática de América . ISBN 978-0-88385-333-7.
• Bryant, Víctor (1993). Aspectos de combinatoria . Prensa de la Universidad de Cambridge. ISBN 0-521-41974-3.
• Flum, Jörg; Grohe, Martin (2006). Teoría de la complejidad parametrizada . Saltador. ISBN 978-3-540-29952-3.
• Fowler, David (enero de 1996). "La función del coeficiente binomial". The American Mathematical Monthly . Asociación Matemática de América. 103 (1): 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 (1994). Matemáticas concretas (Segunda ed.). Addison-Wesley. pp.  153 -256. ISBN 0-201-55802-5.
• Gradshteyn, IS; Ryzhik, MI (2014). Tabla de integrales, series y productos (8ª ed.). Prensa académica. 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 . pag. 25 . ISBN 0-89871-420-6.
• Knuth, Donald E. (1997). El arte de la programación informática, volumen 1: algoritmos fundamentales(Tercera ed.). Addison-Wesley. págs. 52–74. ISBN 0-201-89683-4.
• Maestro de canto, David (1974). "Notas sobre coeficientes binomiales. III. Cualquier número entero divide casi todos los coeficientes binomiales". Revista de la Sociedad Matemática de Londres . 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.

Enlaces externos

• "Coeficientes binomiales" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Andrew Granville (1997). "Propiedades aritméticas de coeficientes binomiales I. Coeficientes binomiales módulo primos potencias" . Conf. CMS 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 bajo la licencia Creative Commons Attribution / Share-Alike : Coeficiente binomial , Límites superior e inferior del coeficiente binomial , El coeficiente binomial es un número entero , Coeficientes binomiales generalizados .