Coeficiente binomial

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Número de subconjuntos de um determinado tamanho

Os coeficientes binomiais podem ser dispostos a formar o triângulo de Pascal, no qual cada entrada é a soma dos dois imediatamente acima.

Visualização da expansão binomial até o 4o poder

Em matemática, o coeficientes binomiais são os inteiros positivos que ocorrem como coeficientes no teorema binomial. Comumente, um coeficiente binomial é indexado por um par de inteiros $n \geq k \geq 0$ e está escrito ${displaystyle {tbinom {n}{k}}.}$ É o coeficiente do $x k$ termo na expansão polinomial do poder binomial $(1+ x) n$ ; este coeficiente pode ser computado pela fórmula multiplicativa

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

que usando notação fatorial pode ser expresso de forma compacta como

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

Por exemplo, a quarta potência de $1 + x$ é

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

e o coeficiente binomial ${displaystyle {tbinom {4}{2}}={tfrac {4times 3}{2times 1}}={tfrac {4!}{2!2!}}=6}$ é o coeficiente do $x 2$ termo.

Organizar os números ${displaystyle {tbinom {n}{0}},{tbinom {n}{1}},ldots{tbinom {n}{n}}}$ em linhas sucessivas para $n=0,1,2,ldots$ dá uma matriz triangular chamada triângulo de Pascal, satisfazendo a relação de recorrência

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

Os coeficientes binomiais ocorrem em muitas áreas de matemática, e especialmente em combinatória. O símbolo ${tbinom {n}{k}}$ é geralmente lido como " $n$ escolher $k$ porque há ${tbinom {n}{k}}$ maneiras de escolher um subconjunto (não ordenado) de $k$ elementos de um conjunto fixo de $n$ elementos. Por exemplo, há ${displaystyle {tbinom {4}{2}}=6}$ maneiras de escolher 2 elementos de ${displaystyle {1,2,3,4},}$ a) ${displaystyle {1,2},,{1,3},,{1,4},,{2,3},,{2,4},}$ e ${displaystyle {3,4}.}$

Os coeficientes binomiais podem ser generalizados para ${displaystyle {tbinom {z}{k}}}$ para qualquer número complexo $zangão.$ e inteiro $k \geq 0$ , e muitas de suas propriedades continuam a manter nesta forma mais geral.

Histórico e notação

Andreas von Ettingshausen introduziu a notação ${tbinom {n}{k}}$ em 1826, embora os números fossem conhecidos séculos antes (veja o triângulo de Pascal). Em cerca de 1150, o matemático indiano Bhaskaracharya deu uma exposição de coeficientes binomiais em seu livro Līlāvatī.

As notações alternativas incluem $C (n, k)$ , $n C k$ , ⁿC_k, $C k n$ , $C n k$ e $C n, k$ em todos os quais $C$ significa combinações ou escolhas. Muitas calculadoras usam variantes da notação $C$ porque podem representá-la em uma exibição de linha única. Nesta forma, os coeficientes binomiais são facilmente comparados com k-permutações de n, escritas como $P (n, k)$ , etc.

Definição e interpretações

k n	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	⋯
FORMAÇÃO	FORMAÇÃO	FORMAÇÃO	FORMAÇÃO	FORMAÇÃO	FORMAÇÃO	⋱
Os primeiros poucos coeficientes binomiais em um triângulo de Pascal alinhado à esquerda

Para números naturais (taken to include 0) n e k, o coeficiente binomial ${tbinom {n}{k}}$ pode ser definido como o coeficiente do monomial X^k na expansão de $(1+ X) n$ . O mesmo coeficiente também ocorre (se $k \leq n$ ) na fórmula binomial

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

(∗)

(válido para quaisquer elementos x, y de um anel comutativo), o que explica o nome "coeficiente binomial n#34;.

Outra ocorrência deste número é em combinatória, onde dá o número de maneiras, ordem de desconsideração, que k objetos podem ser escolhidos de entre n objetos; mais formalmente, o número de k-subconjuntos de elementos (ou k-combinações) de um n- Conjunto de elementos. Este número pode ser visto como igual ao da primeira definição, independentemente de qualquer uma das fórmulas abaixo para computá-lo: se em cada uma das n fatores do poder $(1+ X) n$ um temporariamente rotula o termo X com um índice Eu... (correndo de 1 para 1 n), então cada subconjunto de k índices dá após a expansão uma contribuição X^k, e o coeficiente desse monomial no resultado será o número de tais subconjuntos. Isto mostra, em particular, que ${tbinom {n}{k}}$ é um número natural para qualquer número natural n e k. Há muitas outras interpretações combinatórias de coeficientes binomiais (contando problemas para os quais a resposta é dada por uma expressão de coeficiente binomial), por exemplo, o número de palavras formadas de n bits (digitos 0 ou 1) cuja soma é k é dado por ${tbinom {n}{k}}$ , enquanto o número de maneiras de escrever ${displaystyle k=a_{1}+a_{2}+cdots +a_{n}}$ onde todos um_Eu... é um inteiro nonnegative é dado por ${tbinom {n+k-1}{n-1}}$ . A maioria dessas interpretações são facilmente vistas como equivalentes à contagem k- Combinações.

