Coeficiente binomial

Compartir Imprimir Citar

Todas las posibles combinaciones para n en k, cuando n = 4

Un coeficiente binomial es cualquier número entero positivo que se presenta como coeficiente durante la expansión algebraica de las potencias de un binomio (teorema del binomio). En términos más sencillos el coeficiente binomial es el número de veces (coeficiente) que puede encontrarse un subconjunto de k elementos, dentro de un conjunto exponencial de n de elementos. Se representan comúnmente con la notación (n, k), donde n y k son enteros que cumplen con la condición n ≥ k ≥ 0. Los coeficientes binomiales son especialmente relevante en áreas de las matemáticas como la combinatoria y el álgebra.

Por ejemplo, el coeficiente binomial (n, k) "n en k" es el coeficiente del término x^k en la expansión del binomio (1 + x )ⁿ. Para calcularlo, se utiliza la fórmula:

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

Esta fórmula se puede expresar de manera más compacta utilizando la notación factorial:

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

Por ejemplo, para determinar el número de combinaciones de 2 elementos en un conjunto de 4 elementos, se tiene que la representación exponencial de un conjunto expandido a la cuarta potencia es ( $1 + x$ )⁴, por lo que obtenemos:

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

De donde, el coeficiente binomial ${displaystyle {tbinom {4}{2}}={tfrac {4times 3}{2times 1}}={tfrac {4!}{2!2!}}=6}$ es el coeficiente del término x en su expansión a la segunda potencia, $x 2$ . Por lo que existen 6 combinaciones de 4 elementos tomados de a 2.

Una forma interesante de visualizar los coeficientes binomiales es a través del triángulo de Pascal. Este arreglo triangular se forma colocando los números ${displaystyle {tbinom {n}{0}},{tbinom {n}{1}},ldots{tbinom {n}{n}}}$ en filas sucesivas para $n=0,1,2,ldots$ El triángulo de Pascal cumple con la relación de recurrencia:

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

El término (n, k) se lee comúnmente como "n tomado k" o "n en k", ya que representa el número de formas posibles de seleccionar un subconjunto de k elementos dentro de un conjunto dado de n elementos. Por ejemplo, existen ${displaystyle {tbinom {4}{2}}=6}$ maneras de elegir 2 elementos del conjunto {1,2,3,4}. Los coeficientes binomiales pueden generalizarse para cualquier número complejo z y cualquier entero k ≥ 0, manteniendo muchas de sus propiedades en esta forma más general.

HSD

Historia y notación

Andreas von Ettingshausen presentó la notación ${tbinom {n}{k}}$ en 1826, aunque los números fueron conocidos siglos antes (ver el triángulo de Pascal). La primera discusión detallada conocida de los coeficientes binomiales está en un comentario del siglo X, por Halayudha, sobre un antiguo texto sánscrito, el de Pingala Chandaḥśāstra. La segunda descripción más temprana de los coeficientes binomiales es dada por Al-Karaji. En alrededor de 1150, el matemático indio Bhaskaracharya dio una exposición de coeficientes binomiales en su libro Līlāvatī.

Las notaciones alternativas incluyen $C (n, k)$ , $n C k$ , ⁿC_k, $C k n$ , $C n k$ y $C n, k$ en todos los cuales la $C$ representa combinaciones o 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, escritas como $P (n, k)$ , etc

Definición e interpretaciones

Imagen mostrando las combinaciones binomiales de a+b a la 4 — Todas las posibles combinaciones desde (a+b)¹ hasta (a+b)⁴

For natural numbers (taken to include 0) n y k, el coeficiente binomio ${tbinom {n}{k}}$ se puede definir como el coeficiente del monomial X^k en la expansión de $(1 + X) n$ . El mismo coeficiente también ocurre (si $k \leq n$ ) en la fórmula binomial

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

Otra ocurrencia de este número es en combinatoria, donde da el número de maneras, desprecio del orden, que k objetos se pueden elegir entre n objetos; más formalmente, el número de k-element subsets (or k-combinaciones) de un n-Element set. Este número se puede ver como igual a la de la primera definición, independientemente de cualquiera de las fórmulas siguientes para calcularlo: si en cada una de las n factores de la potencia $(1 + X) n$ una etiqueta temporal el término X con un índice i (de 1 a 1 n), entonces cada subconjunto de k índices da después de la expansión una contribución X^k, y el coeficiente de ese monomial en el resultado será el número de tales subconjuntos. Esto demuestra en particular que ${tbinom {n}{k}}$ es un número natural para cualquier número natural n y k. Hay muchas otras interpretaciones combinatorias de coeficientes binomiales (contando problemas para los cuales la respuesta es dada por una expresión binomio coeficiente), por ejemplo el número de palabras formadas de n bits (digits 0 o 1) cuya suma es k es dado por ${tbinom {n}{k}}$ , mientras que el número de formas de escribir ${displaystyle k=a_{1}+a_{2}+cdots +a_{n}}$ donde cada a_i es un entero no negativo es dado por ${tbinom {n+k-1}{n-1}}$ . La mayoría de estas interpretaciones se consideran fácilmente equivalentes a contar k-combinaciones.

