Coeficiente binomial - Binomial coefficient

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

Por ejemplo, la cuarta potencia de 1 + x es

${\ displaystyle {\ begin {alineado} (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 {alineado}}}$

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, aunque los números se conocían siglos antes (véase 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ī . ${\ 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 o elecciones . 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 , escritas 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 ^ {nk} 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 ), 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 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 . La mayoría de estas interpretaciones se consideran fácilmente 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}}}$

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

Debido a la simetría del coeficiente binomial con respecto a k y n - k , el cálculo puede optimizarse 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! \, (nk)!}} \ quad {\ text {para}} \ 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} {nk}} \ 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 {nk}} / (nk)! & {\ Text {if}} \ k> {\ frac {n} {2}} \ end {cases}}.}$

Generalización y conexión a la serie binomial

La fórmula multiplicativa permite extender la definición de coeficientes binomiales 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 {para}} k \ in \ mathbb {N} { \ text {y arbitrario}} \ 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 \ elige 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 {y}} \ 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 enteros negativos y los números racionales, la serie es realmente infinita.

Triángulo de Pascal

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

${\ Displaystyle {n \ elija k} + {n \ elija k + 1} = {n + 1 \ elija 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.${\ 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) ^ {nk} \ !.}$

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

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) ^ {ki-1}} {ki}} {\ 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, ${\ textstyle \ sum _ {k = 0} ^ {d} a_ {k} {\ binom {t} {k}}}$

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

( 4 )

Polinomios 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 sobre k , usando la identidad de Pascal ). Por lo tanto, cualquier combinación lineal entera de polinomios de coeficientes binomiales también tiene valores 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. Más generalmente, 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 una combinación R lineal de polinomios de coeficientes binomiales. ${\ Displaystyle {\ tbinom {t} {k}}}$${\ Displaystyle t}$

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 {nh} {k}} = {\ binom {n} {k}} {\ binom {nk} {h}} = {\ binom {n } {h + k}} {\ binom {h + 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 ; 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

${\ 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 {nm} {kj}} = {\ 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 \ 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 {nm} {kj}} = {\ 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 {nk} {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,

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

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

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

${\ Displaystyle {\ binom {n} {0}} + {\ binom {n} {4}} + {\ binom {n} {8}} + \ cdots = {\ frac {1} {2}} \ izquierda (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}} \ izquierda (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}} \ izquierda (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}} \ izquierda (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, se puede volver a utilizar ( 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 estuche especial

${\ 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 que para cualquier polinomio P ( x ) de grado menor que n ,

${\ 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 (nj) = 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 + (nj) d) = d ^ {n} n! a_ {norte}}$

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 ^ {nq} {\ 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 de elegir cuál de los elementos restantes de [ n ] también pertenecen al subconjunto. ${\ Displaystyle {\ tbinom {n} {q}}}$${\ Displaystyle 2 ^ {nq}}$

En la identidad de Pascal

${\ Displaystyle {n \ elija k} = {n-1 \ elija k-1} + {n-1 \ elija 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 nk}$

${\ Displaystyle \ sum _ {k = 0} ^ {n} {\ binom {n} {k}} {\ binom {n} {nk}} = {\ 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

tiene la siguiente prueba combinatoria. 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 cubrirse con 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, por lo que la suma de este coeficiente sobre todos los valores posibles de k da la identidad. ${\ Displaystyle {\ tbinom {nk} {k}}}$

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

La identidad de Dixon

La identidad de Dixon es

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

o, de manera más general,

${\ Displaystyle \ sum _ {k = -a} ^ {a} (- 1) ^ {k} {a + b \ elige a + k} {b + c \ elige b + k} {c + a \ elige 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 {de lo contrario}} \ 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, & {\ texto {de lo contrario}} \ end {casos}}}$

Estos se pueden demostrar 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.

Congruencias

Si n es primo, entonces

${\ Displaystyle {\ binom {n-1} {k}} \ equiv (-1) ^ {k} \ mod n}$

para cada k con 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 primos entre sí a n . ${\ Displaystyle 0 \ leq k \ leq n-1.}$

De hecho, tenemos

${\ Displaystyle {\ binom {n-1} {k}} = {(n-1) (n-2) \ cdots (nk) \ over 1 \ cdot 2 \ cdots k} = \ prod _ {i = 1 } ^ {k} {ni \ sobre i} \ equiv \ prod _ {i = 1} ^ {k} {- i \ sobre 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 \ elige 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 \ elige 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 \ elige 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 \ elige k} x ^ {k} y ^ {n} = {\ frac {1} {1-xy}}.}$

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 \ elige 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 , de manera 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 tal que s < p ^r . Sin embargo, esto no es cierto para las potencias superiores de p : por ejemplo, 9 no divide . ${\ 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 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:

${\ 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 número 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 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 , 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 como p es 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 \ elige 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 \ elige 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}} (nk, \ ldots, n)} {(nk) \ cdot {\ text {lcm}} ({\ binom {k} {0}}, \ ldots , {\ binom {k} {k}})}} \ leq {\ binom {n} {k}} \ leq {\ frac {{\ text {lcm}} (nk, \ ldots, n)} {nk }}}$,

donde se pueden lograr ambas igualdades.

Los siguientes límites son útiles en la teoría de la información:

${\ Displaystyle {\ frac {1} {n + 1}} 2 ^ {nH (k / n)} \ leq {n \ elige k} \ leq 2 ^ {nH (k / n)}}$

donde es la

función de entropía binaria . Puede ajustarse aún más para ${\ Displaystyle H (p) = - p \ log _ {2} (p) - (1-p) \ log _ {2} (1-p)}$

${\ Displaystyle {\ sqrt {\ frac {n} {8k (nk)}}} 2 ^ {nH (k / n)} \ leq {n \ elija k} \ leq {\ sqrt {\ frac {n} { \ pi k (nk)}}} 2 ^ {nH (k / n)}.}$

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 \ elija k} \ sim {\ sqrt {n \ over 2 \ pi k (nk)}} \ cdot {n ^ {n} \ over k ^ {k} (nk) ^ {nk}} }$

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, uno tiene ${\ Displaystyle n}$

${\ Displaystyle {2n \ elige n} \ sim {\ frac {2 ^ {2n}} {\ sqrt {n \ pi}}}}$ y ${\ Displaystyle {\ sqrt {n}} {2n \ elija n} \ geq 2 ^ {2n-1}}$

y, más generalmente, para m  ≥ 2 yn  ≥ 1,

${\ Displaystyle {\ sqrt {n}} {mn \ elija 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 ${\ 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 .

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 nuevamente o es la notación o pequeña .

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 \ elija i} \ leq \ sum _ {i = 0} ^ {k} n ^ {i} \ cdot 1 ^ {ki} \ 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},}$

válido para todos los enteros con . ${\ 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 \ elige k} = {- z + k-1 \ elige 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 \ elige k} \ approx {\ frac {(-1) ^ {k}} {\ Gamma (-z) k ^ {z + 1}}} \ qquad \ mathrm {y} \ qquad { z + k \ elija k} = {\ frac {k ^ {z}} {\ Gamma (z + 1)}} \ left (1 + {\ frac {z (z + 1)} {2k}} + { \ mathcal {O}} \ left (k ^ {- 2} \ right) \ right)}$

como . ${\ Displaystyle k \ a \ infty}$

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

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

así como. (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 \ elige j} {k \ elige j}} \ to \ left (1 - {\ frac {j} {k}} \ right) ^ {- z} \ quad {\ texto {y}} \ quad {\ frac {j \ elija jk} {jz \ elija jk}} \ to \ left ({\ frac {j} {k}} \ right) ^ {z}}$