Calculando o valor dos coeficientes binomiais

Vários métodos existem para calcular o valor de ${tbinom {n}{k}}$ sem realmente expandir um poder binomial ou contar k- Combinações.

Fórmula recursiva

Um método usa a fórmula recursiva puramente aditiva

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

n,k

{displaystyle 1leq kleq n-1,}

com valores iniciais/limites

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

{displaystyle ngeq 0.}

A fórmula segue de considerar o conjunto ${1, 2, 3,..., n ?$ e contando separadamente (a) o k- agrupamentos de elementos que incluem um determinado elemento definido, dizer "Eu...", em cada grupo (desde "Eu..." já é escolhido para preencher um ponto em cada grupo, só precisamos escolher $k - 1$ do restante $n - 1$ ) e (b) todos os k- agrupamentos que não incluem "Eu..."; isto enumera todos os possíveis k-combinações de n elementos. Além disso, resulta do acompanhamento das contribuições X^k em $(1+ X) n - Sim. (1+ X)$ . Como há zero $X n + 1$ ou $X - Sim.$ em $(1+ X) n$ , pode-se estender a definição além dos limites acima para incluir ${displaystyle {tbinom {n}{k}}=0}$ quando $k > n$ ou $k < 0$ . Esta fórmula recursiva permite então a construção do triângulo de Pascal, cercado por espaços brancos onde os zeros, ou os coeficientes triviais, seriam.

Fórmula multiplicativa

Um método mais eficiente para calcular coeficientes binomiais individuais é dado pela 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}},}

n^{underline {k}}

knk

Devido à simetria do coeficiente binomial em relação a k e $n - k$ , o cálculo pode ser otimizado definindo o limite superior do produto acima como o menor de k e $n - k$ .

Fórmula fatorial

Finalmente, embora computacionalmente inadequada, existe a forma compacta, frequentemente usada em provas e derivações, que faz uso repetido da conhecida função fatorial:

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

(n - Sim. k)!

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

(1)

o que leva a uma rotina computacional multiplicativa mais eficiente. Usando a notação fatorial decrescente,

{frac {n}{2}}end{cases}}.}" display="block" xmlns="http://www.w3.org/1998/Math/MathML">(nk)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(nkNão. Não. /k!sek≤ ≤ n2nn- Sim. - Sim. kNão. Não. /(n- Sim. - Sim. k)!sek>n2.{displaystyle {binom {n}{k}}={begin{cases}n^{underline {k}}/k!&{text{if }} kleq {frac {n}{2}}\n^{underline {n-k}}/(n-k)!&{text{if }} ? {n}{2}}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;"/>

Generalização e conexão com a série binomial

A fórmula multiplicativa permite estender a definição dos coeficientes binomiais substituindo n por um número arbitrário α (negativo, real, complexo) ou mesmo um elemento de qualquer anel comutativo no qual todos os inteiros positivos são inversíveis:

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

Com esta definição, tem-se uma generalização da fórmula binomial (com uma das variáveis definidas para 1), que justifica ainda chamar a ${tbinom {alpha }{k}}$ coeficientes binomiais:

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

(2)

Esta fórmula é válida para todos os números complexos α e X com |X| < 1. Também pode ser interpretado como uma identidade de séries de potências formais em X, onde na verdade pode servir como definição de potências arbitrárias de séries de potências com coeficiente constante igual a 1; o ponto é que, com esta definição, todas as identidades que se espera para exponenciação são mantidas, notadamente

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

Se α for um inteiro não negativo n, então todos os termos com $k > n$ são zero e a série infinita torna-se uma soma finita, recuperando assim a fórmula binomial. No entanto, para outros valores de α, incluindo inteiros negativos e números racionais, a série é realmente infinita.

Triângulo de Pascal

1000a linha do triângulo de Pascal, disposta verticalmente, com representações em escala cinzenta de dígitos decimais dos coeficientes, alinhados à direita. O limite esquerdo da imagem corresponde aproximadamente ao gráfico do logaritmo dos coeficientes binomiais, e ilustra que formam uma sequência de log-concave.

A regra de Pascal é a importante relação de recorrência

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

(3)

que pode ser usado para provar por indução matemática que ${tbinom {n}{k}}$ é um número natural para todos os inteiros n ≥ 0 e todos os inteiros k, um fato que não é imediatamente óbvio 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:

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 da linha $n$ contém os números ${tbinom {n}{k}}$ para $k = 0,..., n$ . É construído pela primeira vez colocando 1s nas posições mais externas, e depois preenchendo cada posição interna com a soma dos dois números diretamente 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 fora 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}.}

Combinatória e estatística

Os coeficientes binomiais são importantes em combinatória, porque fornecem fórmulas prontas para certos problemas de contagem frequentes:

Há ${tbinom {n}{k}}$ maneiras de escolher k elementos de um conjunto de n elementos. Veja Combinação.
Há ${tbinom {n+k-1}{k}}$ maneiras de escolher k elementos de um conjunto de n elementos se as repetições forem permitidas. Veja Multiset.
Há ${tbinom {n+k}{k}}$ strings contendo k e n zeros.
Há ${tbinom {n+1}{k}}$ strings que consistem em k e n zeros de tal que nenhum dois são adjacentes.
Os números catalães são ${tfrac {1}{n+1}}{tbinom {2n}{n}}.$
A distribuição binomial em estatísticas é ${displaystyle {tbinom {n}{k}}p^{k}(1-p)^{n-k}.}$

Coeficientes binomiais como polinômios

Para qualquer inteiro nonnegative k, a expressão ${textstyle {binom {t}{k}}}$ pode ser simplificado e definido como um polinomial 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}};}

isto 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 polinomial ${tbinom {t}{k}}$ pode ser caracterizado como o grau único k polinomial $p ())$ satisfazendo $p (0) p (1) = p (k - 1) = 0$ e $p (k) = 1$ .

Seus coeficientes são expressos em termos de números de Stirling do primeiro tipo:

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

O derivado de ${tbinom {t}{k}}$ pode ser calculado pela diferenciação logarítmica:

{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 ${displaystyle 0}$ para $t-1$ , mas usando identidades abaixo podemos computar o 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 binomiais como base para o espaço de polinômios

Sobre qualquer campo de característica 0 (isto é, qualquer campo que contenha os números racionais), cada polinomial p()) de grau no máximo D é exclusivamente expressível como uma combinação linear ${textstyle sum _{k=0}^{d}a_{k}{binom {t}{k}}}$ de coeficientes binomiais. O coeficiente um_k é a diferença kth da sequência p(0), p(1),..., p(k). Provavelmente,

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

(4)

Polinômios de valor inteiro

Cada polinomial ${tbinom {t}{k}}$ é integer-valued: tem um valor inteiro em todas as entradas de inteiro $t$ . (Uma maneira de provar isso é por indução em k, usando a identidade de Pascal.) Portanto, qualquer combinação linear de inteiro de polinômios de coeficiente binomial é integer-valorizado também. Por outro lado,4) mostra que qualquer polinomial de valor inteiro é uma combinação linear de inteiro destes polinômios de coeficiente binomial. Mais geralmente, para qualquer subring R de um campo característica 0 KK, um polinômio em KKNão.)] leva valores em R em todos os inteiros se e somente se for um R- combinação linear de polinômios de coeficiente binomial.

Exemplo

O polinômio de valor inteiro $3 t (3 t + 1) / 2$ pode ser reescrito como

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

Identidades envolvendo coeficientes binomiais

A fórmula fatorial facilita a relação de coeficientes binomiais próximos. Por exemplo, se k for um número inteiro positivo e n for arbitrário, então

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

(5)

e, com um pouco mais de trabalho,

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

Também podemos obter

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

Além disso, o seguinte pode 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 a constante n, temos a seguinte recorrência:

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

Resumindo, temos

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

Somas dos coeficientes binomiais

A fórmula

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

(Facilidade de responsabilidade)

diz os elementos no $n$ a linha do triângulo de Pascal sempre adicionar até 2 elevado ao $n$ O poder. Isto é obtido a partir do teorema binomial (∗) por definição x = 1 e Sim. = 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. (Isso é, o lado esquerdo conta o conjunto de energia de {1,..., n} No entanto, esses subconjuntos também podem ser gerados escolhendo sucessivamente ou excluindo cada elemento 1,..., n; n escolhas binárias independentes (strings bits) permitem um total de $2^{n}$ escolhas. Os lados esquerdo e direito são duas maneiras de contar a mesma coleção de subconjuntos, então eles são iguais.

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

siga do teorema binomial depois de derivar em relação a $x$ (duas vezes para o último) e então substituir $x = y = 1$ .

A identidade Chu-Vandermonde, que vale para quaisquer valores complexos m e n e qualquer inteiro não negativo k, é

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

(7)

e pode ser encontrado por exame do coeficiente de $x^{k}$ na expansão de $(1+ x) m (1+ x) n - Sim. m (1+) x) n$ usando equação (2). Quando $m = 1$ , equação (7) reduz a equação (3). No caso especial $n = 2 m, k = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = m$ , usando (1), a expansão (7) torna-se (como visto no triângulo de Pascal à direita)

{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, linhas 0 através 7. Equação 8 para

m = 3

é ilustrado em linhas 3 e 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)

onde o termo do lado direito é um coeficiente binomial central.

Outra forma da identidade Chu–Vandermonde, que se aplica a quaisquer números inteiros j, k e n que satisfaçam $0 \leq j \leq k \leq n$ , é

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

(9)

A prova é semelhante, mas usa a expansão da série binomial (2) com expoentes inteiros negativos. Quando $j = k$ , a equação (9) fornece a identidade do taco de hóquei

{displaystyle sum _{m=k}^{n}{binom {m}{k}}={binom {n+1}{k+1}}}

