Coeficiente binomial
Em matemática, os coeficientes binomiais são os números inteiros positivos que ocorrem como coeficientes no teorema binomial. Comumente, um coeficiente binomial é indexado por um par de inteiros n ≥ k ≥ 0 e é escrito ou . É o coeficiente do termo xk na expansão polinomial da potência binomial (1 + x)n; este coeficiente pode ser calculado pela fórmula multiplicativa
Andreas von Ettingshausen introduziu a notação ( n k ) {\displaystyle {\tbinom {n}{k}}} em 1826, embora os números fossem conhecidos séculos antes (veja triângulo de Pascal). Por volta de 1150, o matemático indiano Bhaskaracharya deu uma exposição dos coeficientes binomiais em seu livro Līlāvatī. Notações alternativas incluem C(n, k), nCk, nCk, Ckn, Cnk e Cn,k, em todas as quais o C significa combinações ou escolhas; a notação C significa o número de maneiras de escolher k dentre n objetos. Muitas calculadoras usam variantes da notação C porque podem representá-la em um visor de linha única. Nesta forma, os coeficientes binomiais são facilmente comparados com os números de k-permutações de n, escritos como P(n, k), etc.
Para números naturais (considerando 0) n e k, o coeficiente binomial ( n k ) {\displaystyle {\tbinom {n}{k}}} pode ser definido como o coeficiente do monômio Xk na expansão de (1 + X)n. O mesmo coeficiente também ocorre (se k ≤ n) na fórmula binomial (válida para quaisquer elementos x, y de um anel comutativo), o que explica o nome "coeficiente binomial". Outra ocorrência deste número está na combinatória, onde ele dá o número de maneiras, desconsiderando a ordem, de escolher k objetos dentre n objetos; mais formalmente, o número de subconjuntos de k elementos (ou k-combinações) de um conjunto de n elementos. Este número pode ser visto como igual ao da primeira definição, independentemente de quaisquer fórmulas abaixo para calculá-lo: se em cada um dos n fatores da potência (1 + X)n rotularmos temporariamente o termo X com um índice i (variando de 1 a n), então cada subconjunto de k índices dá, após a expansão, uma contribuição Xk, e o coeficiente desse monômio no resultado será o número de tais subconjuntos. Isso mostra em particular que ( n k ) {\displaystyle {\tbinom {n}{k}}} é um número natural para quaisquer números naturais n e k. Há muitas outras interpretações combinatórias dos coeficientes binomiais (problemas de contagem para os quais a resposta é dada por uma expressão de coeficiente binomial), por exemplo, o número de palavras formadas por n bits (dígitos 0 ou 1) cuja soma é k é dado por ( n k ) {\displaystyle {\tbinom {n}{k}}} , enquanto o número de maneiras de escrever k = a 1 + a 2 + ⋯ + a n {\displaystyle k=a_{1}+a_{2}+\cdots +a_{n}} onde cada ai é um inteiro não negativo é dado por ( n + k − 1 n − 1 ) {\displaystyle {\tbinom {n+k-1}{n-1}}} . A maioria dessas interpretações pode ser mostrada como equivalente à contagem de k-combinações.
Existem vários métodos para calcular o valor de ( n k ) {\displaystyle {\tbinom {n}{k}}} sem realmente expandir uma potência binomial ou contar k-combinações.
Fórmula recursiva
Um método usa a fórmula recursiva puramente aditiva ( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}} para todos os inteiros n , k {\displaystyle n,k} tais que 1 ≤ k < n {\displaystyle 1\leq k<n} , com valores de contorno ( n 0 ) = ( n n ) = 1 {\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1} para todos os inteiros n ≥ 0. A fórmula segue considerando o conjunto {1, 2, 3, ..., n} e contando separadamente (a) os agrupamentos de k elementos que incluem um determinado elemento do conjunto, digamos "i", em cada grupo (já que "i" já está escolhido para preencher uma posição em cada grupo, precisamos escolher apenas k − 1 dos n − 1 restantes) e (b) todos os agrupamentos de k que não incluem "i"; isso enumera todas as possíveis k-combinações de n elementos. Também segue rastreando as contribuições para Xk em (1 + X)n−1(1 + X). Como não há Xn+1 ou X−1 em (1 + X)n, pode-se estender a definição além dos limites acima para incluir ( n k ) = 0 {\displaystyle {\tbinom {n}{k}}=0} quando k > n ou k < 0. Esta fórmula recursiva então permite a construção do triângulo de Pascal, cercado por espaços em branco onde os zeros, ou os coeficientes triviais, estariam.
Fórmula multiplicativa
Um método mais eficiente para calcular coeficientes binomiais individuais é dado pela fórmula ( n k ) = n k _ k ! = n ( n − 1 ) ( n − 2 ) ⋯ ( n − ( k − 1 ) ) k ( k − 1 ) ( k − 2 ) ⋯ 1 = ∏ i = 1 k n + 1 − i i , {\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}},} onde o numerador da primeira fração, n k _ {\displaystyle n^{\underline {k}}} , é um fatorial decrescente. Esta fórmula é mais fácil de entender para a interpretação combinatória dos coeficientes binomiais. O numerador dá o número de maneiras de selecionar uma sequência de k objetos distintos, mantendo a ordem de seleção, de um conjunto de n objetos. O denominador conta o número de sequências distintas que definem a mesma k-combinação quando a ordem é desconsiderada. Esta fórmula também pode ser declarada em uma forma recursiva. Usando a notação "C" acima, C n , k = C n , k − 1 ⋅ ( n − k + 1 ) / k {\displaystyle C_{n,k}=C_{n,k-1}\cdot (n-k+1)/k} , onde C n , 0 = 1 {\displaystyle C_{n,0}=1} . É prontamente derivada avaliando C n , k / C n , k − 1 {\displaystyle C_{n,k}/C_{n,k-1}} e pode ser intuitivamente compreendida como começando no coeficiente mais à esquerda da n {\displaystyle n} -ésima linha do triângulo de Pascal, cujo valor é sempre 1 {\displaystyle 1} , e calculando recursivamente o próximo coeficiente à sua direita até que o k {\displaystyle k} -ésimo seja alcançado.
Fórmula fatorial
Finalmente, há a forma compacta, frequentemente usada em provas e derivações, que faz uso repetido da familiar função fatorial: ( n k ) = n ! k ! ( n − k ) ! para 0 ≤ k ≤ n , {\displaystyle {\binom {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\text{para }}\ 0\leq k\leq n,} onde n! denota o fatorial de n. Esta fórmula segue da fórmula multiplicativa acima multiplicando numerador e denominador por (n − k)!; como consequência, envolve muitos fatores comuns ao numerador e ao denominador. É menos prática para cálculo explícito (no caso em que k é pequeno e n é grande), a menos que fatores comuns sejam primeiro cancelados (em particular, porque os valores fatoriais crescem muito rapidamente). A fórmula exibe uma simetria que é menos evidente a partir da fórmula multiplicativa (embora seja a partir das definições)
Generalização e conexão com a série binomial
A fórmula multiplicativa permite que a definição dos coeficientes binomiais seja estendida substituindo n por um número arbitrário α (negativo, real, complexo) ou mesmo por um elemento de qualquer anel comutativo no qual todos os inteiros positivos são invertíveis: ( α k ) = α k _ k ! = α ( α − 1 ) ( α − 2 ) ⋯ ( α − k + 1 ) k ( k − 1 ) ( k − 2 ) ⋯ 1 para k ∈ N e α arbitrário . {\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{ e }}\alpha {\text{ arbitrário}}.} Com esta definição, tem-se uma generalização da fórmula binomial (com uma das variáveis definida como 1), o que justifica ainda chamar os ( α k ) {\displaystyle {\tbinom {\alpha }{k}}} de coeficientes binomiais:
A regra de Pascal é a importante relação de recorrência que pode ser usada para provar por indução matemática que ( n k ) {\displaystyle {\tbinom {n}{k}}} é um número natural para todo inteiro n ≥ 0 e todo inteiro k, um fato que não é imediatamente óbvio a partir da fórmula (1). À esquerda e à direita do triângulo de Pascal, as entradas (mostradas como espaços em branco) são todas zero. A regra de Pascal também dá origem ao triângulo de Pascal: A linha número n contém os números ( n k ) {\displaystyle {\tbinom {n}{k}}} para k = 0, …, n. É construída primeiro colocando 1s nas posições mais externas e depois preenchendo cada posição interna com a soma dos dois números imediatamente acima. Este método permite o cálculo rápido de coeficientes binomiais sem a necessidade de frações ou multiplicações. Por exemplo, olhando para a linha número 5 do triângulo, pode-se ler rapidamente que ( x + y ) 5 = 1 _ x 5 + 5 _ x 4 y + 10 _ x 3 y 2 + 10 _ x 2 y 3 + 5 _ x y 4 + 1 _ y 5 . {\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}.}
Os coeficientes binomiais são importantes na combinatória porque fornecem fórmulas prontas para certos problemas de contagem frequentes:
Para qualquer inteiro não negativo k, a expressão ( t k ) {\textstyle {\binom {t}{k}}} pode ser escrita como um polinômio com denominador k!: ( t k ) = t k _ k ! = t ( t − 1 ) ( t − 2 ) ⋯ ( t − k + 1 ) k ( k − 1 ) ( k − 2 ) ⋯ 2 ⋅ 1 ; {\displaystyle {\binom {t}{k}}={\frac {t^{\underline {k}}}{k!}}={\frac {t(t-1)(t-2)\cdots (t-k+1)}{k(k-1)(k-2)\cdots 2\cdot 1}};} isso apresenta um polinômio em t com coeficientes racionais. Como tal, pode ser avaliado em qualquer número real ou complexo t para definir coeficientes binomiais com tais primeiros argumentos. Esses "coeficientes binomiais generalizados" aparecem no teorema binomial generalizado de Newton. Para cada k, o polinômio ( t k ) {\displaystyle {\tbinom {t}{k}}} pode ser caracterizado como o único polinômio de grau k p(t) satisfazendo p(0) = p(1) = ⋯ = p(k − 1) = 0 e p(k) = 1. Seus coeficientes são expressáveis em termos de números de Stirling do primeiro tipo: ( t k ) = ∑ i = 0 k s ( k , i ) t i k ! . {\displaystyle {\binom {t}{k}}=\sum _{i=0}^{k}s(k,i){\frac {t^{i}}{k!}}.} A derivada de ( t k ) {\displaystyle {\tbinom {t}{k}}} pode ser calculada por diferenciação logarítmica: d d t ( t k ) = ( t k ) ∑ i = 0 k − 1 1 t − i . {\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}={\binom {t}{k}}\sum _{i=0}^{k-1}{\frac {1}{t-i}}.} Isso pode causar um problema quando avaliado em inteiros de 0 {\displaystyle 0} a t − 1 {\displaystyle t-1} , mas usando identidades abaixo podemos calcular a derivada como: d d t ( t k ) = ∑ i = 0 k − 1 ( − 1 ) k − i − 1 k − i ( t i ) . {\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 binomiais como base para o espaço de polinômios
Sobre qualquer corpo de característica 0 (ou seja, qualquer corpo que contenha os números racionais), cada polinômio p(t) de grau no máximo d é unicamente expressável como uma combinação linear ∑ k = 0 d a k ( t k ) {\textstyle \sum _{k=0}^{d}a_{k}{\binom {t}{k}}} de coeficientes binomiais, porque os coeficientes binomiais consistem em um polinômio de cada grau. O coeficiente ak é a k-ésima diferença da sequência p(0), p(1), ..., p(k). Explicitamente,
Polinômios com valores inteiros
Cada polinômio ( t k ) {\displaystyle {\tbinom {t}{k}}} tem valores inteiros: tem um valor inteiro em todas as entradas inteiras t {\displaystyle t} . (Uma maneira de provar isso é por indução em k usando a identidade de Pascal.) Portanto, qualquer combinação linear inteira de polinômios de coeficientes binomiais também tem valores inteiros. Reciprocamente, (4) mostra que qualquer polinômio com valores inteiros é uma combinação linear inteira desses polinômios de coeficientes binomiais. Mais geralmente, para qualquer subanel R de um corpo K de característica 0, um polinômio em K[t] assume valores em R em todos os inteiros se e somente se for uma combinação linear R-linear de polinômios de coeficientes binomiais.
Exemplo
O polinômio com valores inteiros 3t(3t + 1) / 2 pode ser reescrito como 9 ( t 2 ) + 6 ( t 1 ) + 0 ( t 0 ) . {\displaystyle 9{\binom {t}{2}}+6{\binom {t}{1}}+0{\binom {t}{0}}.}
A fórmula fatorial facilita relacionar coeficientes binomiais próximos. Por exemplo, se k é um inteiro positivo e n é arbitrário, então e, com um pouco mais de trabalho, ( n − 1 k ) − ( n − 1 k − 1 ) = n − 2 k n ( n k ) . {\displaystyle {\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.} Também podemos obter ( n − 1 k ) = n − k n ( n k ) . {\displaystyle {\binom {n-1}{k}}={\frac {n-k}{n}}{\binom {n}{k}}.} Além disso, o seguinte pode ser útil: ( n k ) ( k j ) = ( n j ) ( n − j k − j ) = ( n k − j ) ( n − k + j j ) . {\displaystyle {\binom {n}{k}}{\binom {k}{j}}={\binom {n}{j}}{\binom {n-j}{k-j}}={\binom {n}{k-j}}{\binom {n-k+j}{j}}.} Para n constante, temos a seguinte recorrência: ( n k ) = n − k + 1 k ( n k − 1 ) . {\displaystyle {\binom {n}{k}}={\frac {n-k+1}{k}}{\binom {n}{k-1}}.} Resumindo, temos ( n k ) = ( n n − k ) = n − k + 1 k ( n k − 1 ) = n n − k ( n − 1 k ) {\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}}} = n k ( n − 1 k − 1 ) = n n − 2 k ( ( n − 1 k ) − ( n − 1 k − 1 ) ) = ( n − 1 k ) + ( n − 1 k − 1 ) . {\displaystyle ={\frac {n}{k}}{\binom {n-1}{k-1}}={\frac {n}{n-2k}}{\Bigg (}{\binom {n-1}{k}}-{\binom {n-1}{k-1}}{\Bigg )}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}.}
Somas dos coeficientes binomiais
diz que os elementos na n-ésima linha do triângulo de Pascal sempre somam 2 elevado à n-ésima potência. Isso é obtido a partir do teorema binomial (∗) definindo x = 1 e y = 1. A fórmula também tem uma interpretação combinatória natural: o lado esquerdo soma o número de subconjuntos de {1, ..., n} de tamanhos k = 0, 1, ..., n, dando o número total de subconjuntos. (Ou seja, o lado esquerdo conta o conjunto das partes de {1, ..., n}.) No entanto, esses subconjuntos também podem ser gerados escolhendo ou excluindo sucessivamente cada elemento 1, ..., n; as n escolhas binárias independentes (strings de bits) permitem um total de 2 n {\displaystyle 2^{n}} escolhas. Os lados esquerdo e direito são duas maneiras de contar a mesma coleção de subconjuntos, portanto são iguais.
Identidades com provas combinatórias
Muitas identidades envolvendo coeficientes binomiais podem ser provadas por meios combinatórios. Por exemplo, para inteiros não negativos n ≥ q {\displaystyle {n}\geq {q}} , a identidade ∑ k = q n ( n k ) ( k q ) = 2 n − q ( n q ) {\displaystyle \sum _{k=q}^{n}{\binom {n}{k}}{\binom {k}{q}}=2^{n-q}{\binom {n}{q}}} (que se reduz a (6) quando q = 1) pode receber uma prova de contagem dupla, como segue. O lado esquerdo conta o número de maneiras de selecionar um subconjunto de [n] = {1, 2, ..., n} com pelo menos q elementos, e marcar q elementos entre os selecionados. O lado direito conta a mesma coisa, porque há ( n q ) {\displaystyle {\tbinom {n}{q}}} maneiras de escolher um conjunto de q elementos para marcar, e 2 n − q {\displaystyle 2^{n-q}} para escolher quais dos elementos restantes de [n] também pertencem ao subconjunto.
Identidade de Dixon
A identidade de Dixon é ∑ k = − a a ( − 1 ) k ( 2 a k + a ) 3 = ( 3 a ) ! ( a ! ) 3 {\displaystyle \sum _{k=-a}^{a}(-1)^{k}{\binom {2a}{k+a}}^{3}={\frac {(3a)!}{(a!)^{3}}}} ou, mais geralmente, ∑ k = − a a ( − 1 ) k ( a + b a + k ) ( b + c b + k ) ( c + a c + k ) = ( a + b + c ) ! a ! b ! c ! , {\displaystyle \sum _{k=-a}^{a}(-1)^{k}{\binom {a+b}{a+k}}{\binom {b+c}{b+k}}{\binom {c+a}{c+k}}={\frac {(a+b+c)!}{a!\,b!\,c!}}\,,} onde a, b e c são inteiros não negativos.
Identidades contínuas
Certas integrais trigonométricas têm valores expressáveis em termos de coeficientes binomiais: Para quaisquer m , n ∈ N {\displaystyle m,n\in \mathbb {N} } , ∫ − π π cos ( ( 2 m − n ) x ) cos n ( x ) d x = π 2 n − 1 ( n m ) {\displaystyle \int _{-\pi }^{\pi }\cos((2m-n)x)\cos ^{n}(x)\ dx={\frac {\pi }{2^{n-1}}}{\binom {n}{m}}} ∫ − π π sin ( ( 2 m − n ) x ) sin n ( x ) d x = { ( − 1 ) m + ( n + 1 ) / 2 π 2 n − 1 ( n m ) , n ímpar 0 , caso contrário {\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{ ímpar}}\\0,&{\text{caso contrário}}\end{cases}}} ∫ − π π cos ( ( 2 m − n ) x ) sin n ( x ) d x = { ( − 1 ) m + ( n / 2 ) π 2 n − 1 ( n m ) , n par 0 , caso contrário {\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{ par}}\\0,&{\text{caso contrário}}\end{cases}}}
Congruências
Se n é primo, então ( n − 1 k ) ≡ ( − 1 ) k mod n {\displaystyle {\binom {n-1}{k}}\equiv (-1)^{k}\mod n} para todo k com 0 ≤ k ≤ n − 1 {\displaystyle 0\leq k\leq n-1} . Mais geralmente, isso permanece verdadeiro se n for qualquer número e k for tal que todos os números entre 1 e k sejam coprimos com n. De fato, temos ( n − 1 k ) = ( n − 1 ) ( n − 2 ) ⋯ ( n − k ) 1 ⋅ 2 ⋯ k = ∏ i = 1 k n − i i ≡ ∏ i = 1 k − i i = ( − 1 ) k mod n . {\displaystyle {\binom {n-1}{k}}={(n-1)(n-2)\cdots (n-k) \over 1\cdot 2\cdots k}=\prod _{i=1}^{k}{n-i \over i}\equiv \prod _{i=1}^{k}{-i \over i}=(-1)^{k}\mod n.}
Funções geradoras ordinárias
Para um n fixo, a função geradora ordinária da sequência ( n 0 ) , ( n 1 ) , ( n 2 ) , … {\displaystyle {\tbinom {n}{0}},{\tbinom {n}{1}},{\tbinom {n}{2}},\ldots } é ∑ k = 0 ∞ ( n k ) x k = ( 1 + x ) n . {\displaystyle \sum _{k=0}^{\infty }{\binom {n}{k}}x^{k}=(1+x)^{n}.} Para um k fixo, a função geradora ordinária da sequência ( 0 k ) , ( 1 k ) , ( 2 k ) , … {\displaystyle {\tbinom {0}{k}},{\tbinom {1}{k}},{\tbinom {2}{k}},\ldots } , é ∑ n = 0 ∞ ( n k ) y n = y k ( 1 − y ) k + 1 . {\displaystyle \sum _{n=0}^{\infty }{\binom {n}{k}}y^{n}={\frac {y^{k}}{(1-y)^{k+1}}}.} A função geradora bivariada dos coeficientes binomiais é ∑ n = 0 ∞ ∑ k = 0 n ( n k ) x k y n = 1 1 − y − x y . {\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{n}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-y-xy}}.}
Função geradora exponencial
Uma função geradora exponencial bivariada simétrica dos coeficientes binomiais é: ∑ n = 0 ∞ ∑ k = 0 ∞ ( n + k k ) x k y n ( n + k ) ! = e x + y . {\displaystyle \sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{\binom {n+k}{k}}{\frac {x^{k}y^{n}}{(n+k)!}}=e^{x+y}.}
Em 1852, Kummer provou que se m e n são inteiros não negativos e p é um número primo, então a maior potência de p que divide ( m + n m ) {\displaystyle {\tbinom {m+n}{m}}} é igual a pc, onde c é o número de "vai-uns" quando m e n são somados na base p. Equivalentemente, o expoente de um primo p em ( n k ) {\displaystyle {\tbinom {n}{k}}} é igual ao número de inteiros não negativos j tais que a parte fracionária de k/pj é maior que a parte fracionária de n/pj. (Por exemplo, ( n k ) {\displaystyle {\tbinom {n}{k}}} não é divisível por p se todo dígito na representação base-p de k for menor ou igual ao dígito correspondente na representação base-p de n.) Pode-se deduzir disso que ( n k ) {\displaystyle {\tbinom {n}{k}}} é divisível por n/mdc(n,k). Em particular, portanto, segue que p divide ( p r s ) {\displaystyle {\tbinom {p^{r}}{s}}} para todos os inteiros positivos r e s tais que s < pr. No entanto, isso não é verdade para potências superiores de p: por exemplo, 9 não divide ( 9 6 ) {\displaystyle {\tbinom {9}{6}}} .
Os seguintes limites para ( n k ) {\displaystyle {\tbinom {n}{k}}} valem para todos os valores de n e k tais que 1 ≤ k ≤ n: n k k k ≤ ( n k ) ≤ n k k ! < ( n ⋅ e k ) k . {\displaystyle {\frac {n^{k}}{k^{k}}}\leq {\binom {n}{k}}\leq {\frac {n^{k}}{k!}}<\left({\frac {n\cdot e}{k}}\right)^{k}.} A primeira desigualdade segue do fato de que ( n k ) = n k ⋅ n − 1 k − 1 ⋯ n − ( k − 1 ) 1 {\displaystyle {\binom {n}{k}}={\frac {n}{k}}\cdot {\frac {n-1}{k-1}}\cdots {\frac {n-(k-1)}{1}}} e cada um desses k {\displaystyle k} termos neste produto é ≥ n k {\displaystyle \geq {\frac {n}{k}}} . Um argumento semelhante pode ser feito para mostrar a segunda desigualdade. A última desigualdade estrita é equivalente a e k > k k / k ! {\displaystyle e^{k}>k^{k}/k!} , o que é claro, pois o lado direito é um termo da série exponencial e k = ∑ j = 0 ∞ k j / j ! {\displaystyle e^{k}=\sum _{j=0}^{\infty }k^{j}/j!} .
Tanto n quanto k grandes
A aproximação de Stirling fornece a seguinte aproximação, válida quando n − k , k {\displaystyle n-k,k} ambos tendem ao infinito: ( n k ) ∼ n 2 π k ( n − k ) ⋅ n n k k ( n − k ) n − k {\displaystyle {\binom {n}{k}}\sim {\sqrt {n \over 2\pi k(n-k)}}\cdot {n^{n} \over k^{k}(n-k)^{n-k}}} Como as formas de desigualdade da fórmula de Stirling também limitam os fatoriais, pequenas variações da aproximação assintótica acima fornecem limites exatos. Em particular, quando n {\displaystyle n} é suficientemente grande, tem-se ( 2 n n ) ∼ 2 2 n n π {\displaystyle {\binom {2n}{n}}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}} e n ( 2 n n ) ≥ 2 2 n − 1 {\displaystyle {\sqrt {n}}{\binom {2n}{n}}\geq 2^{2n-1}} . Mais geralmente, para m ≥ 2 e n ≥ 1 (novamente, aplicando a fórmula de Stirling aos fatoriais no coeficiente binomial), n ( m n n ) ≥ m m ( n − 1 ) + 1 ( m − 1 ) ( m − 1 ) ( n − 1 ) . {\displaystyle {\sqrt {n}}{\binom {mn}{n}}\geq {\frac {m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}}}.}
n muito maior que k
Se n é grande e k é o(n) (isto é, se k/n → 0), então ( n k ) ∼ ( n e k ) k ⋅ ( 2 π k ) − 1 / 2 ⋅ exp ( − k 2 2 n ( 1 + o ( 1 ) ) ) {\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)} onde novamente o é a notação pequeno-o.
Somas de coeficientes binomiais
Um limite superior simples para a soma dos coeficientes binomiais pode ser obtido usando uma estimativa aproximada para a fórmula multiplicativa para ( m i ) {\displaystyle {\binom {m}{i}}} e depois o teorema binomial: ∑ i = 0 k ( n i ) ≤ ∑ i = 0 k n i ≤ ∑ i = 0 k ( k i ) n i ⋅ 1 k − i = ( n + 1 ) k . {\displaystyle \sum _{i=0}^{k}{\binom {n}{i}}\leq \sum _{i=0}^{k}n^{i}\leq \sum _{i=0}^{k}{\binom {k}{i}}\,n^{i}\cdot 1^{k-i}=(n+1)^{k}.} Limites mais precisos são dados por 1 8 n ε ( 1 − ε ) ⋅ 2 H ( ε ) ⋅ n ≤ ∑ i = 0 k ( n i ) ≤ 2 H ( ε ) ⋅ n , {\displaystyle {\frac {1}{\sqrt {8n\varepsilon (1-\varepsilon )}}}\cdot 2^{H(\varepsilon )\cdot n}\leq \sum _{i=0}^{k}{\binom {n}{i}}\leq 2^{H(\varepsilon )\cdot n},} válidos para todos os inteiros n > k ≥ 1 {\displaystyle n>k\geq 1} com ε ≐ k / n ≤ 1 / 2 {\displaystyle \varepsilon \doteq k/n\leq 1/2} .
Coeficientes binomiais generalizados
A fórmula do produto infinito para a função gama também dá uma expressão para coeficientes binomiais ( − 1 ) k ( z k ) = ( − z + k − 1 k ) = 1 Γ ( − z ) 1 ( k + 1 ) z + 1 ∏ j = k + 1 ( 1 + 1 j ) − z − 1 1 − z + 1 j {\displaystyle (-1)^{k}{\binom {z}{k}}={\binom {-z+k-1}{k}}={\frac {1}{\Gamma (-z)}}{\frac {1}{(k+1)^{z+1}}}\prod _{j=k+1}{\frac {\left(1+{\frac {1}{j}}\right)^{-z-1}}{1-{\frac {z+1}{j}}}}} que fornece as fórmulas assintóticas ( z k ) ≈ ( − 1 ) k Γ ( − z ) k z + 1 e ( z + k k ) = k z Γ ( z + 1 ) ( 1 + z ( z + 1 ) 2 k + O ( k − 2 ) ) {\displaystyle {\binom {z}{k}}\approx {\frac {(-1)^{k}}{\Gamma (-z)k^{z+1}}}\qquad {\text{e}}\qquad {\binom {z+k}{k}}={\frac {k^{z}}{\Gamma (z+1)}}\left(1+{\frac {z(z+1)}{2k}}+{\mathcal {O}}\left(k^{-2}\right)\right)} quando k → ∞ {\displaystyle k\to \infty } .