es cierto, cuando sea y para algún número complejo . ${\ Displaystyle k \ a \ 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 \ elige 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 \ elija k_ {1}, k_ {2}} = {n \ elija k_ {1}, n-k_ {1}} = {n \ elija k_ {1}} = {n \ elija 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 \ elige k_ {1}, k_ {2}, \ ldots, k_ {r}} = {n-1 \ elige k_ {1} -1, k_ {2}, \ ldots, k_ {r }} + {n-1 \ elija k_ {1}, k_ {2} -1, \ ldots, k_ {r}} + \ ldots + {n-1 \ elija k_ {1}, k_ {2}, \ ldots, k_ {r} -1}}$

y simetría:

${\ Displaystyle {n \ elija k_ {1}, k_ {2}, \ ldots, k_ {r}} = {n \ elija 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

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 {alineado} {z \ elige 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} \ elija ji} {\ frac {s_ {k + ij, i}} {(k + ij)!}} \\ & = \ sum _ {i = 0} ^ {k} (z-z_ {0}) ^ {i} \ sum _ {j = i} ^ {k} z_ {0} ^ {ji} {j \ elija i} {\ frac {s_ {k, j}} {k!}}. \ end {alineado}}}$

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 se muestra 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 \ elija m} {z \ elija n} = \ sum _ {k = 0} ^ {m} {m + nk \ elija k, mk, nk} {z \ elija m + nk},}$

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 para 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 fracción parcial