e seu parente

{displaystyle sum _{r=0}^{m}{binom {n+r}{r}}={binom {n+m+1}{m}}.}

Deixe F(n) denotar o n-ésimo número de Fibonacci. Então

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

Isso pode ser provado por indução usando (3) ou pela representação de Zeckendorf. Uma prova combinatória é dada a seguir.

Multisseções de somas

Para inteiros S e ) tal que $<math alttext="{displaystyle 0leq t 0\leq \leq )<S,{displaystyle 0leq t<s,} <img alt="{displaystyle 0leq t$ ~~multissecção série dá a seguinte identidade para a soma de coeficientes binomiais:~~

~~${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 $s$ pequenos, essas séries têm formas particularmente agradáveis; por exemplo,~~

~~${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)}$~~

Somas parciais

~~Embora não exista fórmula fechada para somas parciais~~

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

~~de coeficientes binomiais, pode-se novamente usar (3) e indução 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}},}$~~

~~com caso especial~~

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

~~para n > 0. Este último resultado também é um caso especial do resultado da teoria das diferenças finitas que para qualquer polinômio P(x) de grau menor que n,~~

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

~~Diferenciação (2) k tempos e configuração x = −1 produz isto para $P(x)=x(x-1)cdots (x-k+1)$ , quando 0 ≤ k < n, e o caso geral segue tomando combinações lineares destes.~~

~~Quando P(x) é de grau menor ou igual a n,~~

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

(10.)

~~Onde? $a_{n}$ é o coeficiente de grau n em P(x).~~

~~Mais geralmente para (10),~~

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

Onde? m e D são números complexos. Isto segue imediatamente a aplicação (10.) ao polinômio ${displaystyle Q(x):=P(m+dx)}$ em vez de $P(x)$ e observando isso $Q(x)$ ainda tem grau menor ou igual a n, e que seu coeficiente de grau n o Dⁿum_n.