(x+y)^{n}=sum _{k=0}^{n}{binom {n}{k}}x^{n-k}y^{k}

()Alternativa)

Cálculo del valor de los coeficientes binomiales

Existen varios métodos para calcular el valor ${tbinom {n}{k}}$ sin realmente expandir un poder binomio o contar k-combinaciones.

Fórmula recursiva

Un método utiliza la fórmula puramente aditiva recursiva

{displaystyle {binom {n}{k}}={binom {n-1}{k-1}}+{binom {n-1}{k}}}

$n,k$ ${displaystyle 1leq kleq n-1,}$

con valores iniciales/límites

{displaystyle {binom {n}{0}}={binom {n}{n}}=1}

${displaystyle ngeq 0.}$

La fórmula sigue considerando el conjunto $1, 2, 3,... n}$ y contando por separado (a) el k-element groupings that include a particular set element, say "i", en cada grupo (desde entonces "i" ya está elegido para llenar un lugar en cada grupo, sólo necesitamos elegir $k - 1$ del resto $n - 1$ ) y (b) todos los k- agrupaciones que no incluyen "i"; esto enumera todo lo posible k-combinaciones de n elementos. También se deriva de la localización de las contribuciones a X^k dentro $(1 + X) n -1 (1 + X)$ . Como hay cero $X n + 1$ o $X -1$ dentro $(1 + X) n$ , se podría ampliar la definición más allá de los límites anteriores para incluir ${displaystyle {tbinom {n}{k}}=0}$ cuando $k ■ n$ o $k 0$ . Esta fórmula recursiva permite entonces la construcción del triángulo de Pascal, rodeado de espacios blancos donde los ceros, o los coeficientes triviales, serían.

Fórmula multiplicativa

La fórmula proporciona un método más eficiente para calcular coeficientes binomiales individuales

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

$n^{underline {k}}$ knk

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 en el menor de k y $n - k$ .

Fórmula factorial

Finalmente, aunque computacionalmente inadecuado, existe la forma compacta, a menudo utilizada en demostraciones y derivaciones, que hace un uso repetido de la familiar función factorial:

{displaystyle {binom {n}{k}}={frac {n!}{k!,(n-k)!}}quad {text{for }} 0leq kleq n,}

nn $() n - k)!$ kn

{binom {n}{k}}={binom {n}{n-k}}quad {text{for }} 0leq kleq n,

()1)

lo que conduce a una rutina computacional multiplicativa más eficiente. Usando la notación factorial descendente,

{frac {n}{2}}end{cases}}.}" display="block" xmlns="http://www.w3.org/1998/Math/MathML">()nk)={}nk¿Qué? ¿Qué? /k!sik≤ ≤ n2nn− − k¿Qué? ¿Qué? /()n− − k)!sik■n2.{displaystyle {binom {} {begin{cases}n^{compline {k}/k! {n}{2}n^{enline {n-k}/(n-k)! k {frac {n}}end {cases}} {frac {n}{2}}end{cases}}.}" aria-hidden="true" class="mwe-math-fallback-image-display" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/014e9c8d38fd399a22520ba2f6bca22b0301e21b" style="vertical-align: -3.171ex; width:35.975ex; height:7.509ex;"/>

Generalización y conexión a la serie binomial

La fórmula multiplicativa permite ampliar 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{for }}kin mathbb {N} {text{ and arbitrary }}alpha.}

Con esta definición uno tiene una generalización de la fórmula binomial (con una de las variables fijadas a 1), que justifica todavía llamar a la ${tbinom {alpha }{k}}$ coeficientes binomiales:

(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 puede interpretarse como una identidad de series de potencias formales en X, donde en realidad puede servir como definición de potencias arbitrarias de series de potencias con coeficiente constante igual a 1; el punto es que con esta definición todas las identidades tienen lo que uno espera para la exponenciación, en particular

{displaystyle (1+X)^{alpha }(1+X)^{beta }=(1+X)^{alpha +beta }quad {text{and}}quad ((1+X)^{alpha })^{beta }=(1+X)^{alpha beta }.}

Si α es un 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

1000a fila del triángulo de Pascal, dispuesta verticalmente, con representaciones a escala gris de dígitos decimales de los coeficientes, alineados a la derecha. El límite izquierdo de la imagen corresponde aproximadamente al gráfico del logaritmo de los coeficientes binomiales, e ilustra que forman una secuencia de conversión de troncos.

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

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

()3)

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

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