La descomposición de la

fracción parcial del recíproco está dada por

${\ Displaystyle {\ frac {1} {z \ elige n}} = \ sum _ {i = 0} ^ {n-1} (- 1) ^ {n-1-i} {n \ elige i} { \ frac {ni} {zi}}, \ qquad {\ frac {1} {z + n \ elija n}} = \ sum _ {i = 1} ^ {n} (- 1) ^ {i-1} {n \ elija 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 \ elige n} z ^ {n} = 1 + {\ alpha \ elige 1} z + {\ alpha \ elija 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 \ elige n} z ^ {n }}$

donde la identidad

${\ Displaystyle {n \ elige k} = (- 1) ^ {k} {kn-1 \ elige 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 ; 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 {blanco} {\ 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 alternos se niegan. El caso n  = −1 da la serie de Grandi .

Para cualquier n ,

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

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

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 \ elige 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 \ elige y} = {\ frac {\ sin (y \ pi)} {\ sin (x \ pi)}} {- y-1 \ elige -x-1} = {\ frac {\ sin ((xy) \ pi)} {\ sin (x \ pi)}} {yx-1 \ elige y};}$

es más,

${\ Displaystyle {x \ elige y} \ cdot {y \ elige x} = {\ frac {\ sin ((xy) \ pi)} {(xy) \ 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 \ elige m} = {n \ elige nm}}}$${\ Displaystyle \ textstyle {{-n \ elige m} \ neq {-n \ elige -nm}}}$${\ 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 \ elige \ 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}$

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 . ${\ Displaystyle {n \ elige 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:
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    k = min(k, n - k)  # Take advantage of symmetry
    c = 1
    for i in range(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:
    if k < 0 or k > n:
        return 0
    if k > n - k:  # Take advantage of symmetry
        k = n - k
    if k == 0 or n <= 1:
        return 1
    return binomial_coefficient(n - 1, k) + binomial_coefficient(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 \ elige k + 1} = {\ frac {nk} {k + 1}} {n \ elige k}}$

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

${\ Displaystyle {n \ elige k + 1} = \ left [(nk) {n \ elige k} \ right] \ div (k + 1)}$

La siguiente implementación usa todas estas ideas

(define (binomial n k)
;; Helper function to compute C(n,k) via forward recursion
  (define (binomial-iter n k i prev)
    (if (>= i k)
      prev
     (binomial-iter n k (+ i 1) (/ (* (- n i) prev) (+ i 1)))))
;; Use symmetry property C(n,k)=C(n, n-k)
  (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 \ elige k + 1} = \ left [(nk) {n \ elige k} \ right] \ div (k + 1)}$${\ Displaystyle (nk)}$

${\ Displaystyle {n \ elige k + 1} = \ left [\ textstyle {n \ elige k} \ div (k + 1) \ right] (nk) + {\ left [{n \ elige k} \ \ mathrm {mod} \ (k + 1) \ right] (nk) \ over (k + 1)}}$

Implementación en lenguaje C:

#include <limits.h>

unsigned long binomial(unsigned long n, unsigned long k) {
  unsigned long c = 1, i;
  
  if (k > n-k) // take advantage of symmetry
    k = n-k;
  
  for (i = 1; i <= k; i++, n--) {
    if (c/i >= ULONG_MAX/n) // return 0 on potential overflow
      return 0;
      
    c = c / i * n + c % i * n / i;  // split c * n / i into (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 \ elige k} = {\ frac {n!} {k! \, (nk)!}} = {\ 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 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

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 sujetos a 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 .