A série ${textstyle {frac {k-1}{k}}sum _{j=0}^{infty }{frac {1}{binom {j+x}{k}}}={frac {1}{binom {x-1}{k-1}}}}$ é convergente para k ≥ 2. Esta fórmula é usada na análise do problema do tanque alemão. Daqui resulta ${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 é provado pela indução em M.

Identidades com provas combinatórias

~~Muitas identidades envolvendo coeficientes binomiais podem ser comprovadas por meios combinatórios. Por exemplo, para inteiros nonnegativos ${n}geq {q}$ , a identidade~~

~~${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 ser dada uma prova de contagem dupla, como segue. O lado esquerdo conta o número de maneiras de selecionar um subconjunto de [nNão. nCom pelo menos q elementos, e marcação q elementos entre os selecionados. O lado direito conta a mesma coisa, porque há ${tbinom {n}{q}}$ formas de escolher um conjunto de q elementos para marcar, e ${displaystyle 2^{n-q}}$ escolher qual dos elementos restantes de [n] também pertencem ao subconjunto.

~~Na identidade de Pascal~~

~~${displaystyle {n choose k}={n-1 choose k-1}+{n-1 choose k},}$~~

~~ambos os lados contam o número de subconjuntos de elementos k de [n]: os dois termos do lado direito os agrupam naqueles que contêm o elemento n e aqueles que não.~~

~~A identidade (8) também possui uma prova combinatória. A identidade lê~~

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

Suponha que você tenha $2n$ quadrados vazios dispostos em uma linha e você quer marcar (selecionar) n deles. Há ${tbinom {2n}{n}}$ maneiras de fazer isso. Por outro lado, você pode selecionar seu n quadrados selecionando k quadrados de entre os primeiros n e $n-k$ quadrados dos restantes n quadrados; qualquer k de 0 a n vai funcionar. Isto dá

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

~~Agora aplique (1) para obter o resultado.~~

~~Se alguém denotar por $F (i)$ a sequência de números de Fibonacci, indexados de forma que $F (0) = F (1) = 1$ , então a identidade~~

{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 - Sim. k$ ${tbinom {n-k}{k}}$ $k$
Soma da linha de coeficientes
O número de k-combinações para todos k, ${textstyle sum _{0leq {k}leq {n}}{binom {n}{k}}=2^{n}}$ , é a soma da na linha (contando de 0) dos coeficientes binomiais. Estas combinações são enumeradas pelos 1 dígitos do conjunto de números base 2 que contam de 0 a $2^{n}-1$ , onde cada posição de dígito é um item do conjunto de n.
Identidade de Dixon
A identidade de Dixon é
$sum _{k=-a}^{a}(-1)^{k}{2a choose k+a}^{3}={frac {(3a)!}{(a!)^{3}}}$
ou, de forma mais geral,
${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!}},,}$
onde a, b e c são inteiros não negativos.
Identidades contínuas
Determinadas integrais trigonométricas têm valores expressíveis em termos de coeficientes binomiais: Para qualquer ${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}}}$
Isso pode ser provado usando a fórmula de Euler para converter funções trigonométricas em exponenciais complexas, expandindo usando o teorema binomial e integrando termo a termo.
Congruências
Se n for primo, então
${displaystyle {binom {n-1}{k}}equiv (-1)^{k}mod n}$ k ${displaystyle 0leq kleq n-1.}$ nkkn
De fato, temos
${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.}$
Gerando funções
Funções geradoras comuns
Para um fixo $n$ , a função de geração ordinária da sequência ${displaystyle {tbinom {n}{0}},{tbinom {n}{1}},{tbinom {n}{2}},ldots }$ o
${displaystyle sum _{k=0}^{infty }{n choose k}x^{k}=(1+x)^{n}.}$
Para um fixo $k$ , a função de geração ordinária da sequência ${displaystyle {tbinom {0}{k}},{tbinom {1}{k}},{tbinom {2}{k}},ldots}$ o
${displaystyle sum _{n=0}^{infty }{n choose k}y^{n}={frac {y^{k}}{(1-y)^{k+1}}}.}$
A função geradora bivariada dos coeficientes binomiais é
${displaystyle sum _{n=0}^{infty }sum _{k=0}^{n}{n choose k}x^{k}y^{n}={frac {1}{1-y-xy}}.}$
Uma função geradora bivariada simétrica dos coeficientes binomiais é
${displaystyle sum _{n=0}^{infty }sum _{k=0}^{infty }{n+k choose k}x^{k}y^{n}={frac {1}{1-x-y}}.}$
que é o mesmo que a função geradora anterior após a substituição ${displaystyle xto xy}$ .
Função de geração exponencial
Uma função geradora bivariada exponencial simétrica dos coeficientes binomiais é:
${displaystyle sum _{n=0}^{infty }sum _{k=0}^{infty }{n+k choose k}{frac {x^{k}y^{n}}{(n+k)!}}=e^{x+y}.}$
Propriedades de divisibilidade
Em 1852, Kummer provou que se m e n são inteiros nonnegativos e p é um número primo, então o maior poder de p divisão ${tbinom {m+n}{m}}$ iguais p^c, onde c é o número de transporte quando m e n são adicionados na base p. Equivalentemente, o expoente de um primo p em ${tbinom {n}{k}}$ igual ao número de inteiros nonnegativos JJ tal que a parte fracionada de k/p^JJ é maior do que a parte fracionada de n/p^JJ. Pode ser deduzido disto que ${tbinom {n}{k}}$ é divisível por n/gcd(n,k). Por conseguinte, em particular, segue-se o seguinte: p divide ${tbinom {p^{r}}{s}}$ para todos os inteiros positivos R e S tal que $S < p R$ . No entanto, isso não é verdade para poderes mais elevados de p: por exemplo 9 não se divide ${tbinom {9}{6}}$ .
Um resultado um tanto surpreendente por David Singmaster (1974) é que qualquer inteiro divide quase todos os coeficientes binomiais. Mais precisamente, corrigir um inteiro D e deixar f(N) denota o número de coeficientes binomiais ${tbinom {n}{k}}$ com n < N tal que D divide ${tbinom {n}{k}}$ . Então...
$lim _{Nto infty }{frac {f(N)}{N(N+1)/2}}=1.$
Desde o número de coeficientes binomiais ${tbinom {n}{k}}$ com n < N o N(N + 1) / 2, isso implica que a densidade de coeficientes binomiais divisível por D vai para 1.
Os coeficientes binomiais têm propriedades de divisibilidade relacionadas aos mínimos múltiplos comuns de números inteiros consecutivos. Por exemplo:
${displaystyle {binom {n+k}{k}}}$ divide ${displaystyle {frac {operatorname {lcm} (n,n+1,ldotsn+k)}{n}}}$ .
${displaystyle {binom {n+k}{k}}}$ é um múltiplo de ${displaystyle {frac {operatorname {lcm} (n,n+1,ldotsn+k)}{ncdot operatorname {lcm} ({binom {k}{0}},{binom {k}{1}},ldots{binom {k}{k}})}}}$ .
Outro fato: Um inteiro $n \geq 2$ é primo se e somente se todos os coeficientes binomiais intermediários
${binom {n}{1}},{binom {n}{2}},ldots{binom {n}{n-1}}$
são divisíveis por n.
Prova: Quando p é 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}}}$ é um número natural e p divide o numerador, mas não o denominador. Quando n é composto, deixa p ser o menor fator principal de n e deixar $k = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = n / p$ . Então... $0 < p < n$ e
${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}}$
caso contrário, o numerador $k (n - 1)(n - 2)\dots(n - p + 1)$ tem que ser divisível por $n = k \times p$ , este só pode ser o caso quando $(n - 1)(n - 2)\dots(n - p + 1)$ é divisível por p. Mas n é divisível por p, então p não divide $n - 1, n - 2, \dots, n - p + 1$ e porque p é primo, sabemos que p não divide $(n - 1)(n - 2)\dots(n - p + 1)$ e, portanto, o numerador não pode ser divisível por n.
Limites e fórmulas assintóticas
Os seguintes limites para ${tbinom {n}{k}}$ manter para todos os valores de n e k tal 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 {n^{k}}{k^{k}}}}}leq {n choose k}leq {frac {n^{k}}{k!}}<left({frac {ncdot e}{k}}right)^{k}.}<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!- Sim.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!}$
Das propriedades de divisibilidade 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}},}$
Os seguintes limites são úteis na teoria da informação:
${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}{2pi k(n-k)}}}2^{nH(k/n)}}$ $1 leq k leq n-1$
Ambos n e k grandes
A aproximação de Stirling produz a seguinte aproximação, válida quando $n,k$ ambos tendem 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)}}}.}$
Se n é grande e k é linear em n, várias estimativas assintóticas precisas existem para o coeficiente binomial ${textstyle {binom {n}{k}}}$ . Por exemplo, se ${displaystyle |n/2-k|=o(n^{2/3})}$ então
${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 muito maior que k
Se $n$ for grande e $k$ é $o (n)$ (ou seja, se $k / n \to 0$ ), então
${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$
Somas de coeficientes binomiais
Um limite superior simples e aproximado para a soma dos coeficientes binomiais pode ser obtido usando o 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>kgeqq 1kgeq 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 binomiais generalizados
A fórmula do produto infinito para a função gama também fornece uma expressão para coeficientes binomiais
${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$
Esse comportamento assintótico está contido na aproximação
${displaystyle {z+k choose k}approx {frac {e^{z(H_{k}-gamma)}}{Gamma (z+1)}}}$ $H_{k}$ k $gamma$
Além disso, a fórmula assintó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$
Generalizações
Generalização para multinômios
Coeficientes binomiais podem ser generalizados para coeficientes multinomiais definidos como o número:
${n choose k_{1},k_{2},ldotsk_{r}}={frac {n!}{k_{1}!k_{2}!cdots k_{r}!}}$
onde
$sum _{i=1}^{r}k_{i}=n.$
Enquanto os coeficientes binomiais representam os coeficientes de (x+y)ⁿ, os coeficientes multinomiais representam os coeficientes do polinômio
${displaystyle (x_{1}+x_{2}+cdots +x_{r})^{n}.}$
O caso r = 2 dá coeficientes binomiais:
${n choose k_{1},k_{2}}={n choose k_{1},n-k_{1}}={n choose k_{1}}={n choose k_{2}}.$
A interpretação combinatória de coeficientes multinomiais é a distribuição de n elementos distinguíveis sobre recipientes r (distinguíveis), cada um contendo exatamente k_i elementos, onde i é o índice do contêiner.
Os coeficientes multinomiais têm muitas propriedades semelhantes às dos coeficientes binomiais, por exemplo, a relação de recorrência:
${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}$
e simetria:
${n choose k_{1},k_{2},ldotsk_{r}}={n choose k_{sigma _{1}},k_{sigma _{2}},ldotsk_{sigma _{r}}}$
Onde? $(sigma _{i})$ é uma permutação de (1, 2,..., R).
Série Taylor
Usando números Stirling do primeiro tipo a expansão da série em torno de qualquer ponto arbitrariamente escolhido $z_{0}$ o
${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 com n = 1/2
A definição dos coeficientes binomiais pode ser estendida ao caso em que $n$ é real e $k$ é inteiro.
Em particular, a seguinte identidade é válida para qualquer inteiro não negativo $k$ :
${{1/2} choose {k}}={{2k} choose {k}}{frac {(-1)^{k+1}}{2^{2k}(2k-1)}}.$
Isso aparece quando se expande ${sqrt {1+x}}$ em uma série de energia usando a série binomial de Newton:
${displaystyle {sqrt {1+x}}=sum _{kgeq 0}{binom {1/2}{k}}x^{k}.}$
Produtos de coeficientes binomiais
Pode-se expressar o produto de dois coeficientes binomiais como uma combinação linear de coeficientes binomiais:
${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},}$
onde os coeficientes de conexão são coeficientes multinomiais. Em termos de objetos combinatórios rotulados, os coeficientes de conexão representam o número de maneiras de atribuir $m + n - k$ a um par de objetos combinatórios rotulados — de peso m e n respectivamente — que tiveram seus primeiros k rótulos identificados, ou colados para obter um novo objeto combinatório rotulado de peso $m + n - k$ . (Isto é, separar os rótulos em três porções para aplicar à parte colada, à parte não colada do primeiro objeto e à parte não colada do segundo objeto.) Nesse sentido, os coeficientes binomiais são para as séries geradoras exponenciais o que os fatoriais decrescentes são para série geradora ordinária.
O produto de todos os coeficientes binomiais na nésima linha do triângulo de Pascal é dado pela fórmula:
${displaystyle prod _{k=0}^{n}{binom {n}{k}}=prod _{k=1}^{n}k^{2k-n-1}.}$
Decomposição de frações parciais
A decomposição em frações parciais do recíproco é 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}}.}$
Série binomial de Newton
A série binomial de Newton, em homenagem a Sir Isaac Newton, é uma generalização do teorema binomial para séries infinitas:
$(1+z)^{alpha }=sum _{n=0}^{infty }{alpha choose n}z^{n}=1+{alpha choose 1}z+{alpha choose 2}z^{2}+cdots.$
A identidade pode ser obtida mostrando que ambos os lados satisfazem a equação diferencial $(1 + z) f' (z) = α f (z)$ .
O raio de convergência desta série é 1. Uma expressão alternativa é
${frac {1}{(1-z)^{alpha +1}}}=sum _{n=0}^{infty }{n+alpha choose n}z^{n}$
onde a identidade
${n choose k}=(-1)^{k}{k-n-1 choose k}$
é aplicado.
Coeficiente binomial multiconjunto (crescente)
Os coeficientes binomiais contam subconjuntos de tamanho prescrito de um determinado conjunto. Um problema combinatorial relacionado é contar multisets de tamanho prescrito com elementos desenhados de um determinado conjunto, ou seja, contar o número de maneiras de selecionar um determinado número de elementos de um determinado conjunto com a possibilidade de selecionar o mesmo elemento repetidamente. Os números resultantes são chamados coeficientes multiset; o número de maneiras de "multicoose" (ou seja, escolha com substituição) k itens de um n conjunto de elementos é denotado ${textstyle left(!!{binom {n}{k}}!!right)}$ .
Para evitar ambigüidade e confusão com a denotação principal de n' neste artigo,
deixe $f = n = r + (k - 1)$ e $r = f - (k - 1)$ .
Coeficientes multiconjuntos podem ser expressos em termos de coeficientes binomiais pela regra
${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}}.}$
Generalização para números inteiros negativos n