Número de filas $n$ contiene los números ${tbinom {n}{k}}$ para $k = 0,..., n$ . Se construye por primera vez colocando 1 en las posiciones más externas, y luego llenando cada posición interior con la suma de los dos números directamente arriba. Este método permite el cálculo rápido de los coeficientes binomiales sin necesidad de fracciones o multiplicaciones. Por ejemplo, mirando la fila número 5 del triángulo, uno puede leer rápidamente que

{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 ${tbinom {n}{k}}$ maneras de elegir k elementos de un conjunto de n elementos. Ver Combinación.
Hay ${tbinom {n+k-1}{k}}$ maneras de elegir k elementos de un conjunto de n elementos si se permiten repeticiones. Ver Multiset.
Hay ${tbinom {n+k}{k}}$ strings containing k y n ceros.
Hay ${tbinom {n+1}{k}}$ strings consisting of k y n ceros tales que no hay dos adyacentes.
Los números catalanes son ${tfrac {1}{n+1}}{tbinom {2n}{n}}.$
La distribución binomial en las estadísticas es ${displaystyle {tbinom {n}{k}}p^{k}(1-p)^{n-k}.}$

Coeficientes binomiales como polinomios

Para cualquier entero no negativo k, la expresión ${textstyle {binom {t}{k}}}$ puede ser simplificado y definido como un polinomio dividido por $k!$ :

{displaystyle {binom {t}{k}}={frac {t^{underline {k}}}{k!}}={frac {t(t-1)(t-2)cdots (t-k+1)}{k(k-1)(k-2)cdots 2cdot 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 del binomio generalizado de Newton.

Para cada uno k, el polinomio ${tbinom {t}{k}}$ se puede caracterizar como el título único k polinomios $p () t)$ satisfacción $p (0) p (1) = p () k -1) = 0$ y $p () k) = 1$ .

Sus coeficientes son expresables en términos de números de Stirling de primera clase:

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

El derivado de ${tbinom {t}{k}}$ se puede calcular por diferenciación logarítmica:

{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 los enteros de ${displaystyle 0}$ a $t-1$ , pero usando identidades abajo podemos calcular el derivado como:

{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 la característica 0 (es decir, cualquier campo que contenga los números racionales), cada polinomio p()t) de grado en la mayoría d es únicamente expresible como una combinación lineal ${textstyle sum _{k=0}^{d}a_{k}{binom {t}{k}}}$ de coeficientes binomiales. El coeficiente a_k es la diferencia kth de la secuencia p(0), p(1),... p()k). Explícitamente,

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

()4)

Polinomios con valores enteros

Cada polinomio ${tbinom {t}{k}}$ se valora entero: tiene un valor entero en todos los insumos enteros $t$ . (Una manera de probar que esto es por inducción en k, usando la identidad de Pascal.) Por lo tanto, cualquier combinación lineal integer de polinomios de coeficiente binomial es integer-valued también. Por el contrario,4) muestra que cualquier polinomio de valor entero es una combinación lineal entero de estos polinomios de coeficiente binomio. Más generalmente, para cualquier subring R de un campo 0 característico K, un polinomio en K[t] toma valores en R en todos los enteros si y sólo si es un R- combinación lineal de polinomios de coeficiente binomial.

Ejemplo

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

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

Identidades que involucran coeficientes binomiales

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

{binom {n}{k}}={frac {n}{k}}{binom {n-1}{k-1}}

()5)

y, con un poco más de trabajo,

{binom {n-1}{k}}-{binom {n-1}{k-1}}={frac {n-2k}{n}}{binom {n}{k}}.

También podemos obtener

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

Además, lo siguiente puede ser útil:

{displaystyle {binom {n}{h}}{binom {n-h}{k}}={binom {n}{k}}{binom {n-k}{h}}={binom {n}{h+k}}{binom {h+k}{h}}.}

Para n constante, tenemos la siguiente recurrencia:

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

Para resumir, tenemos

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

Sumas de los coeficientes binomiales

La fórmula

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

()Alternativa)

