Coeficiente binomial - Binomial coefficient
Em matemática , os 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 ≥ k ≥ 0 e é escrito É o coeficiente do termo x k na expansão polinomial da potência binomial (1 + x ) n , e é dado pela fórmula
Por exemplo, a quarta potência de 1 + x é
e o coeficiente binomial é o coeficiente do termo x 2 .
Organizar os números em linhas sucessivas para dá uma matriz triangular chamada triângulo de Pascal , satisfazendo a relação de recorrência
Os coeficientes binomiais ocorrem em muitas áreas da matemática e, especialmente, em combinatória . O símbolo é geralmente lido como " n escolha k " porque há maneiras de escolher um subconjunto (não ordenado) de k elementos a partir de um conjunto fixo de n elementos. Por exemplo, existem maneiras de escolher 2 elementos, a saber e
Os coeficientes binomiais podem ser generalizados para qualquer número complexo z e inteiro k ≥ 0 , e muitas de suas propriedades continuam nesta forma mais geral.
História e notação
Andreas von Ettingshausen introduziu a notação em 1826, embora os números fossem conhecidos séculos antes (veja o triângulo de Pascal ). A mais antiga discussão detalhada conhecida sobre coeficientes binomiais está em um comentário do século X, por Halayudha , sobre um antigo texto em sânscrito , Pingala 's Chandaḥśāstra . Por volta de 1150, o matemático indiano Bhaskaracharya fez uma exposição dos coeficientes binomiais em seu livro Līlāvatī .
Notações alternativas incluem C ( n , k ) , n C k , n C k , C k n , C n k e C n , k , em todos os quais C representa combinações ou escolhas . Muitas calculadoras usam variantes da notação C porque podem representá-la em uma tela de linha única. Nesta forma, os coeficientes binomiais são facilmente comparados a 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 | ⋯ |
⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋱ |
Os primeiros coeficientes binomiais em um triângulo de Pascal alinhado à esquerda |
Para números naturais (considerados como incluindo 0) n e k , o coeficiente binomial pode ser definido como o coeficiente do monômio X k na expansão de (1 + X ) n . O mesmo coeficiente também ocorre (se k ≤ n ) na fórmula binomial
-
( ∗ )
(válido para quaisquer elementos x , y de um anel comutativo ), o que explica o nome "coeficiente binomial".
Outra ocorrência desse número é na combinatória, onde ele fornece o número de maneiras, desconsiderando a ordem, que k objetos podem ser escolhidos entre n objetos; mais formalmente, o número de k subconjuntos de 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 qualquer uma das fórmulas abaixo para computá-lo: se em cada um dos n fatores da potência (1 + X ) n um rotula temporariamente o termo X com um índice i (variando de 1 a n ), então cada subconjunto de índices k dá após a expansão uma contribuição X k , e o coeficiente desse monômio no resultado será o número de tais subconjuntos. Isso mostra em particular que é um número natural para quaisquer números naturais n e k . Existem muitas outras interpretações combinatórias de 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 é dada por , enquanto o número de maneiras de escrever onde todo a i é um inteiro não negativo é dado por . Muitas dessas interpretações são facilmente vistas como equivalentes à contagem de combinações de k .
Calculando o valor dos coeficientes binomiais
Existem vários métodos para calcular o valor de sem realmente expandir uma potência binomial ou contar combinações de k .
Fórmula recursiva
Um método usa a fórmula recursiva puramente aditiva
- para todos os inteiros tais que
com valores iniciais / limites
- para todos os inteiros
A fórmula segue considerando o conjunto {1, 2, 3, ..., n } e contando separadamente (a) os agrupamentos de k- elementos que incluem um elemento de conjunto particular, digamos " i ", em cada grupo (uma vez que " i "já foi escolhido para preencher uma vaga em cada grupo, precisamos apenas escolher k - 1 dos n - 1) restantes e (b) todos os k -grupos que não incluem" i "; isso enumera todas as combinações k possíveis de n elementos. Também segue traçando as contribuições para X k em (1 + X ) n −1 (1 + X ) . Como há zero X n +1 ou X −1 em (1 + X ) n , pode-se estender a definição além dos limites acima para incluir quando k > n ou k <0. Esta fórmula recursiva então permite a construção de Pascal's triângulo , rodeado 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
onde o numerador da primeira fração é expresso como uma potência fatorial decrescente . Esta fórmula é mais fácil de entender para a interpretação combinatória de coeficientes binomiais. O numerador fornece o número de maneiras de selecionar uma sequência de k objetos distintos, mantendo a ordem de seleção, a partir de um conjunto de n objetos. O denominador conta o número de sequências distintas que definem a mesma combinação k quando a ordem é desconsiderada.
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 para o menor de k e n - k .
Fórmula Fatorial
Finalmente, embora computacionalmente inadequada, existe a forma compacta, muitas vezes usada em provas e derivações, que faz uso repetido da função fatorial familiar :
onde n ! denota o fatorial de n . Esta fórmula segue da fórmula multiplicativa acima, multiplicando o numerador e o denominador por ( n - k )! ; como consequência, envolve muitos fatores comuns ao numerador e ao denominador. É menos prático para computação explícita (no caso em que k é pequeno e n é grande), a menos que fatores comuns sejam cancelados primeiro (em particular porque os valores fatoriais crescem muito rapidamente). A fórmula exibe uma simetria que é menos evidente na fórmula multiplicativa (embora seja nas definições)
-
( 1 )
o que leva a uma rotina computacional multiplicativa mais eficiente. Usando a notação fatorial decrescente ,
Generalização e conexão com a série binomial
A fórmula multiplicativa permite a definição de coeficientes binomiais a serem estendidos, substituindo n por um número arbitrário α (negativo, real, complexo) ou mesmo um elemento de qualquer anel comutativo em que todos os inteiros positivos são invertíveis:
Com esta definição, tem-se uma generalização da fórmula binomial (com uma das variáveis definidas como 1), o que justifica ainda chamar os coeficientes binomiais:
-
( 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 mantêm o que se espera para a exponenciação , notavelmente
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
A regra de Pascal é a importante relação de recorrência
-
( 3 )
que pode ser usado para provar por indução matemática que é um número natural para todo inteiro n ≥ 0 e todo inteiro k , um fato que não é imediatamente óbvio pela fórmula (1) . À esquerda e à direita do triângulo de Pascal, as entradas (mostradas 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
O número da linha n contém os números para k = 0, ..., n . Ele é construído colocando primeiro 1s nas posições mais externas e, em seguida, 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 que
Combinatória e estatística
Os coeficientes binomiais são importantes na combinatória , porque fornecem fórmulas prontas para certos problemas de contagem frequentes:
- Existem maneiras de escolher k elementos de um conjunto de n elementos. Veja Combinação .
- Existem maneiras de escolher k elementos de um conjunto de n elementos se repetições forem permitidas. Veja Multiset .
- Existem strings contendo k uns e n zeros.
- Existem strings que consistem em k uns en zeros, de forma que não há dois adjacentes.
- Os números catalães são
- A distribuição binomial nas estatísticas é
Coeficientes binomiais como polinômios
Para qualquer número inteiro não negativo k , a expressão pode ser simplificada e definida como um polinômio dividido por k !:
isto apresenta um polinômio em t com coeficientes racionais .
Como tal, ele pode ser avaliado em qualquer número real ou complexo t para definir coeficientes binomiais com esses primeiros argumentos. Esses "coeficientes binomiais generalizados" aparecem no teorema binomial generalizado de Newton .
Para cada k , o polinômio 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 expressos em termos de números de Stirling de primeiro tipo :
A derivada de pode ser calculada por diferenciação logarítmica :
Isso pode causar um problema quando avaliado em inteiros de a , mas usando as identidades abaixo, podemos calcular a derivada como:
Coeficientes binomiais como base para o espaço de polinômios
Em qualquer campo de característica 0 (ou seja, qualquer campo que contenha os números racionais ), cada polinômio p ( t ) de grau no máximo d é expressável exclusivamente como uma combinação linear de coeficientes binomiais. O coeficiente a k é a k ésima diferença da sequência p (0), p (1), ..., p ( k ). Explicitamente,
-
( 4 )
Polinômios de valor inteiro
Cada polinomial é inteiro de valor : ele tem um valor inteiro em todas as entradas inteiras . (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 coeficiente binomial também tem valor inteiro. Por outro lado, ( 4 ) mostra que qualquer polinômio de valor inteiro é uma combinação linear inteira desses polinômios de coeficiente binomial. De modo mais geral, para qualquer subanel R de um campo K característico 0 , um polinômio em K [ t ] assume valores em R em todos os números inteiros se e somente se for uma combinação R- linear de polinômios de coeficiente binomial.
Exemplo
O polinômio de valor inteiro 3 t (3 t + 1) / 2 pode ser reescrito como
Identidades envolvendo coeficientes binomiais
A fórmula fatorial facilita o relacionamento dos coeficientes binomiais próximos. Por exemplo, se k é um número inteiro positivo e n é arbitrário, então
-
( 5 )
e, com um pouco mais de trabalho,
Além disso, o seguinte pode ser útil:
Para n constante , temos a seguinte recorrência:
Soma dos coeficientes binomiais
A fórmula
-
( ∗∗ )
diz que os elementos no n º linha do triângulo de Pascal sempre adicionar até 2 elevado à n º poder. Isso é obtido a partir do teorema binomial ( ∗ ), definindo x = 1 ey = 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 de potência 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 (cadeias de bits) permitem um total de escolhas. Os lados esquerdo e direito são duas maneiras de contar a mesma coleção de subconjuntos, portanto, eles são iguais.
As fórmulas
-
( 6 )
e
siga do teorema binomial após a diferenciação com respeito ax (duas vezes para o último) e então substituindo x = y = 1 .
A identidade Chu-Vandermonde , que vale para quaisquer valores complexos m e n e qualquer número inteiro não negativo k , é
-
( 7 )
e pode ser encontrado pelo exame do coeficiente de na expansão de (1 + x ) m (1 + x ) n - m = (1 + x ) n usando a equação ( 2 ). Quando m = 1 , a equação ( 7 ) se reduz à 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)
-
( 8 )
onde o termo do lado direito é um coeficiente binomial central .
Outra forma de identidade Chu-Vandermonde, que se aplica a quaisquer inteiros j , k e n que satisfaçam 0 ≤ j ≤ k ≤ n , é
-
( 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 ) dá a identidade do taco de hóquei
e seu parente
Seja F ( n ) o n -ésimo número de Fibonacci . Então
Isso pode ser provado por indução usando ( 3 ) ou pela representação de Zeckendorf . Uma prova combinatória é fornecida abaixo.
Múltiplas seções de somas
Para inteiros s e t de forma que a multissecção em série forneça a seguinte identidade para a soma dos coeficientes binomiais:
Para as pequenas s , essas séries têm formas particularmente agradáveis; por exemplo,
Somas parciais
Embora não haja uma fórmula fechada para somas parciais
de coeficientes binomiais, pode-se novamente usar ( 3 ) e indução para mostrar que para k = 0, ..., n - 1 ,
com caso especial
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 ,
Diferenciar ( 2 ) k vezes e definir x = −1 resulta em , quando 0 ≤ k < n , e o caso geral segue tomando combinações lineares destes.
Quando P ( x ) é de grau menor ou igual a n ,
-
( 10 )
onde é o coeficiente de grau n em P ( x ).
Mais geralmente para ( 10 ),
onde m e d são números complexos. Isso segue imediatamente aplicando ( 10 ) ao polinômio em vez de , e observando que ainda tem grau menor ou igual a n , e que seu coeficiente de grau n é d n a n .
A série é convergente para k ≥ 2. Esta fórmula é usada na análise do problema do tanque alemão . Decorre que está provado por indução em M .
Identidades com provas combinatórias
Muitas identidades envolvendo coeficientes binomiais podem ser provadas por meios combinatórios . Por exemplo, para inteiros não negativos , a identidade
(que se reduz a ( 6 ) quando q = 1) pode receber uma prova de dupla contagem , 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 existem maneiras de escolher um conjunto de q elementos para marcar e escolher qual dos elementos restantes de [ n ] também pertence ao subconjunto.
Na identidade de Pascal
ambos os lados contam o número de subconjuntos de k- elementos de [ n ]: os dois termos do lado direito agrupam-nos naqueles que contêm o elemento n e nos que não.
A identidade ( 8 ) também possui uma prova combinatória. A identidade lê
Suponha que você tenha quadrados vazios organizados em uma linha e deseja marcar (selecionar) n deles. Existem maneiras de fazer isso. Por outro lado, você pode selecionar seus n quadrados selecionando k quadrados entre os primeiros n e quadrados dos n quadrados restantes ; qualquer k de 0 a n funcionará. Isto dá
Agora aplique ( 1 ) para obter o resultado.
Se alguém denota por F ( i ) a sequência de números de Fibonacci , indexados de forma que F (0) = F (1) = 1 , então a identidade
Soma da linha de coeficientes
O número de k - combinações para todos os k , , é a soma de a
n -ésima linha (contagem de 0) dos coeficiente binomial. Essas combinações são enumeradas por 1 dígito do conjunto de números de base 2 , contando de 0 a , onde cada posição de dígito é um item do conjunto de n .A identidade de Dixon
ou, mais geralmente,
onde a , b e c são inteiros não negativos.
Identidades contínuas
Certos integrais trigonométricos têm valores expressáveis em termos de coeficientes binomiais: Para qualquer
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 por termo.
Congruências
Se n for primo, então
para cada k com De maneira mais geral, isso permanece verdadeiro se
n for qualquer número ek for tal que todos os números entre 1 e k sejam coprimes para n .Na verdade, nós temos
Gerando funções
Funções geradoras ordinárias
Para um n fixo , a função geradora comum da sequência é
Para um k fixo , a função geradora comum da sequência é
A função geradora bivariada dos coeficientes binomiais é
Uma função geradora bivariada simétrica dos coeficientes binomiais é
que é o mesmo que a função geradora anterior após a substituição .
Função de geração exponencial
Uma função de
geração bivariada exponencial simétrica dos coeficientes binomiais é:Propriedades de divisibilidade
Em 1852, Kummer provou que se m e n são inteiros não negativos ep é um número primo, então a maior potência de p dividindo é
p c , onde c é o número de carregamentos quando m e n são adicionados na base p . Equivalentemente, o expoente de um p primo em é igual ao número de inteiros não negativos j tal que a parte fracionária de k / p j é maior do que a parte fracionária de n / p j . Pode-se deduzir disso que é divisível por n / mdc ( n , k ). Em particular, portanto, segue-se que p divide para todos os inteiros positivos r e s tais que s < p r . No entanto, isso não é verdade para potências superiores de p : por exemplo, 9 não se divide .Um resultado um tanto surpreendente de David Singmaster (1974) é que qualquer número inteiro divide quase todos os coeficientes binomiais. Mais precisamente, fixe um inteiro d e deixe f ( N ) denotar o número de coeficientes binomiais com
n < N tal que d divide . EntãoComo o número de coeficientes binomiais com
n < N é N ( N + 1) / 2, isso implica que a densidade dos coeficientes binomiais divisíveis por d vai para 1.Os coeficientes binomiais têm propriedades de divisibilidade relacionadas aos múltiplos menos comuns de inteiros consecutivos. Por exemplo:
divide .
é um múltiplo de .
Outro fato: um inteiro n ≥ 2 é primo se e somente se todos os coeficientes binomiais intermediários
são divisíveis por n .
Prova: quando p é primo, p se divide
- para todos 0 < k < p
porque é um número natural
ep divide o numerador, mas não o denominador. Quando n é composto, seja p o menor fator primo de n e seja k = n / p . Então 0 < p < n ecaso contrário, o numerador k ( n - 1) ( n - 2) × ... × ( n - p + 1) deve ser divisível por n = k × p , isso só pode ser o caso quando ( n - 1) ( n - 2) × ... × ( n - p + 1) é divisível por p . Mas n é divisível por p , então p não divide n - 1, n - 2, ..., n - p + 1 e porque p é primo, sabemos que p não divide ( n - 1) ( n - 2) × ... × ( n - p + 1) e, portanto, o numerador não pode ser divisível por n .
Limites e fórmulas assintóticas
Os seguintes limites são válidos para todos os valores de
n e k, de modo que 1 ≤ k ≤ n :- .
A primeira desigualdade decorre do fato de que
e cada um desses termos neste produto é . Um argumento semelhante pode ser feito para mostrar a segunda desigualdade. A desigualdade estrita final é equivalente a , isso é claro, pois o RHS é um termo da série exponencial .
A partir das propriedades de divisibilidade, podemos inferir que
- ,
onde ambas as igualdades podem ser alcançadas.
Os limites a seguir são úteis na teoria da informação:
onde está a
função de entropia binária . Pode ser ainda mais apertado paraAmbos n e k grande
A aproximação de Stirling produz a seguinte aproximação, válida quando ambos tendem ao infinito:
Como as formas de desigualdade da fórmula de Stirling também limitam os fatoriais, pequenas variações na aproximação assintótica acima fornecem limites exatos. Em particular, quando é suficientemente grande, um tem
- e
e, de forma mais geral, para m ≥ 2 e n ≥ 1,
Se n é grande e k é linear em n , existem várias estimativas assintóticas precisas para o coeficiente binomial . Por exemplo, se então
onde d = n - 2 k .
n muito maior que k
Se n for grande e k for o ( n ) (ou seja, se
k / n → 0 ), entãoSoma dos coeficientes binomiais
Um limite superior simples e aproximado para a soma dos coeficientes binomiais pode ser obtido usando o teorema binomial :
Limites mais precisos são dados por
válido para todos os inteiros com .
Coeficientes binomiais generalizados
A fórmula de produto infinito para a função Gama também fornece uma expressão para coeficientes binomiais
que produz as fórmulas assintóticas
como .
Este comportamento assintótico está contido na aproximação
também. (Aqui está o número
harmônico k- ésimo e é a constante de Euler-Mascheroni .)Além disso, a fórmula assintótica
mantenha true, quando e para algum número complexo .
Generalizações
Generalização para multinomiais
Os coeficientes binomiais podem ser generalizados para coeficientes multinomiais definidos como sendo o número:
Onde
Enquanto os coeficientes binomiais representam os coeficientes de ( x + y ) n , os coeficientes multinomiais representam os coeficientes do polinômio
O caso r = 2 dá coeficientes binomiais:
A interpretação combinatória de coeficientes multinomiais é a distribuição de n elementos distinguíveis em r contêineres (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:
e simetria:
onde é uma
permutação de (1, 2, ..., r ).Série Taylor
Usando números de Stirling do primeiro tipo, a expansão da
série em torno de qualquer ponto escolhido arbitrariamente éCoeficiente binomial com n = 1/2
A definição dos coeficientes binomiais pode ser estendida para o caso em que é real e é inteiro.
Em particular, a seguinte identidade é válida para qualquer número inteiro não negativo :
Isso aparece ao expandir em uma série de potências usando a série binomial de Newton:
Produtos de coeficientes binomiais
Pode-se expressar o produto de dois coeficientes binomiais como uma combinação linear de coeficientes binomiais:
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 rótulos 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 . (Ou seja, separar os rótulos em três partes para aplicar à parte colada, à parte descolada do primeiro objeto e à parte descolada do segundo objeto.) A este respeito, os coeficientes binomiais são para séries geradoras exponenciais do que fatoriais decrescentes são para séries de geração comuns.
O produto de todas as coeficiente binomial na n -ésima linha do triângulo de Pascal é dada pela fórmula:
Decomposição parcial da fração
A decomposição da
fração parcial do recíproco é dada porSé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:
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 é
onde a identidade
é aplicado.
Coeficiente binomial multiset (crescente)
Os coeficientes binomiais contam subconjuntos de tamanho prescrito de um determinado conjunto. Um problema combinatório relacionado é contar multiconjuntos de tamanho prescrito com elementos retirados de um determinado conjunto, isto é, contar o número de maneiras de selecionar um certo número de elementos de um determinado conjunto com a possibilidade de selecionar o mesmo elemento repetidamente. Os números resultantes são chamados de coeficientes multiset ; o número de maneiras de "escolher entre vários" (ou seja, escolher com substituição) k itens de um conjunto de n elementos é denotado .
Para evitar ambigüidade e confusão com a denotação principal de
n neste artigo,seja f = n = r + ( k - 1) e r = f - ( k - 1).
Coeficientes multiset podem ser expressos em termos de coeficientes binomiais pela regra
Uma possível caracterização alternativa desta identidade é a seguinte: Podemos definir o fatorial de queda como
- ,
e o fatorial ascendente correspondente como
- ;
então, por exemplo,
- .
Em seguida, os coeficientes binomiais podem ser escritos como
- ,
enquanto o coeficiente multiset correspondente é definido substituindo o fatorial decrescente pelo crescente:
- .
Generalização para números inteiros negativos n
Para qualquer n ,
Em particular, os coeficientes binomiais avaliados em inteiros negativos n são dados por coeficientes multiset com sinais. No caso especial , isso se reduz a
Por exemplo, se n = −4 e k = 7, então r = 4 e f = 10:
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
Esta definição herda as seguintes propriedades adicionais de :
além disso,
A função resultante foi pouco estudada, aparentemente sendo representada graficamente pela primeira vez ( Fowler 1996 ). Notavelmente, muitas identidades binomiais falham: mas para
n positivo (tão negativo). O comportamento é bastante complexa, e marcadamente diferente em diferentes octantes (isto é, no que diz respeito ao x e y eixos e a linha ), com o comportamento de negativos x com singularidades em valores inteiros negativos e um tabuleiro de regiões positivas e negativas:- no octante , é uma forma suavemente interpolada do binômio usual, com uma crista ("crista de Pascal").
- no octante e no quadrante a função é próxima de zero.
- no quadrante, a função é alternadamente muito grande positiva e negativa nos paralelogramos com vértices
- no octante, o comportamento é novamente alternadamente muito grande, positivo e negativo, mas em uma grade quadrada.
- no octante é próximo de zero, exceto perto das singularidades.
Generalização para a série q
O coeficiente binomial tem uma generalização q-analógica conhecida como coeficiente binomial gaussiano .
Generalização para cardeais infinitos
A definição do coeficiente binomial pode ser generalizada para cardinais infinitos , definindo:
onde A é algum conjunto com cardinalidade . Pode-se mostrar que o coeficiente binomial generalizado é bem definido, no sentido de que qualquer conjunto que escolhermos para representar o número cardinal , permanecerá o mesmo. Para cardinais finitos, esta definição coincide com a definição padrão do coeficiente binomial.
Assumindo o Axioma da Escolha , pode-se mostrar isso para qualquer cardeal infinito .
Em linguagens de programação
A notação é conveniente para escrita à mão, mas inconveniente para
máquinas de escrever e terminais de computador . Muitas linguagens de programação não oferecem um padrão sub-rotina para calcular o coeficiente binomial, mas, por exemplo, tanto a linguagem de programação APL eo (relacionados) linguagem de programação J uso o ponto de exclamação: . O coeficiente binomial é implementado no SciPy como scipy.special.comb .k ! n
Implementações ingênuas da fórmula fatorial, como o seguinte snippet em Python :
from math import factorial
def binomial_coefficient(n: int, k: int) -> int:
return factorial(n) // (factorial(k) * factorial(n - 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:
def binomial_coefficient(n: int, k: int) -> int:
if k < 0 or k > n:
return 0
if k == 0 or k == n:
return 1
k = min(k, n - k) # Take advantage of symmetry
c = 1
for i in range(k):
c = c * (n - i) / (i + 1)
return c
(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:
def binomial_coefficient(n: int, k: int) -> int:
if k < 0 or k > n:
return 0
if k > n - k: # Take advantage of symmetry
k = n - k
if k == 0 or n <= 1:
return 1
return binomial_coefficient(n - 1, k) + binomial_coefficient(n - 1, k - 1)
O exemplo mencionado acima também pode ser escrito em estilo funcional. O seguinte exemplo de esquema usa a definição recursiva
A aritmética racional pode ser facilmente evitada usando divisão inteira
A implementação a seguir usa todas essas idéias
(define (binomial n k)
;; Helper function to compute C(n,k) via forward recursion
(define (binomial-iter n k i prev)
(if (>= i k)
prev
(binomial-iter n k (+ i 1) (/ (* (- n i) prev) (+ i 1)))))
;; Use symmetry property C(n,k)=C(n, n-k)
(if (< k (- n k))
(binomial-iter n k 0 1)
(binomial-iter n (- n k) 0 1)))
Ao calcular em uma linguagem com números inteiros de comprimento fixo, a multiplicação por pode estourar mesmo quando o resultado caberia. O estouro pode ser evitado dividindo primeiro e fixando o resultado usando o restante:
Implementação na linguagem C:
#include <limits.h>
unsigned long binomial(unsigned long n, unsigned long k) {
unsigned long c = 1, i;
if (k > n-k) // take advantage of symmetry
k = n-k;
for (i = 1; i <= k; i++, n--) {
if (c/i >= ULONG_MAX/n) // return 0 on potential overflow
return 0;
c = c / i * n + c % i * n / i; // split c * n / i into (c / i * i + c % i) * n / i
}
return c;
}
Outra maneira de calcular o coeficiente binomial ao usar números grandes é reconhecer que
onde denota o
logaritmo natural da função gama em . É uma função especial que é facilmente calculada e é padrão em algumas linguagens de programação, como usar log_gamma no Maxima , LogGamma no Mathematica , gammaln no MATLAB e módulo SciPy do Python , lngamma em PARI / GP ou lgamma em C, R e Julia . O erro de arredondamento pode fazer com que o valor retornado não seja um número inteiro.Veja também
- Transformação binomial
- Número Delannoy
- Número Euleriano
- Função hipergeométrica
- Lista de tópicos fatoriais e binomiais
- Representação Macaulay de um inteiro
- Número Motzkin
- Multiplicidades de entradas no triângulo de Pascal
- Número de Narayana
- Teorema da Estrela de David
- A curiosa identidade da Sun
- Tabela da série newtoniana
- Expansão trinomial
Notas
Referências
- Ash, Robert B. (1990) [1965]. Teoria da Informação . Dover Publications, Inc. ISBN 0-486-66521-6.
- Benjamin, Arthur T .; Quinn, Jennifer J. (2003). Provas que realmente contam: a arte da prova combinatória . Dolciani Mathematical Expositions. 27 . Mathematical Association of America . ISBN 978-0-88385-333-7.
- Bryant, Victor (1993). Aspectos da combinatória . Cambridge University Press. ISBN 0-521-41974-3.
- Flum, Jörg; Grohe, Martin (2006). Teoria da Complexidade Parametrizada . Springer. ISBN 978-3-540-29952-3.
- Fowler, David (janeiro de 1996). "A função de coeficiente binomial". The American Mathematical Monthly . Mathematical Association of America. 103 (1): 1–17. doi : 10.2307 / 2975209 . JSTOR 2975209 .
- Goetgheluck, P. (1987). "Coeficientes binomiais de computação". American Mathematical Monthly . 94 (4): 360–365. doi : 10.2307 / 2323099 . JSTOR 2323099 .
- Graham, Ronald L .; Knuth, Donald E .; Patashnik, Oren (1994). Concrete Mathematics (segunda ed.). Addison-Wesley. pp. 153 –256. ISBN 0-201-55802-5.
- Gradshteyn, IS; Ryzhik, IM (2014). Tabela de integrais, séries e produtos (8ª ed.). Academic Press. ISBN 978-0-12-384933-5.
- Grinshpan, AZ (2010), "Weighted inequalities and negative binomials", Advances in Applied Mathematics , 45 (4): 564-606, doi : 10.1016 / j.aam.2010.04.004
- Higham, Nicholas J. (1998). Manual de redação para as ciências matemáticas . SIAM . p. 25 . ISBN 0-89871-420-6.
- Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms(Terceira edição). Addison-Wesley. pp. 52–74. ISBN 0-201-89683-4.
- Singmaster, David (1974). "Notas sobre coeficientes binomiais. III. Qualquer número inteiro divide quase todos os coeficientes binomiais". Journal of the London Mathematical Society . 8 (3): 555–560. doi : 10.1112 / jlms / s2-8.3.555 .
- Shilov, GE (1977). Álgebra linear . Publicações de Dover. ISBN 978-0-486-63518-7.
links externos
- "Binomial coefficients" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Andrew Granville (1997). "Propriedades aritméticas dos coeficientes binomiais I. Coeficientes binomiais das potências primárias do módulo" . CMS Conf. Proc . 20 : 151–162. Arquivado do original em 23/09/2015 . Retirado 2013-09-03 .
Este artigo incorpora material dos seguintes artigos do PlanetMath , licenciados sob a licença Creative Commons Atribuição / Compartilhamento pela mesma Licença : Coeficiente Binomial , Limites superior e inferior do coeficiente binomial , Coeficiente binomial é um número inteiro , Coeficientes binomiais generalizados .