Coeficientes binomiais C(n, k) estendido para negativo e fracionado n, ilustrado com um binomial simples. Pode-se observar que o triângulo de Pascal é girado e os termos alternativos são negados. Processo n= −1 dá a série de Grandi.
Para qualquer 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}}$
Em particular, coeficientes binomiais avaliados em inteiros negativos n são dados por coeficientes multiset assinados. No caso especial $n=-1$ , isto reduz a ${displaystyle (-1)^{k}={binom {-1}{k}}=left(!!{binom {-k}{k}}!!right).}$
Por exemplo, se n = −4 e k = 7, então r = 4 e 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}}$
Dois argumentos de valor real ou complexo
O coeficiente binomial é generalizado para dois argumentos de valor real ou complexo usando a função gama ou função beta via
${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 definição herda estas seguintes propriedades adicionais 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};$
além disso,
${x choose y}cdot {y choose x}={frac {sin((x-y)pi)}{(x-y)pi }}.$
A função resultante foi pouco estudada, aparentemente primeiro sendo grafiada em (Fowler 1996). Notavelmente, muitas identidades binomiais falham: ${textstyle {binom {n}{m}}={binom {n}{n-m}}}$ mas... ${textstyle {binom {-n}{m}}neq {binom {-n}{-n-m}}}$ para n positivo (so $-n$ negativo). O comportamento é bastante complexo, e marcadamente diferente em vários octants (isto é, com respeito ao x e Sim. eixos e a linha $y=x$ ), com o comportamento negativo x ter singularidades em valores inteiros negativos e um checkerboard de regiões positivas e negativas:
no octant $0leq yleq x$ é uma forma suavemente interpolada do binomial habitual, com um cume ("Cusco de Pancal").
no octant $0leq xleq y$ e no quadrante $xgeq 0,yleq 0$ a função é próxima de zero.
no quadrante $xleq 0,ygeq 0$ a função é alternadamente muito grande positivo e negativo nos paralelogramas com vértices ${displaystyle (-n,m+1),(-n,m),(-n-1,m-1),(-n-1,m)}$
no octant $x>y}" xmlns="http://www.w3.org/1998/Math/MathML">0>x>Sim.- Sim. 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;"/>$ o comportamento é novamente alternadamente muito grande positivo e negativo, mas em uma grade quadrada.
no octant $y>x+1}" xmlns="http://www.w3.org/1998/Math/MathML">- Sim. - Sim. 1>Sim.>x+1Não. -1>x+1 y>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;"/>$ é perto de zero, exceto para perto das singularidades.
Generalização para série q
O coeficiente binomial tem uma generalização q-analógica conhecida como coeficiente binomial gaussiano.
Generalização para cardinais infinitos
A definição do coeficiente binomial pode ser generalizada para cardinais infinitos definindo:
${displaystyle {alpha choose beta }=left|left{Bsubseteq A:left|Bright|=beta right}right|}$
onde A é um conjunto com cardinalidade $alpha$ . Pode-se mostrar que o coeficiente binomial generalizado é bem definido, no sentido de que não importa o conjunto que escolhemos representar o número cardinal $alpha$ , ${textstyle {alpha choose beta }}$ permanecerá o mesmo. Para cardeais finitos, essa definição coincide com a definição padrão do coeficiente binomial.
Assumindo o Axioma da Escolha, pode-se mostrar que ${textstyle {alpha choose alpha }=2^{alpha }}$ para qualquer cardeal infinito $alpha$ .
Em linguagens de programação
A notação ${textstyle {n choose k}}$ é conveniente na caligrafia, mas inconveniente para máquinas de escrever e terminais de computador. Muitas linguagens de programação não oferecem uma subrotina padrão para a computação do coeficiente binomial, mas, por exemplo, tanto a linguagem de programação APL quanto a (relacionada) J linguagem de programação usar a marca de exclamação: k ! n. O coeficiente binomial é implementado em SciPy como scipy.special.com b).
Implementações ingênuas da fórmula fatorial, como o seguinte trecho em Python:
a partir de Matemática importação factorialde binomial_coeficiente(n: - Não., k: - Não.) - Sim. - Não.: retorno factorial(n) // (factorial(k) * factorial(n - Não. k)
são muito lentos e inúteis para calcular fatoriais de números muito altos (em linguagens como C ou Java eles sofrem de erros de estouro por esse motivo). Uma implementação direta da fórmula multiplicativa funciona bem:
de binomial_coeficiente(n: - Não., k: - Não.) - Sim. - Não.: se k < 0 ou k > n: retorno 0 se k - Sim. 0 ou k - Sim. n: retorno 1 k = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = min(k, n - Não. k) # Aproveite a simetria c = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1 para Eu... em gama(k: c = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = c * (n - Não. Eu...) // (Eu... + 1) retorno c
(Em Python, range(k) produz uma lista de 0 a k−1.)
A regra de Pascal fornece uma definição recursiva que também pode ser implementada em Python, embora seja menos eficiente:
de binomial_coeficiente(n: - Não., k: - Não.) - Sim. - Não.: se k < 0 ou k > n: retorno 0 se k > n - Não. k: # Aproveite a simetria k = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = n - Não. k se k - Sim. 0 ou n < 1: retorno 1 retorno binomial_coeficiente(n - Não. 1, k) + binomial_coeficiente(n - Não. 1, k - Não. 1)
O exemplo mencionado acima também pode ser escrito em estilo funcional. O seguinte exemplo de Scheme usa a definição recursiva
${n choose k+1}={frac {n-k}{k+1}}{n choose k}$
A aritmética racional pode ser facilmente evitada usando a divisão inteira
${n choose k+1}=left[(n-k){n choose k}right]div (k+1)$
A implementação a seguir usa todas essas ideias
(definição (binomial n k);; Função de ajuda para computar C(n,k) via recursão para a frente (definição (binomial-iter n k Eu... prevários) (se (- Sim. Eu... k) prevários (binomial-iter n k (+ Eu... 1) (/ (* (- Não. n Eu...) prevários) (+ Eu... 1)));; Usar propriedade de simetria C(n,k)=C(n, n-k) (se (< k (- Não. n k) (binomial-iter n k 0 1) (binomial-iter n (- Não. n k) 0 1)
Quando a computação ${textstyle {n choose k+1}=left[(n-k){n choose k}right]div (k+1)}$ em uma linguagem com inteiros de comprimento fixo, a multiplicação por $(n-k)$ pode transbordar mesmo quando o resultado se encaixasse. O excesso pode ser evitado dividindo primeiro e fixando o resultado usando o restante:
${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)}}$
Implementação na linguagem C:
#include # não assinado longo binomial(não assinado longo n, não assinado longo k) ( não assinado longo c = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1, Eu...; se (k > n- Não.k) // aproveitar a simetria k = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = n- Não.k; para (Eu... = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 1; Eu... < k; Eu...++, n-...) ( se (c/Eu... > IMPOSTO/n) // retornar 0 no fluxo de sobrecarga potencial retorno 0; c = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = c / Eu... * n + c % Eu... * n / Eu...; // dividir c * n / i em (c / i * i + c % i) * n / i ? retorno c;?
Outra forma de calcular o coeficiente binomial ao usar números grandes é reconhecer 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)),}$
Onde? ${displaystyle ln Gamma (n)}$ denota o logaritmo natural da função gama em $n$ . É uma função especial que é facilmente computada e é padrão em algumas linguagens de programação, como usar O que é isso? em Maxima, LogGamma em Mathematica, Gammaln em MATLAB e módulo SciPy do Python, Ingamma em PARI/GP ou Igamma em C, R e Julia. O erro Roundoff pode fazer com que o valor retornado não seja um inteiro.

Contenido relacionado

Conjunto de cantores
Na matemática, o conjunto de Cantor é um conjunto de pontos situados em um único segmento de linha que possui várias propriedades não intuitivas. Foi...
Bijeção
Em matemática, uma bijeção, também conhecida como função bijetiva, correspondência bijetiva ou função invertível , é uma função entre os...
Criptoanálise diferencial
Criptoanálise diferencial é uma forma geral de criptoanálise aplicável principalmente a cifras de bloco, mas também a cifras de fluxo e funções hash...
Más resultados...
Te puede interesar

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

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