dice los elementos en los $n$ la fila del triángulo de Pascal siempre suman hasta 2 elevados al $n$ Ese poder. Esto se obtiene del teorema binomial (Alternativa) x = 1 y Sí. = 1. La fórmula también tiene una interpretación combinatoria natural: el lado izquierdo resume 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 potencia de {1,... n}.) Sin embargo, estos subconjuntos también se pueden generar eligiendo o excluyendo sucesivamente cada elemento 1,..., n; el n opciones binarias independientes (herramientas) permiten un total de $2^{n}$ opciones. Los lados izquierdo y derecho son dos maneras de contar la misma colección de subconjuntos, por lo que son iguales.

Las fórmulas

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

()6)

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

seguir del teorema del binomio después de diferenciar con respecto a $x$ (dos veces por el último) y luego sustituir $x = y = 1$ .

La identidad de Chu–Vandermonde, que se cumple para cualquier valor complejo m y n y cualquier número 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 mediante el examen del coeficiente $x^{k}$ en la expansión de $(1 + x) m (1 + x) n - m = 1 + x) n$ usando la ecuación2). Cuando $m = 1$ , ecuación7) reduce a la ecuación (3). En el caso especial $n = 2 m, k = m$ , utilizando (1), la expansión (7) se convierte (como se ve en el triángulo de Pascal a la derecha)

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

triángulo de Pascal, filas 0 a través 7. 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 satisfagan $0 \leq j \leq k \leq n$ , es

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

()9)

La prueba 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.
Después

{displaystyle sum _{k=0}^{lfloor n/2rfloor }{binom {n-k}{k}}=F(n+1).}

Esto se puede probar por inducción usando (3) o por la representación de Zeckendorf. A continuación se da una demostración combinatoria.

Multisecciones de sumas

Para los enteros s y t tales que $<math alttext="{displaystyle 0leq t 0\leq \leq t.s,{displaystyle 0leq t wons,} <img alt="{displaystyle 0leq t$ multisección de serie da la siguiente identidad para la suma de coeficientes binomiales:

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

Para las $s$ pequeñas, estas series tienen formas particularmente agradables; por ejemplo,

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

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

{displaystyle {binom {n}{2}}+{binom {n}{5}}+{binom {n}{8}}+cdots ={frac {1}{3}}left(2^{n}+2cos {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 {npi }{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 {npi }{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 {npi }{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 {npi }{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 usar nuevamente (3) e inducción para mostrar que para $k = 0, \dots, 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.}

Diferenciante (diferente)2) k tiempos y ajustes x = 1 - produce esto para
$P(x)=x(x-1)cdots (x-k+1)$ ,
cuando 0 ≤ k. n,
y el caso general sigue tomando combinaciones lineales de estos.

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

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

()10)

Donde $a_{n}$ es el coeficiente de grado n dentro P()x).

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 se aplica inmediatamente (10) al polinomio ${displaystyle Q(x):=P(m+dx)}$ en lugar de $P(x)$ , y observando que $Q(x)$ todavía tiene un grado inferior o igual a n, y que su coeficiente de grado n es dⁿa_n.

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

Identidades con pruebas combinatorias

Muchas identidades que involucran coeficientes binomiales pueden ser probadas por medios combinatorios. Por ejemplo, para los enteros no negativos ${n}geq {q}$ , la identidad

{displaystyle sum _{k=q}^{n}{binom {n}{k}}{binom {k}{q}}=2^{n-q}{binom {n}{q}}}

(que reduce a (6Cuando q = 1) se puede dar una prueba contable doble, como sigue. El lado izquierdo cuenta el número de maneras de seleccionar un subconjunto de [n# = {1, 2,..., nCon al menos q elementos y marcación q elementos entre los seleccionados. El lado derecho cuenta lo mismo, porque hay ${tbinom {n}{q}}$ maneras de elegir un conjunto de q elementos a marcar, y ${displaystyle 2^{n-q}}$ elegir cuál de los elementos restantes de [nTambién pertenecen al subconjunto.

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 n y 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}}.}

Supongamos que usted tiene $2n$ cuadrados vacíos dispuestos en una fila y desea marcar (seleccionar) n de ellos. Hay ${tbinom {2n}{n}}$ maneras de hacer esto. Por otro lado, puede seleccionar su n cuadrados seleccionando k cuadrados de entre los primeros n y $n-k$ cuadrados de los restantes n cuadrados; cualquier k de 0 a 0 n funcionará. Esto da

{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, indexada de modo que $F (0) = F (1) = 1$ , entonces la identidad

{displaystyle sum _{k=0}^{leftlfloor {frac {n}{2}}rightrfloor }{binom {n-k}{k}}=F(n)}

$F () n)$ $n \times 1$ $2 \times 1$ $1 \times 1$ $k$ $2 \times 1$ $n - 2 k$ $1 \times 1$ $n - k$ ${tbinom {n-k}{k}}$ $k$

Suma de la fila de coeficientes

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

Identidad de Dixon

La identidad de Dixon es

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

o, más generalmente,

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

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

Identidades continuas

Ciertas integrales trigonométricas tienen valores expresables en términos de coeficientes binomiales: Para cualquier ${displaystyle m,nin 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 pueden probarse 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}

k ${displaystyle 0leq kleq n-1.}$ nkkn

De hecho, tenemos

{displaystyle {binom {n-1}{k}}={(n-1)(n-2)cdots (n-k) over 1cdot 2cdots k}=prod _{i=1}^{k}{n-i over i}equiv prod _{i=1}^{k}{-i over i}=(-1)^{k}mod n.}

Funciones generadoras

Funciones generadoras ordinarias

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

{displaystyle sum _{k=0}^{infty }{n choose k}x^{k}=(1+x)^{n}.}

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

{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 el mismo que la anterior función generadora después de la sustitución ${displaystyle xto xy}$ .

Función generadora exponencial

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

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

Propiedades de divisibilidad

En 1852, Kummer demostró que si m y n son enteros no negativos y p es un número primo, entonces el mayor poder de p división ${tbinom {m+n}{m}}$ iguales p^c, donde c es el número de cargas cuando m y n se añaden en base p.
Equivalentemente, el exponente de un primo p dentro ${tbinom {n}{k}}$ iguala el número de enteros no negativos j tal que la parte fraccional de k/p^j es mayor que la parte fraccional de n/p^j. Se puede deducir de esto que ${tbinom {n}{k}}$ es divisible por n/gcd(n,k). En particular, sigue que p divideciones ${tbinom {p^{r}}{s}}$ para todos los enteros positivos r y s tales que $s . p r$ . Sin embargo esto no es verdad de los poderes superiores p: por ejemplo 9 no divide ${tbinom {9}{6}}$ .

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

lim _{Nto infty }{frac {f(N)}{N(N+1)/2}}=1.

Desde el número de coeficientes binomiales ${tbinom {n}{k}}$ con n. N es N()N + 1) / 2, esto implica que la densidad de coeficientes binomiales divisible por d va a 1.

Los coeficientes binomiales tienen propiedades de divisibilidad relacionadas con los mínimos comunes múltiplos de enteros consecutivos. Por ejemplo:

${displaystyle {binom {n+k}{k}}}$ divideciones ${displaystyle {frac {operatorname {lcm} (n,n+1,ldotsn+k)}{n}}}$ .

${displaystyle {binom {n+k}{k}}}$ es un múltiple de ${displaystyle {frac {operatorname {lcm} (n,n+1,ldotsn+k)}{ncdot operatorname {lcm} ({binom {k}{0}},{binom {k}{1}},ldots{binom {k}{k}})}}}$ .

Otro dato:
Un entero $n \geq 2$ es primo si y solo si
todos los coeficientes binomiales intermedios

{binom {n}{1}},{binom {n}{2}},ldots{binom {n}{n-1}}

son divisibles por n.

Prueba:
Cuando p es primo, p divide

{binom {p}{k}}={frac {pcdot (p-1)cdots (p-k+1)}{kcdot (k-1)cdots 1}}

para todos

0 k . p

porque ${displaystyle {tbinom {p}{k}}}$ es un número natural y p divide el numerador pero no el denominador.
Cuando n es composite, vamos p ser el factor primario más pequeño n y dejar $k = n / p$ . Entonces... $0 p . n$ y

{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)\dots(n - p + 1)$ tiene que ser divisible por $n = k \times p$ , este solo puede ser el caso cuando $(n - 1)(n - 2)\dots(n - p + 1)$ es divisible por p. Pero n es divisible por p, entonces p no divide a $n - 1, n - 2, \dots, n - p + 1$ y porque p es primo, sabemos que p no divide $(n - 1)(n - 2)\dots(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 para ${tbinom {n}{k}}$ para todos los valores n y k tales que $1 \leq k \leq n$ :

<math alttext="{displaystyle {frac {n^{k}}{k^{k}}}leq {n choose k}leq {frac {n^{k}}{k!}}nkkk≤ ≤ ()nk)≤ ≤ nkk!.()n⋅ ⋅ ek)k.{displaystyle {frac {f}{k}}}leq {n choose k}leq {frac {n^{k}}} {left({frac {ncdot e} {k}}right)} {k}}}} {ccH0} {ccH0} {ccH0}}}ccH00}cH0}cH0}ccccH0}}}}}ccccccccccH00}ccH00}ccH00}cccH0cccccccccccH00}cccH00}ccccH00}cccccccccH00}cH00}ccH00ccccccH00}cccH <img alt="{displaystyle {frac {n^{k}}{k^{k}}}leq {n choose k}leq {frac {n^{k}}{k!}}

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

$k$ ${textstyle geq {frac {n}{k}}}$ $k^{k}/k!}" xmlns="http://www.w3.org/1998/Math/MathML">ek■kk/k!{textstyle e^{k} {k}/k}k^{k}/k!}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0761abba6fa513b4ca9409521eada6e97e84faaf" style="vertical-align: -0.838ex; width:10.591ex; height:3.009ex;"/>$ ${textstyle e^{k}=sum _{j=0}^{infty }k^{j}/j!}$

De las propiedades de divisibilidad podemos inferir que

{displaystyle {frac {operatorname {lcm} (n-k,ldotsn)}{(n-k)cdot operatorname {lcm} left({binom {k}{0}},ldots{binom {k}{k}}right)}}leq {binom {n}{k}}leq {frac {operatorname {lcm} (n-k,ldotsn)}{n-k}},}

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 choose k}leq 2^{nH(k/n)}}

${displaystyle H(p)=-plog _{2}(p)-(1-p)log _{2}(1-p)}$

{displaystyle {sqrt {frac {n}{8k(n-k)}}}2^{nH(k/n)}leq {n choose k}leq {sqrt {frac {n}{pi k(n-k)}}}2^{nH(k/n)}}

$1 leq k leq n-1$

N y K tendiendo a infinito

La aproximación de Stirling produce la siguiente aproximación, válida cuando $n,k$ ambos tienden a infinito:

{displaystyle {n choose k}sim {sqrt {n over 2pi k(n-k)}}cdot {n^{n} over k^{k}(n-k)^{n-k}}}

$n$

{displaystyle {2n choose n}sim {frac {2^{2n}}{sqrt {npi }}}}

${sqrt {n}}{2n choose n}geq 2^{2n-1}$ $m \geq 2$ $n \geq 1$

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

Si n es grande y k es lineal en n, existen varias estimaciones asintomáticas precisas para el coeficiente binomio ${textstyle {binom {n}{k}}}$ . Por ejemplo, si ${displaystyle |n/2-k|=o(n^{2/3})}$ entonces

{displaystyle {binom {n}{k}}sim {binom {n}{frac {n}{2}}}e^{-d^{2}/(2n)}sim {frac {2^{n}}{sqrt {{frac {1}{2}}npi }}}e^{-d^{2}/(2n)}}

dnk

N mucho mayor que K

Si $n$ es grande y $k$ es $o (n)$ (es decir, si $k / n \to 0$ ), luego

{displaystyle {binom {n}{k}}sim left({frac {ne}{k}}right)^{k}cdot (2pi k)^{-1/2}cdot exp left(-{frac {k^{2}}{2n}}(1+o(1))right)}

$o$

Sumas de coeficientes binomiales

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

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

{displaystyle {frac {1}{sqrt {8nvarepsilon (1-varepsilon)}}}cdot 2^{H(varepsilon)cdot n}leq sum _{i=0}^{k}{binom {n}{i}}leq 2^{H(varepsilon)cdot n},}

$kgeq 1}" xmlns="http://www.w3.org/1998/Math/MathML">n■k≥ ≥ 1{displaystyle n títulokgeq 1}kgeq 1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3d1a4fc62991479d4caef69a5ae6c4a8a22006d8" style="vertical-align: -0.505ex; width:9.965ex; height:2.343ex;"/>$ ${displaystyle varepsilon doteq k/nleq 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 {left(1+{frac {1}{j}}right)^{-z-1}}{1-{frac {z+1}{j}}}}}

{displaystyle {z choose k}approx {frac {(-1)^{k}}{Gamma (-z)k^{z+1}}}qquad {text{and}}qquad {z+k choose k}={frac {k^{z}}{Gamma (z+1)}}left(1+{frac {z(z+1)}{2k}}+{mathcal {O}}left(k^{-2}right)right)}

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

$H_{k}$ k $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}}

$kto infty$ ${displaystyle j/kto x}$ $x$

Generalizaciones

Generalización a multinomios

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

{n choose k_{1},k_{2},ldotsk_{r}}={frac {n!}{k_{1}!k_{2}!cdots k_{r}!}}

dónde

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:

{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 los 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:

{n choose k_{1},k_{2},ldotsk_{r}}={n-1 choose k_{1}-1,k_{2},ldotsk_{r}}+{n-1 choose k_{1},k_{2}-1,ldotsk_{r}}+ldots +{n-1 choose k_{1},k_{2},ldotsk_{r}-1}

y simetría:

{n choose k_{1},k_{2},ldotsk_{r}}={n choose k_{sigma _{1}},k_{sigma _{2}},ldotsk_{sigma _{r}}}

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

Serie Taylor

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

{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 puede ampliarse al caso en que $n$ es real y $k$ es entero.

En particular, la siguiente identidad tiene para cualquier entero no negativo $k$ :

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

Esto aparece cuando se expande ${sqrt {1+x}}$ en una serie de energía usando la serie binomial Newton:

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

Productos de coeficientes binomiales

Uno 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 etiquetados, los coeficientes de conexión representan el número de formas de asignar $m + n - k</i$ etiquetas a un par de objetos combinatorios etiquetados, de peso m y n respectivamente, que han tenido sus primeras etiquetas k identificadas, o pegados para obtener un nuevo objeto combinatorio etiquetado de peso $m + n - k$ . (Es decir, separar las etiquetas en tres partes para aplicarlas a la parte pegada, la parte no pegada del primer objeto y la parte no pegada del segundo objeto). son a series generatrices ordinarias.

El producto de todos los coeficientes binomiales en la fila n del triángulo de Pascal viene dado por la fórmula:

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

Descomposición en fracciones parciales

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

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

Serie binomial de Newton

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

(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

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

donde la identidad

{n choose k}=(-1)^{k}{k-n-1 choose k}

se aplica.

Coeficiente binomial multiconjunto (ascendente)

Los coeficientes binomiales cuentan subconjuntos de tamaño prescrito de un conjunto dado. Un problema combinatorio relacionado es contar multiconjuntos de tamaño prescrito con elementos extraídos de un conjunto dado, es decir, contar el número de maneras de seleccionar un cierto número de elementos de un determinado conjunto con la posibilidad de seleccionar el mismo elemento repetidamente. Los números resultantes se llaman coeficientes multiconjuntos; el número de maneras de "multichoose" (es decir, elegir con reemplazo) k artículos de un n elemento set es denotado ${textstyle left(!!{binom {n}{k}}!!right)}$ .

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

Los coeficientes 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}}.}

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

{displaystyle r^{(k)}=,r^{overline {k}}=,rcdot (r+1)cdot (r+2)cdot (r+3)cdots (r+k-1);}

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

{displaystyle {binom {f}{k}}={frac {(f)_{k}}{k!}}={frac {(f-k+1)cdots (f-2)cdot (f-1)cdot f}{1cdot 2cdot 3cdot 4cdot 5cdots k}},}

{displaystyle left(!!{binom {r}{k}}!!right)={frac {r^{(k)}}{k!}}={frac {rcdot (r+1)cdot (r+2)cdots (r+k-1)}{1cdot 2cdot 3cdot 4cdot 5cdots k}}.}

Generalización a enteros negativos n

Coeficientes binomiales C()n, k) prorrogado para negativo y fraccional n, ilustrado con un simple binomio. Se puede observar que el triángulo de Pascal está rota y los términos alternativos son negados. El caso n= 1 - da la serie de Grandi.

Para cualquier n,

{begin{aligned}{binom {-n}{k}}&={frac {-ncdot -(n+1)dots -(n+k-2)cdot -(n+k-1)}{k!}}\&=(-1)^{k};{frac {ncdot (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 son dados por los coeficientes multiset firmados. En el caso especial $n=-1$ , esto reduce a ${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:

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

Dos argumentos de valor reales o complejos

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

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

Esta definición hereda estas siguientes propiedades adicionales de $Gamma$ :

{x choose y}={frac {sin(ypi)}{sin(xpi)}}{-y-1 choose -x-1}={frac {sin((x-y)pi)}{sin(xpi)}}{y-x-1 choose y};

además,

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

The resulting function has been little-studied, apparently first being graphed in (Fowler 1996). Notablemente, muchas identidades binomiales fallan: ${textstyle {binom {n}{m}}={binom {n}{n-m}}}$ pero ${textstyle {binom {-n}{m}}neq {binom {-n}{-n-m}}}$ para n positivo (so $-n$ negativo). El comportamiento es bastante complejo, y marcadamente diferente en varios octantes (es decir, con respecto a los x y Sí. ejes y la línea $y=x$ ), con el comportamiento negativo x tener singularidades en valores enteros negativos y un tablero de control de regiones positivas y negativas:

en el octante $0leq yleq x$ es una forma suavemente interpolada del binomial habitual, con una cresta ("la cresta de Pascal").
en el octante $0leq xleq y$ y en el cuadrante $xgeq 0,yleq 0$ la función está cerca de cero.
en el cuadrante $xleq 0,ygeq 0$ la función es alternadamente muy grande positivo y negativo en los paralelogramas con vértices ${displaystyle (-n,m+1),(-n,m),(-n-1,m-1),(-n-1,m)}$
en el octante $x>y}" xmlns="http://www.w3.org/1998/Math/MathML">0■x■Sí.{displaystyle 0 títulox confianzay}x>y" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/064a0afafec9d2763065e3948c473986a95a9b13" style="vertical-align: -0.671ex; width:9.845ex; height:2.509ex;"/>$ el comportamiento es otra vez muy grande positivo y negativo, pero en una cuadrícula cuadrada.
en el octante $y>x+1}" xmlns="http://www.w3.org/1998/Math/MathML">− − 1■Sí.■x+1{displaystyle - 1 título de propiedady>x+1" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2b78516a89e2b5656e38354fefe87cae02845b01" style="vertical-align: -0.671ex; width:15.656ex; height:2.509ex;"/>$ está cerca de cero, excepto cerca de las singularidades.

Generalización a serie q

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

Generalización a infinitos cardinales

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

{displaystyle {alpha choose beta }=left|left{Bsubseteq A:left|Bright|=beta right}right|}

donde A es un conjunto con la cardenalidad $alpha$ . Uno puede demostrar que el coeficiente binomial generalizado está bien definido, en el sentido de que no importa lo que elijamos representar el número cardenal $alpha$ , ${textstyle {alpha choose beta }}$ permanecerá igual. Para los cardenales finitos, esta definición coincide con la definición estándar del coeficiente binomio.

Suponiendo el Axioma de la Elección, se puede demostrar que ${textstyle {alpha choose alpha }=2^{alpha }}$ para cualquier cardenal infinito $alpha$ .

En lenguajes de programación

La notación ${textstyle {n choose k}}$ es conveniente en la escritura de mano pero inconveniente para las máquinas de escribir y terminales de ordenador. Muchos idiomas de programación no ofrecen una subrutina estándar para calcular el coeficiente binomio, pero por ejemplo el lenguaje de programación de la APL y el (relacionado) El lenguaje de programación J utiliza la marca de exclamación: k ! n. El coeficiente binomial se implementa en SciPy scipy.special.com b.

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

desde matemáticas importación factorialdef binomial_coeficiente()n: int, k: int) - int: retorno factorial()n) // ()factorial()k) * factorial()n - k)

son muy lentos y no sirven para calcular factoriales de números muy altos (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_coeficiente()n: int, k: int) - int: si k . 0 o k ■ n: retorno 0 si k == 0 o k == n: retorno 1 k = min()k, n - k) # Aproveche la simetría c = 1 para i dentro rango()k): c = c * ()n - i) // ()i + 1) retorno c

(En Python, range(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_coeficiente()n: int, k: int) - int: si k . 0 o k ■ n: retorno 0 si k ■ n - k: # Aproveche la simetría k = n - k si k == 0 o n . 1: retorno 1 retorno binomial_coeficiente()n - 1, k) + binomial_coeficiente()n - 1, k - 1)

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

{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

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

La siguiente implementación utiliza todas estas ideas

()definir ()binomial n k);; Función de ayuda para calcular C(n,k) a través de la recursión avanzada ()definir ()binomial-iter n k i prev) ()si ()>= i k) prev ()binomial-iter n k ()+ i 1) ()/ ()* ()- n i) prev) ()+ i 1))));; Use la propiedad de la simetría C(n,k)=C(n, n-k) ()si (). k ()- n k) ()binomial-iter n k 0 1) ()binomial-iter n ()- n k) 0 1))

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

{displaystyle {n choose k+1}=left[{frac {binom {n}{k}}{(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 - No.no firmado largo binomial()no firmado largo n, no firmado largo k) {} no firmado largo c = 1, i; si ()k ■ n-k) // aprovechar la simetría k = n-k; para ()i = 1; i . k; i++, n--) {} si ()c/i ■ ULONG_MAX/n) // retorno 0 sobre el potencial de desbordamiento retorno 0; c = c / i * n + c % i * n / i; // split c * n / i in (c / i * i + c % i) * n / i } retorno c;}

Otra forma de calcular el coeficiente binomial cuando se usan 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 ${displaystyle ln Gamma (n)}$ denota el logaritmo natural de la función gamma en $n$ . Es una función especial que se computa fácilmente y es estándar en algunos idiomas de programación como el uso log_gamma en Maxima, LogGamma en Mathematica, gammaln en el módulo SciPy de MATLAB y Python, lngamma en PARI/GP o lgamma en C, R y Julia. El error Roundoff puede causar que el valor devuelto no sea un entero.

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

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