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 \geq k \geq 0$ e é escrito $(\binom{n}{k})$ ou ⁠ $C (n, k)$ ⁠. É o coeficiente do termo $x k$ na expansão polinomial da potência binomial $(1 + x) n$ ; este coeficiente pode ser calculado pela fórmula multiplicativa

$(\binom{n}{k}) = \frac{n \times (n - 1) \times \dots \times (n - k + 1)}{k \times (k - 1) \times \dots \times 1},$

que, usando a notação fatorial, pode ser expressa de forma compacta como

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

Por exemplo, a quarta potência de $1 + x$ é $\begin{matrix} (1 + x)^{4} & = (\binom{4}{0}) x^{0} + (\binom{4}{1}) x^{1} + (\binom{4}{2}) x^{2} + (\binom{4}{3}) x^{3} + (\binom{4}{4}) x^{4} \\ = 1 + 4 x + 6 x^{2} + 4 x^{3} + x^{4}, \end{matrix}$ e o coeficiente binomial $(\binom{4}{2}) = \frac{4 \times 3}{2 \times 1} = \frac{4!}{2! 2!} = 6$ é o coeficiente do termo $x 2$ .

Dispondo os números $(\binom{n}{0}), (\binom{n}{1}), \dots, (\binom{n}{n})$ em linhas sucessivas para $n = 0, 1, 2, ...$ obtém-se um arranjo triangular chamado triângulo de Pascal, que satisfaz a relação de recorrência $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) .$

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

Os coeficientes binomiais podem ser estendidos para aceitar famílias mais gerais de entradas. Quando $n$ é um inteiro não negativo e $k$ é um inteiro tal que $k < 0$ ou $k > n$ , é comum definir ⁠ $(\binom{n}{k}) = 0$ ⁠. Se $k$ é um inteiro não negativo e $z$ é qualquer número complexo, a primeira fórmula multiplicativa acima pode ser usada para definir ⁠ $(\binom{z}{k})$ ⁠. Muitas das propriedades dos coeficientes binomiais continuam válidas nesses contextos mais gerais.

História e notação

Andreas von Ettingshausen introduziu a notação $(\binom{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)$ , $n C k$ , $n C k$ , $C k n$ , $C n k$ e $C n, 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.

Definição e interpretações

n \ k	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 (considerando 0) $n$ e $k$ , o coeficiente binomial $(\binom{n}{k})$ 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 \leq n$ ) na fórmula binomial

|

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n - k}

|∗

(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 $X k$ , e o coeficiente desse monômio no resultado será o número de tais subconjuntos. Isso mostra em particular que $(\binom{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 ⁠ $(\binom{n}{k})$ ⁠, enquanto o número de maneiras de escrever $k = a_{1} + a_{2} + \dots + a_{n}$ onde cada $a i$ é um inteiro não negativo é dado por ⁠ $(\binom{n + k - 1}{n - 1})$ ⁠. A maioria dessas interpretações pode ser mostrada como equivalente à contagem de $k$ -combinações.

Calculando o valor dos coeficientes binomiais

Existem vários métodos para calcular o valor de $(\binom{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 $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ para todos os inteiros $n, k$ tais que ⁠ $1 \leq k < n$ ⁠, com valores de contorno $(\binom{n}{0}) = (\binom{n}{n}) = 1$ para todos os inteiros $n \geq 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 X^k em $(1 + X) n -1 (1 + X)$ . Como não há $X n +1$ ou $X -1$ em $(1 + X) n$ , pode-se estender a definição além dos limites acima para incluir $(\binom{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 $(\binom{n}{k}) = \frac{n^{\underline{k}}}{k!} = \frac{n (n - 1) (n - 2) \dots (n - (k - 1))}{k (k - 1) (k - 2) \dots 1} = \prod_{i = 1}^{k} \frac{n + 1 - i}{i},$ onde o numerador da primeira fração, ⁠ $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} \cdot (n - k + 1) / k$ ⁠, onde ⁠ $C_{n, 0} = 1$ ⁠. É prontamente derivada avaliando $C_{n, k} / C_{n, k - 1}$ e pode ser intuitivamente compreendida como começando no coeficiente mais à esquerda da ⁠ $n$ ⁠-ésima linha do triângulo de Pascal, cujo valor é sempre ⁠ $1$ ⁠, e calculando recursivamente o próximo coeficiente à sua direita até que o ⁠ $k$ ⁠-ésimo seja alcançado.

Devido à simetria dos coeficientes binomiais em relação a $k$ e $n - k$ , o cálculo do produto acima, bem como a relação recursiva, pode ser otimizado definindo seu limite superior como o menor entre $k$ e $n - k$ .

Fórmula fatorial

Finalmente, há a forma compacta, frequentemente usada em provas e derivações, que faz uso repetido da familiar função fatorial: $(\binom{n}{k}) = \frac{n!}{k! (n - k)!} 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)

|

(\binom{n}{k}) = (\binom{n}{n - k}) para 0 \leq k \leq n,

|1

o que leva a uma rotina computacional multiplicativa mais eficiente. Usando a notação de fatorial decrescente, $(\binom{n}{k}) = {\begin{matrix} n^{\underline{k}} / k! & se k \leq \frac{n}{2} \\ n^{\underline{n - k}} / (n - k)! & se k > \frac{n}{2} \end{matrix} .$

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: $(\binom{α}{k}) = \frac{α^{\underline{k}}}{k!} = \frac{α (α - 1) (α - 2) \dots (α - k + 1)}{k (k - 1) (k - 2) \dots 1} para k \in ℕ e α 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 $(\binom{α}{k})$ de coeficientes binomiais:

|

(1 + X)^{α} = \sum_{k = 0}^{\infty} (\binom{α}{k}) X^{k} .

|2

Esta fórmula é válida para todos os números complexos α e X com |X| < 1. Também pode ser interpretada como uma identidade de séries de potências formais em X, onde 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 esperam para a exponenciação são válidas, notadamente $(1 + X)^{α} (1 + X)^{β} = (1 + X)^{α + β} e ((1 + X)^{α})^{β} = (1 + X)^{α β} .$

Se α é um inteiro não negativo n, então todos os termos com $k > n$ são zero, e a série infinita se torna 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

|

(\binom{n}{k}) + (\binom{n}{k + 1}) = (\binom{n + 1}{k + 1}),

|3

que pode ser usada para provar por indução matemática que $(\binom{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:

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

A linha número $n$ contém os números $(\binom{n}{k})$ para $k = 0, \dots, 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} = \underline{1} x^{5} + \underline{5} x^{4} y + \underline{10} x^{3} y^{2} + \underline{10} x^{2} y^{3} + \underline{5} x y^{4} + \underline{1} y^{5} .$

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:

Há $(\binom{n}{k})$ maneiras de escolher k elementos de um conjunto de n elementos. Veja Combinação.
Há $(\binom{n + k - 1}{k})$ maneiras de escolher k elementos de um conjunto de n elementos se repetições forem permitidas. Veja Multiconjunto.
Há $(\binom{n + k}{k})$ strings contendo k uns e n zeros.
Há $(\binom{n + 1}{k})$ strings consistindo de k uns e n zeros tais que não haja dois uns adjacentes.
Os números de Catalan são ⁠ $\frac{1}{n + 1} (\binom{2 n}{n})$ ⁠.
A distribuição binomial em estatística é ⁠ $(\binom{n}{k}) p^{k} (1 - p)^{n - k}$ ⁠.

Coeficientes binomiais como polinômios

Para qualquer inteiro não negativo k, a expressão $(\binom{t}{k})$ pode ser escrita como um polinômio com denominador $k!$ : $(\binom{t}{k}) = \frac{t^{\underline{k}}}{k!} = \frac{t (t - 1) (t - 2) \dots (t - k + 1)}{k (k - 1) (k - 2) \dots 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 $(\binom{t}{k})$ pode ser caracterizado como o único polinômio de grau k $p (t)$ satisfazendo $p (0) = p (1) = \dots = p (k - 1) = 0$ e $p (k) = 1$ .

Seus coeficientes são expressáveis em termos de números de Stirling do primeiro tipo: $(\binom{t}{k}) = \sum_{i = 0}^{k} s (k, i) \frac{t^{i}}{k!} .$ A derivada de $(\binom{t}{k})$ pode ser calculada por diferenciação logarítmica: $\frac{d}{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$ a ⁠ $t - 1$ ⁠, mas usando identidades abaixo podemos calcular a derivada como: $\frac{d}{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 $\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 a_k é a k-ésima diferença da sequência p(0), p(1), ..., p(k). Explicitamente,

|

a_{k} = \sum_{i = 0}^{k} (- 1)^{k - i} (\binom{k}{i}) p (i) .

|4

Polinômios com valores inteiros

Cada polinômio $(\binom{t}{k})$ tem valores inteiros: tem um valor inteiro em todas as entradas inteiras ⁠ $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 $3 t (3 t + 1) / 2$ pode ser reescrito como $9 (\binom{t}{2}) + 6 (\binom{t}{1}) + 0 (\binom{t}{0}) .$

Identidades envolvendo coeficientes binomiais

A fórmula fatorial facilita relacionar coeficientes binomiais próximos. Por exemplo, se k é um inteiro positivo e n é 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 - 2 k}{n} (\binom{n}{k}) .$

Também podemos obter $(\binom{n - 1}{k}) = \frac{n - k}{n} (\binom{n}{k}) .$

Além disso, o seguinte pode ser útil: $(\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: $(\binom{n}{k}) = \frac{n - k + 1}{k} (\binom{n}{k - 1}) .$

Resumindo, temos $(\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 - 2 k} ((\binom{n - 1}{k}) - (\binom{n - 1}{k - 1})) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) .$

Somas dos coeficientes binomiais

A fórmula

|

\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}

|∗∗

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}$ escolhas. Os lados esquerdo e direito são duas maneiras de contar a mesma coleção de subconjuntos, portanto são iguais.

As fórmulas

|

\sum_{k = 0}^{n} k (\binom{n}{k}) = n 2^{n - 1}

|6

e $\sum_{k = 0}^{n} k^{2} (\binom{n}{k}) = (n + n^{2}) 2^{n - 2}$ seguem do teorema binomial após derivar em relação a $x$ (duas vezes para a última) e depois substituir $x = y = 1$ .

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

|

\sum_{j = 0}^{k} (\binom{m}{j}) (\binom{n - m}{k - j}) = (\binom{n}{k})

|7

e pode ser encontrada examinando o coeficiente de $x^{k}$ 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) se torna (como visto no triângulo de Pascal à direita)

\begin{matrix} 1 \\ 1 1 \\ 1 2 1 \\ 1 3 3 1 \\ 1 4 6 4 1 \\ 1 5 10 10 5 1 \\ 1 6 15 20 15 6 1 \\ 1 7 21 35 35 21 7 1 \end{matrix}

Triângulo de Pascal, linhas 0 a 7. A equação 8 para

m = 3

é ilustrada nas linhas 3 e 6 como ⁠

1^{2} + 3^{2} + 3^{2} + 1^{2} = 20

⁠.

|

\sum_{j = 0}^{m} {(\binom{m}{j})}^{2} = (\binom{2 m}{m}),

|8

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

Outra forma da identidade de Chu–Vandermonde, que se aplica para quaisquer inteiros j, k e n satisfazendo $0 \leq j \leq k \leq n$ , é

|

\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) dá a identidade do taco de hóquei $\sum_{m = k}^{n} (\binom{m}{k}) = (\binom{n + 1}{k + 1})$ e sua relativa $\sum_{r = 0}^{m} (\binom{n + r}{r}) = (\binom{n + m + 1}{m}) .$

Seja F(n) o n-ésimo número de Fibonacci. Então $\sum_{k = 0}^{⌊ n / 2 ⌋} (\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 abaixo.

Multisseções de somas

Para inteiros s e t tais que ⁠ $0 \leq t < s$ ⁠, a multisseção de séries dá a seguinte identidade para a soma dos coeficientes binomiais: $(\binom{n}{t}) + (\binom{n}{t + s}) + (\binom{n}{t + 2 s}) + \dots = \frac{1}{s} \sum_{j = 0}^{s - 1} {(2 \cos \frac{π j}{s})}^{n} \cos \frac{π (n - 2 t) j}{s} .$

Para $s$ pequeno, essas séries têm formas particularmente agradáveis; por exemplo, $(\binom{n}{0}) + (\binom{n}{3}) + (\binom{n}{6}) + \dots = \frac{1}{3} (2^{n} + 2 \cos \frac{n π}{3})$ $(\binom{n}{1}) + (\binom{n}{4}) + (\binom{n}{7}) + \dots = \frac{1}{3} (2^{n} + 2 \cos \frac{(n - 2) π}{3})$ $(\binom{n}{2}) + (\binom{n}{5}) + (\binom{n}{8}) + \dots = \frac{1}{3} (2^{n} + 2 \cos \frac{(n - 4) π}{3})$ $(\binom{n}{0}) + (\binom{n}{4}) + (\binom{n}{8}) + \dots = \frac{1}{2} (2^{n - 1} + 2^{\frac{n}{2}} \cos \frac{n π}{4})$ $(\binom{n}{1}) + (\binom{n}{5}) + (\binom{n}{9}) + \dots = \frac{1}{2} (2^{n - 1} + 2^{\frac{n}{2}} \sin \frac{n π}{4})$ $(\binom{n}{2}) + (\binom{n}{6}) + (\binom{n}{10}) + \dots = \frac{1}{2} (2^{n - 1} - 2^{\frac{n}{2}} \cos \frac{n π}{4})$ $(\binom{n}{3}) + (\binom{n}{7}) + (\binom{n}{11}) + \dots = \frac{1}{2} (2^{n - 1} - 2^{\frac{n}{2}} \sin \frac{n π}{4})$

Somas parciais

Embora não haja uma fórmula fechada para somas parciais $\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$ , $\sum_{j = 0}^{k} (- 1)^{j} (\binom{n}{j}) = (- 1)^{k} (\binom{n - 1}{k}),$ com o caso especial

$\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 de que para qualquer polinômio P(x) de grau menor que n, $\sum_{j = 0}^{n} (- 1)^{j} (\binom{n}{j}) P (j) = 0.$ Derivando (2) k vezes e definindo x = −1 obtém-se isso para ⁠ $P (x) = x (x - 1) \dots (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,

|

\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), $\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. Isso segue imediatamente aplicando (10) ao polinômio ⁠ $Q (x) := P (m + d x)$ ⁠ em vez de ⁠ $P (x)$ ⁠, e observando que ⁠ $Q (x)$ ⁠ ainda tem grau menor ou igual a n, e que seu coeficiente de grau n é dⁿa_n.

A série $\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. Ela segue de $\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 é provada 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 ⁠ $n \geq q$ ⁠, a identidade $\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á $(\binom{n}{q})$ maneiras de escolher um conjunto de q elementos para marcar, e $2^{n - q}$ para escolher quais dos elementos restantes de [n] também pertencem ao subconjunto.

Na identidade de Pascal $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}),$ ambos os lados contam o número de subconjuntos de k elementos de [n]: os dois termos do lado direito os agrupam naqueles que contêm o elemento n e naqueles que não o contêm.

A identidade (8) também tem uma prova combinatória. A identidade diz $\sum_{k = 0}^{n} {(\binom{n}{k})}^{2} = (\binom{2 n}{n}) .$

Suponha que você tenha $2 n$ quadrados vazios dispostos em uma linha e queira marcar (selecionar) n deles. Há $(\binom{2 n}{n})$ maneiras de fazer isso. Por outro lado, você pode selecionar seus n quadrados escolhendo k quadrados entre os primeiros n e $n - k$ quadrados dos n quadrados restantes; qualquer k de 0 a n funcionará. Isso dá $\sum_{k = 0}^{n} (\binom{n}{k}) (\binom{n}{n - k}) = (\binom{2 n}{n}) .$ Agora aplique (1) para obter o resultado.

Se denotarmos por $F (i)$ a sequência dos números de Fibonacci, indexada de modo que $F (0) = F (1) = 1$ , então a identidade $\sum_{k = 0}^{⌊ \frac{n}{2} ⌋} (\binom{n - k}{k}) = F (n)$ tem a seguinte prova combinatória. Pode-se mostrar por indução que $F (n)$ conta o número de maneiras que uma faixa de quadrados $n \times 1$ pode ser coberta por ladrilhos $2 \times 1$ e $1 \times 1$ . Por outro lado, se tal ladrilhamento usa exatamente $k$ dos ladrilhos $2 \times 1$ , então ele usa $n - 2 k$ dos ladrilhos $1 \times 1$ , e portanto usa $n - k$ ladrilhos no total. Há $(\binom{n - k}{k})$ maneiras de ordenar esses ladrilhos, e somando esse coeficiente sobre todos os valores possíveis de $k$ obtém-se a identidade.

Soma dos coeficientes de uma linha

O número de k-combinações para todo k, ⁠ $\sum_{0 \leq k \leq n} (\binom{n}{k}) = 2^{n}$ ⁠, é a soma da $n$ -ésima linha (contando a partir de 0) dos coeficientes binomiais. Essas combinações são enumeradas pelos dígitos 1 do conjunto de números na base 2 contando 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} {(\binom{2 a}{k + a})}^{3} = \frac{(3 a)!}{(a!)^{3}}$ ou, mais geralmente, $\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 \in ℕ$ ⁠, $\int_{- π}^{π} \cos ((2 m - n) x) \cos^{n} (x) d x = \frac{π}{2^{n - 1}} (\binom{n}{m})$ $\int_{- π}^{π} \sin ((2 m - n) x) \sin^{n} (x) d x = {\begin{matrix} (- 1)^{m + (n + 1) / 2} \frac{π}{2^{n - 1}} (\binom{n}{m}), & n ímpar \\ 0, & caso contrário \end{matrix}$ $\int_{- π}^{π} \cos ((2 m - n) x) \sin^{n} (x) d x = {\begin{matrix} (- 1)^{m + (n / 2)} \frac{π}{2^{n - 1}} (\binom{n}{m}), & n par \\ 0, & caso contrário \end{matrix}$

Estas podem ser provadas 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 é primo, então $(\binom{n - 1}{k}) \equiv (- 1)^{k} mod n$ para todo k com ⁠ $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 $(\binom{n - 1}{k}) = \frac{(n - 1) (n - 2) \dots (n - k)}{1 \cdot 2 \dots k} = \prod_{i = 1}^{k} \frac{n - i}{i} \equiv \prod_{i = 1}^{k} \frac{- i}{i} = (- 1)^{k} mod n .$

Funções geradoras

Funções geradoras ordinárias

Para um $n$ fixo, a função geradora ordinária da sequência $(\binom{n}{0}), (\binom{n}{1}), (\binom{n}{2}), \dots$ é $\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 ⁠ $(\binom{0}{k}), (\binom{1}{k}), (\binom{2}{k}), \dots$ ⁠, é $\sum_{n = 0}^{\infty} (\binom{n}{k}) y^{n} = \frac{y^{k}}{(1 - y)^{k + 1}} .$

A função geradora bivariada dos coeficientes binomiais é $\sum_{n = 0}^{\infty} \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n} = \frac{1}{1 - y - x y} .$

Uma função geradora bivariada simétrica dos coeficientes binomiais é $\sum_{n = 0}^{\infty} \sum_{k = 0}^{\infty} (\binom{n + k}{k}) x^{k} y^{n} = \frac{1}{1 - x - y} .$ que é a mesma função geradora anterior após a substituição ⁠ $x \to x y$ ⁠.

Função geradora exponencial

Uma função geradora exponencial bivariada simétrica dos coeficientes binomiais é: $\sum_{n = 0}^{\infty} \sum_{k = 0}^{\infty} (\binom{n + k}{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 não negativos e p é um número primo, então a maior potência de p que divide $(\binom{m + n}{m})$ é igual a p^c, 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 $(\binom{n}{k})$ é igual ao número de inteiros não negativos j tais que a parte fracionária de k/p^j é maior que a parte fracionária de n/p^j. (Por exemplo, $(\binom{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 $(\binom{n}{k})$ é divisível por n/mdc(n,k). Em particular, portanto, segue que p divide $(\binom{p^{r}}{s})$ 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 divide ⁠ $(\binom{9}{6})$ ⁠.

Qualquer inteiro divide quase todos os coeficientes binomiais. Mais precisamente, fixe um inteiro d e seja f(N) o número de coeficientes binomiais $(\binom{n}{k})$ com $n < N$ tais que d divide ⁠ $(\binom{n}{k})$ ⁠. Então $lim_{N \to \infty} \frac{f (N)}{N (N + 1) / 2} = 1.$ Como o número de coeficientes binomiais $(\binom{n}{k})$ com n < N é N(N + 1) / 2, isso implica que a densidade dos coeficientes binomiais divisíveis por d tende a 1.

Os coeficientes binomiais têm propriedades de divisibilidade relacionadas a mínimos múltiplos comuns de inteiros consecutivos. Por exemplo: $(\binom{n + k}{k})$ divide ⁠ $\frac{mmc (n, n + 1, \dots, n + k)}{n}$ ⁠. $(\binom{n + k}{k})$ é um múltiplo de ⁠ $\frac{mmc (n, n + 1, \dots, n + k)}{n \cdot mmc ((\binom{k}{0}), (\binom{k}{1}), \dots, (\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}), \dots, (\binom{n}{n - 1})$ são divisíveis por n.

Prova: Quando p é primo, p divide $(\binom{p}{k}) = \frac{p \cdot (p - 1) \dots (p - k + 1)}{k \cdot (k - 1) \dots 1}$ para todo $0 < k < p$ porque $(\binom{p}{k})$ é um número natural e p 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$ e $(\binom{n}{p}) = \frac{n (n - 1) (n - 2) \dots (n - p + 1)}{p!} = \frac{k (n - 1) (n - 2) \dots (n - p + 1)}{(p - 1)!} \equiv̸ 0 (\mod n)$ caso contrário, o numerador $k (n - 1)(n - 2)\dots(n - p + 1)$ teria que ser divisível por $n = k \times p$ , o que só pode acontecer 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, como 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 $(\binom{n}{k})$ valem para todos os valores de n e k tais que $1 \leq k \leq n$ : $\frac{n^{k}}{k^{k}} \leq (\binom{n}{k}) \leq \frac{n^{k}}{k!} < {(\frac{n \cdot e}{k})}^{k} .$ A primeira desigualdade segue do fato de que $(\binom{n}{k}) = \frac{n}{k} \cdot \frac{n - 1}{k - 1} \dots \frac{n - (k - 1)}{1}$ e cada um desses $k$ termos neste produto é ⁠ $\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!$ ⁠, o que é claro, pois o lado direito é um termo da série exponencial ⁠ $e^{k} = \sum_{j = 0}^{\infty} k^{j} / j!$ ⁠.

A partir das propriedades de divisibilidade, podemos inferir que $\frac{mmc (n - k, \dots, n)}{(n - k) \cdot mmc ((\binom{k}{0}), \dots, (\binom{k}{k}))} \leq (\binom{n}{k}) \leq \frac{mmc (n - k, \dots, n)}{n - k},$ onde ambas as igualdades podem ser alcançadas.

Os seguintes limites são úteis em teoria da informação:^:353 $\frac{1}{n + 1} 2^{n H (k / n)} \leq (\binom{n}{k}) \leq 2^{n H (k / n)}$ onde $H (p) = - p \log_{2} (p) - (1 - p) \log_{2} (1 - p)$ é a função entropia binária. Pode ser ainda mais apertado para $\sqrt{\frac{n}{8 k (n - k)}} 2^{n H (k / n)} \leq (\binom{n}{k}) \leq \sqrt{\frac{n}{2 π k (n - k)}} 2^{n H (k / n)}$ para todo ⁠ $1 \leq k \leq n - 1$ ⁠.^:309

Tanto n quanto k grandes

A aproximação de Stirling fornece a seguinte aproximação, válida quando $n - k, k$ ambos tendem ao infinito: $(\binom{n}{k}) \sim \sqrt{\frac{n}{2 π k (n - k)}} \cdot \frac{n^{n}}{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$ é suficientemente grande, tem-se $(\binom{2 n}{n}) \sim \frac{2^{2 n}}{\sqrt{n π}}$ e ⁠ $\sqrt{n} (\binom{2 n}{n}) \geq 2^{2 n - 1}$ ⁠. Mais geralmente, para $m \geq 2$ e $n \geq 1$ (novamente, aplicando a fórmula de Stirling aos fatoriais no coeficiente binomial), $\sqrt{n} (\binom{m n}{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 ⁠ $(\binom{n}{k})$ ⁠. Por exemplo, se $| n / 2 - k | = o (n^{2 / 3})$ então $(\binom{n}{k}) \sim (\binom{n}{\frac{n}{2}}) e^{- d^{2} / (2 n)} \sim \frac{2^{n}}{\sqrt{\frac{1}{2} n π}} e^{- d^{2} / (2 n)}$ onde d = n − 2k.

$n$ muito maior que $k$

Se $n$ é grande e $k$ é $o (n)$ (isto é, se $k / n \to 0$ ), então $(\binom{n}{k}) \sim {(\frac{n e}{k})}^{k} \cdot (2 π k)^{- 1 / 2} \cdot \exp (- \frac{k^{2}}{2 n} (1 + o (1)))$ 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 $(\binom{m}{i})$ e depois o teorema binomial: $\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 $\frac{1}{\sqrt{8 n ε (1 - ε)}} \cdot 2^{H (ε) \cdot n} \leq \sum_{i = 0}^{k} (\binom{n}{i}) \leq 2^{H (ε) \cdot n},$ válidos para todos os inteiros $n > k \geq 1$ com ⁠ $ε ≐ 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} (\binom{z}{k}) = (\binom{- z + k - 1}{k}) = \frac{1}{Γ (- z)} \frac{1}{(k + 1)^{z + 1}} \prod_{j = k + 1} \frac{{(1 + \frac{1}{j})}^{- z - 1}}{1 - \frac{z + 1}{j}}$ que fornece as fórmulas assintóticas $(\binom{z}{k}) \approx \frac{(- 1)^{k}}{Γ (- z) k^{z + 1}} e (\binom{z + k}{k}) = \frac{k^{z}}{Γ (z + 1)} (1 + \frac{z (z + 1)}{2 k} + 𝒪 (k^{- 2}))$ quando ⁠ $k \to \infty$ ⁠.

Este comportamento assintótico está contido na aproximação $(\binom{z + k}{k}) \approx \frac{e^{z (H_{k} - γ)}}{Γ (z + 1)}$ também. (Aqui $H_{k}$ é o k-ésimo número harmônico e $γ$ é a constante de Euler–Mascheroni.)

Além disso, a fórmula assintótica $\frac{(\binom{z + k}{j})}{(\binom{k}{j})} \to {(1 - \frac{j}{k})}^{- z} e \frac{(\binom{j}{j - k})}{(\binom{j - z}{j - k})} \to {(\frac{j}{k})}^{z}$ são verdadeiras sempre que $k \to \infty$ e $j / k \to x$ para algum número complexo ⁠ $x$ ⁠.

Generalizações

Generalização para multinomiais

Os coeficientes binomiais podem ser generalizados para coeficientes multinomiais definidos como o número: $(\binom{n}{k_{1}, k_{2}, \dots, k_{r}}) = \frac{n!}{k_{1}! k_{2}! \dots k_{r}!}$ onde $\sum_{i = 1}^{r} k_{i} = n .$

Enquanto os coeficientes binomiais representam os coeficientes de $(x + y) n$ , os coeficientes multinomiais representam os coeficientes do polinômio $(x_{1} + x_{2} + \dots + x_{r})^{n} .$ O caso r = 2 dá os coeficientes binomiais: $(\binom{n}{k_{1}, k_{2}}) = (\binom{n}{k_{1}, n - k_{1}}) = (\binom{n}{k_{1}}) = (\binom{n}{k_{2}}) .$

A interpretação combinatória dos coeficientes multinomiais é a distribuição de n elementos distinguíveis em r recipientes (distinguíveis), cada um contendo exatamente k_i elementos, onde i é o índice do recipiente.

Os coeficientes multinomiais têm muitas propriedades semelhantes às dos coeficientes binomiais, por exemplo, a relação de recorrência: $(\binom{n}{k_{1}, k_{2}, \dots, k_{r}}) = (\binom{n - 1}{k_{1} - 1, k_{2}, \dots, k_{r}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, \dots, k_{r}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, \dots, k_{r} - 1})$ e simetria: $(\binom{n}{k_{1}, k_{2}, \dots, k_{r}}) = (\binom{n}{k_{σ_{1}}, k_{σ_{2}}, \dots, k_{σ_{r}}})$ onde $(σ_{i})$ é uma permutação de (1, 2, ..., r).

Série de Taylor

Usando números de Stirling do primeiro tipo, a expansão em série em torno de qualquer ponto escolhido arbitrariamente $z_{0}$ é $\begin{matrix} (\binom{z}{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} (\binom{z_{0}}{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} (\binom{j}{i}) \frac{s_{k, j}}{k!} . \end{matrix}$

Coeficiente binomial com $n = 1/2$

A definição dos coeficientes binomiais pode ser estendida para o caso em que $n$ é real e $k$ é inteiro.

Em particular, a seguinte identidade vale para qualquer inteiro não negativo ⁠ $k$ ⁠: $(\binom{1 / 2}{k}) = (\binom{2 k}{k}) \frac{(- 1)^{k + 1}}{2^{2 k} (2 k - 1)} .$

Isso aparece ao expandir $\sqrt{1 + x}$ em uma série de potências usando a série binomial de Newton: $\sqrt{1 + x} = \sum_{k \geq 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: $(\binom{z}{m}) (\binom{z}{n}) = \sum_{k = 0}^{min (m, n)} (\binom{m + n - k}{k, m - k, n - k}) (\binom{z}{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$ rótulos a um par de objetos combinatórios rotulados — de peso m e n, respectivamente — que tiveram seus primeiros k rótulos identificados, ou colados juntos para obter um novo objeto combinatório rotulado de peso $m + n - k$ . (Ou seja, para separar os rótulos em três partes para aplicar à parte colada, à parte não colada do primeiro objeto e à parte não colada do segundo objeto.) A esse respeito, os coeficientes binomiais estão para séries geradoras exponenciais assim como os fatoriais decrescentes estão para séries geradoras ordinárias.

O produto de todos os coeficientes binomiais na n-ésima linha do triângulo de Pascal é dado pela fórmula: $\prod_{k = 0}^{n} (\binom{n}{k}) = \prod_{k = 1}^{n} k^{2 k - n - 1} .$

Decomposição em frações parciais

A decomposição em frações parciais do recíproco é dada por $\frac{1}{(\binom{z}{n})} = \sum_{i = 0}^{n - 1} (- 1)^{n - 1 - i} (\binom{n}{i}) \frac{n - i}{z - i}, \frac{1}{(\binom{z + n}{n})} = \sum_{i = 1}^{n} (- 1)^{i - 1} (\binom{n}{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)^{α} = \sum_{n = 0}^{\infty} (\binom{α}{n}) z^{n} = 1 + (\binom{α}{1}) z + (\binom{α}{2}) z^{2} + \dots .$

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)^{α + 1}} = \sum_{n = 0}^{\infty} (\binom{n + α}{n}) z^{n}$ onde a identidade $(\binom{n}{k}) = (- 1)^{k} (\binom{k - n - 1}{k})$ é aplicada.

Coeficiente binomial multiconjunto (ascendente)

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, ou seja, 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 multiconjunto; o número de maneiras de "multiescolher" (isto é, escolher com reposição) k itens de um conjunto de n elementos é denotado ⁠ $((\binom{n}{k}))$ ⁠.

Para evitar ambiguidade e confusão com a denotação principal de n neste artigo,
seja $f = n = r + (k - 1)$ e $r = f - (k - 1)$ .

Os coeficientes multiconjunto podem ser expressos em termos de coeficientes binomiais pela regra $(\binom{f}{k}) = ((\binom{r}{k})) = (\binom{r + k - 1}{k}) .$ Uma possível caracterização alternativa desta identidade é a seguinte: Podemos definir o fatorial decrescente como $(f)_{k} = f^{\underline{k}} = (f - k + 1) \dots (f - 3) \cdot (f - 2) \cdot (f - 1) \cdot f,$ e o fatorial ascendente correspondente como $r^{(k)} = r^{\overline{k}} = r \cdot (r + 1) \cdot (r + 2) \cdot (r + 3) \dots (r + k - 1);$ assim, por exemplo, $17 \cdot 18 \cdot 19 \cdot 20 \cdot 21 = (21)_{5} = 2 1^{\underline{5}} = 1 7^{\overline{5}} = 1 7^{(5)} .$ Então os coeficientes binomiais podem ser escritos como $(\binom{f}{k}) = \frac{(f)_{k}}{k!} = \frac{(f - k + 1) \dots (f - 2) \cdot (f - 1) \cdot f}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \dots k},$ enquanto o coeficiente multiconjunto correspondente é definido substituindo o fatorial decrescente pelo ascendente: $((\binom{r}{k})) = \frac{r^{(k)}}{k!} = \frac{r \cdot (r + 1) \cdot (r + 2) \dots (r + k - 1)}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \dots k} .$

Generalização para inteiros negativos n

Para qualquer n, $\begin{matrix} (\binom{- n}{k}) & = \frac{- n \cdot - (n + 1) \dots - (n + k - 2) \cdot - (n + k - 1)}{k!} \\ = (- 1)^{k} \frac{n \cdot (n + 1) \cdot (n + 2) \dots (n + k - 1)}{k!} \\ = (- 1)^{k} (\binom{n + k - 1}{k}) \\ = (- 1)^{k} ((\binom{n}{k})) . \end{matrix}$ Em particular, coeficientes binomiais avaliados em inteiros negativos n são dados por coeficientes multiconjunto com sinal. No caso especial ⁠ $n = - 1$ ⁠, isso se reduz a ⁠ $(- 1)^{k} = (\binom{- 1}{k}) = ((\binom{- k}{k}))$ ⁠.

Por exemplo, se n = −4 e k = 7, então r = 4 e f = 10: $\begin{matrix} (\binom{- 4}{7}) & = \frac{- 10 \cdot - 9 \cdot - 8 \cdot - 7 \cdot - 6 \cdot - 5 \cdot - 4}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7} \\ = (- 1)^{7} \frac{4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7} \\ = ((\binom{- 7}{7})) ((\binom{4}{7})) = (\binom{- 1}{7}) (\binom{10}{7}) . \end{matrix}$

Dois argumentos reais ou complexos

O coeficiente binomial é generalizado para dois argumentos reais ou complexos usando a função gama ou função beta através de $(\binom{x}{y}) = \frac{Γ (x + 1)}{Γ (y + 1) Γ (x - y + 1)} = \frac{1}{(x + 1) B (y + 1, x - y + 1)} .$ Esta definição herda estas seguintes propriedades adicionais de ⁠ $Γ$ ⁠: $(\binom{x}{y}) = \frac{\sin (y π)}{\sin (x π)} (\binom{- y - 1}{- x - 1}) = \frac{\sin ((x - y) π)}{\sin (x π)} (\binom{y - x - 1}{y});$ além disso, $(\binom{x}{y}) \cdot (\binom{y}{x}) = \frac{\sin ((x - y) π)}{(x - y) π} .$

A função resultante tem sido pouco estudada, aparentemente sendo representada graficamente pela primeira vez em (Fowler 1996). Notavelmente, muitas identidades binomiais falham: $(\binom{n}{m}) = (\binom{n}{n - m})$ mas $(\binom{- n}{m}) \neq (\binom{- n}{- n - m})$ para n positivo (então $- n$ negativo). O comportamento é bastante complexo e marcadamente diferente em vários octantes (isto é, em relação aos eixos x e y e à linha ⁠ $y = x$ ⁠), com o comportamento para x negativo tendo singularidades em valores inteiros negativos e um tabuleiro de xadrez de regiões positivas e negativas:

no octante $0 \leq y \leq x$ é uma forma interpolada suavemente do binomial usual, com uma crista ("crista de Pascal").
no octante $0 \leq x \leq y$ e no quadrante $x \geq 0, y \leq 0$ a função está próxima de zero.
no quadrante $x \leq 0, y \geq 0$ a função é alternadamente muito grande positiva e negativa nos paralelogramos com vértices $(- n, m + 1), (- n, m), (- n - 1, m - 1), (- n - 1, m)$
no octante $0 > x > y$ o comportamento é novamente alternadamente muito grande positivo e negativo, mas em uma grade quadrada.
no octante $- 1 > y > x + 1$ está próximo de zero, exceto perto das singularidades.

Generalização para q-séries

O coeficiente binomial tem uma generalização q-análoga conhecida como coeficiente binomial gaussiano. Esses coeficientes são polinômios em uma indeterminada (tradicionalmente denotada q) e têm aplicações a muitos problemas enumerativos em combinatória, como contar o número de subespaços lineares de um espaço vetorial sobre um corpo finito e contar o número de subconjuntos de {1, 2, ..., n} com certas simetrias (uma instância do fenômeno de peneiramento cíclico).

Generalização para cardinais infinitos

A definição do coeficiente binomial pode ser generalizada para cardinais infinitos definindo: $(\binom{α}{β}) = | {B \subseteq A : | B | = β} |$ onde $A$ é algum conjunto com cardinalidade ⁠ $α$ ⁠. Pode-se mostrar que o coeficiente binomial generalizado é bem definido, no sentido de que não importa qual conjunto escolhemos para representar o número cardinal ⁠ $α$ ⁠, $(\binom{α}{β})$ 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 que $(\binom{α}{α}) = 2^{α}$ para qualquer cardinal infinito ⁠ $α$ ⁠.

Ver também

Referências

↑ Higham (1998)
↑ Lilavati Seção 6, Capítulo 4 (veja Knuth (1997)).
↑ Uspensky 1937, p. 18
↑ Veja (Graham, Knuth & Patashnik 1994), que também define $(\binom{n}{k}) = 0$ para ⁠ $k < 0$ ⁠. Generalizações alternativas, como para dois argumentos reais ou complexos usando a função gama atribuem valores não nulos a $(\binom{n}{k})$ para ⁠ $k < 0$ ⁠, mas isso faz com que a maioria das identidades dos coeficientes binomiais falhe e, portanto, não é amplamente utilizada pela maioria das definições. Uma dessas escolhas de valores não nulos leva ao esteticamente agradável "moinho de vento de Pascal" em Hilton, Holton e Pedersen, Mathematical reflections: in a room with many mirrors, Springer, 1997, mas faz até mesmo a identidade de Pascal falhar (na origem).
↑ Quando $α = n$ é um inteiro não negativo, $(\binom{n}{k}) = 0$ para $k > n$ porque o ⁠ $(k = n + 1)$ ⁠-ésimo fator do numerador é ⁠ $n - (n + 1) + 1 = 0$ ⁠. Assim, o ⁠ $k$ ⁠-ésimo termo é um produto nulo para todo ⁠ $k \geq n + 1$ ⁠.
↑ Muir, Thomas (1902). «Note on Selected Combinations». Proceedings of the Royal Society of Edinburgh
↑ Isso pode ser visto como um análogo discreto do teorema de Taylor. Está intimamente relacionado ao polinômio de Newton. Somas alternadas desta forma podem ser expressas como a integral de Nörlund–Rice.
↑ Gradshteyn & Ryzhik (2014, pp. 3–4).
↑ Boardman, Michael (2004). «The Egg-Drop Numbers». Mathematics Magazine. 77 (5): 368–372. JSTOR 3219201. MR 1573776. doi:10.2307/3219201. é bem conhecido que não há forma fechada (isto é, fórmula direta) para a soma parcial de coeficientes binomiais .
↑ veja indução desenvolvida na eq (7) p. 1389 em Aupetit, Michael (2009). «Nearly homogeneous multi-partitioning with a deterministic generator». Neurocomputing. 72 (7–9): 1379–1389. ISSN 0925-2312. doi:10.1016/j.neucom.2008.12.024 .
↑ Ruiz, Sebastian (1996). «An Algebraic Identity Leading to Wilson's Theorem». The Mathematical Gazette. 80 (489): 579–582. JSTOR 3618534. arXiv:math/0406086. doi:10.2307/3618534
↑ Benjamin & Quinn 2003, pp. 4−5
↑ David Singmaster (1974)
1 2 Farhi, Bakir (2007). «Nontrivial lower bounds for the least common multiple of some finite sequence of integers». Journal of Number Theory. 125 (2): 393–411. arXiv:0803.0290. doi:10.1016/j.jnt.2006.10.017
↑ Thomas M. Cover; Joy A. Thomas (18 de julho de 2006). Elements of Information Theory. Hoboken, Nova Jersey: Wiley. ISBN 0-471-24195-4
↑ F. J. MacWilliams; N. J. A. Sloane (1981). The Theory of Error-Correcting Codes. 16 3ª ed. [S.l.]: North-Holland. ISBN 0-444-85009-0
↑ Spencer, Joel; Florescu, Laura (2014). Asymptopia. Col: Student mathematical library. 71. Joel Spencer. [S.l.]: AMS. p. 66. ISBN 978-1-4704-0904-3. OCLC 865574788
↑ Spencer, Joel; Florescu, Laura (2014). Asymptopia. Col: Student mathematical library. 71. Joel Spencer. [S.l.]: AMS. p. 59. ISBN 978-1-4704-0904-3. OCLC 865574788
↑ veja, por exemplo, Ash (1990, p. 121) ou Flum & Grohe (2006, p. 427).
↑ Munarini, Emanuele (2011). «Riordan matrices and sums of harmonic numbers» (PDF). Applicable Analysis and Discrete Mathematics. 5 (2): 176–200. MR 2867317. doi:10.2298/AADM110609014M .

Bibliografia

Ash, Robert B. (1990). Information Theory. 1965. [S.l.]: Dover Publications, Inc. ISBN 0-486-66521-6
Benjamin, Arthur T.; Quinn, Jennifer J. (2003). Proofs that Really Count: The Art of Combinatorial Proof. Col: Dolciani Mathematical Expositions. 27. [S.l.]: Mathematical Association of America. ISBN 978-0-88385-333-7
Bryant, Victor (1993). Aspects of combinatorics. [S.l.]: Cambridge University Press. ISBN 0-521-41974-3
Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. [S.l.]: Springer. ISBN 978-3-540-29952-3. Consultado em 28 de agosto de 2017. Arquivado do original em 18 de novembro de 2007
Fowler, David (janeiro de 1996). «The Binomial Coefficient Function». Mathematical Association of America. The American Mathematical Monthly. 103 (1): 1–17. JSTOR 2975209. doi:10.2307/2975209
Goetgheluck, P. (1987). «Computing Binomial Coefficients». American Mathematical Monthly. 94 (4): 360–365. JSTOR 2323099. doi:10.2307/2323099
Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (fevereiro de 1994). Concrete Mathematics: A Foundation for Computer Science 2.ª ed. Reading, Massachusetts, EUA: Addison-Wesley Professional. pp. 154–155. ISBN 0-201-55802-5. MR 1397498
Gradshteyn, I. S.; Ryzhik, I. M. (2014). Table of Integrals, Series, and Products. Gradshteyn and Ryzhik 8ª ed. [S.l.]: Academic Press. ISBN 978-0-12-384933-5
Grinshpan, A. Z. (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). Handbook of writing for the mathematical sciences. [S.l.]: SIAM. p. 25. ISBN 0-89871-420-6
Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms Terceira ed. [S.l.]: Addison-Wesley. pp. 52–74. ISBN 0-201-89683-4
Singmaster, David (1974). «Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients». Journal of the London Mathematical Society. 8 (3): 555–560. doi:10.1112/jlms/s2-8.3.555
Shilov, G. E. (1977). Linear algebra. [S.l.]: Dover Publications. ISBN 978-0-486-63518-7
Uspensky, James (1937). Introduction to Mathematical Probability. [S.l.]: McGraw-Hill

Ligações externas

Hazewinkel, Michiel, ed. (2001), «Binomial coefficients», Enciclopédia de Matemática, ISBN 978-1-55608-010-4 (em inglês), Springer
Andrew Granville (1997). «Arithmetic Properties of Binomial Coefficients I. Binomial coefficients modulo prime powers». CMS Conf. Proc. 20: 151–162. Consultado em 3 de setembro de 2013. Arquivado do original em 23 de setembro de 2015

[1] Higham (1998)

[2] Lilavati Seção 6, Capítulo 4 (veja Knuth (1997)).

[3] Uspensky 1937, p. 18

[4] Veja (Graham, Knuth & Patashnik 1994), que também define $(\binom{n}{k}) = 0$ para ⁠ $k < 0$ ⁠. Generalizações alternativas, como para dois argumentos reais ou complexos usando a função gama atribuem valores não nulos a $(\binom{n}{k})$ para ⁠ $k < 0$ ⁠, mas isso faz com que a maioria das identidades dos coeficientes binomiais falhe e, portanto, não é amplamente utilizada pela maioria das definições. Uma dessas escolhas de valores não nulos leva ao esteticamente agradável "moinho de vento de Pascal" em Hilton, Holton e Pedersen, Mathematical reflections: in a room with many mirrors, Springer, 1997, mas faz até mesmo a identidade de Pascal falhar (na origem).

[5] Quando $α = n$ é um inteiro não negativo, $(\binom{n}{k}) = 0$ para $k > n$ porque o ⁠ $(k = n + 1)$ ⁠-ésimo fator do numerador é ⁠ $n - (n + 1) + 1 = 0$ ⁠. Assim, o ⁠ $k$ ⁠-ésimo termo é um produto nulo para todo ⁠ $k \geq n + 1$ ⁠.

[6] Muir, Thomas (1902). «Note on Selected Combinations». Proceedings of the Royal Society of Edinburgh

[7] Isso pode ser visto como um análogo discreto do teorema de Taylor. Está intimamente relacionado ao polinômio de Newton. Somas alternadas desta forma podem ser expressas como a integral de Nörlund–Rice.

[8] Gradshteyn & Ryzhik (2014, pp. 3–4).

[9] Boardman, Michael (2004). «The Egg-Drop Numbers». Mathematics Magazine. 77 (5): 368–372. JSTOR 3219201. MR 1573776. doi:10.2307/3219201. é bem conhecido que não há forma fechada (isto é, fórmula direta) para a soma parcial de coeficientes binomiais .

[10] veja indução desenvolvida na eq (7) p. 1389 em Aupetit, Michael (2009). «Nearly homogeneous multi-partitioning with a deterministic generator». Neurocomputing. 72 (7–9): 1379–1389. ISSN 0925-2312. doi:10.1016/j.neucom.2008.12.024 .

[11] Ruiz, Sebastian (1996). «An Algebraic Identity Leading to Wilson's Theorem». The Mathematical Gazette. 80 (489): 579–582. JSTOR 3618534. arXiv:math/0406086. doi:10.2307/3618534

[12] Benjamin & Quinn 2003, pp. 4−5

[13] David Singmaster (1974)

[Farhi2007-14] 1 2 Farhi, Bakir (2007). «Nontrivial lower bounds for the least common multiple of some finite sequence of integers». Journal of Number Theory. 125 (2): 393–411. arXiv:0803.0290. doi:10.1016/j.jnt.2006.10.017

[cover2006-15] Thomas M. Cover; Joy A. Thomas (18 de julho de 2006). Elements of Information Theory. Hoboken, Nova Jersey: Wiley. ISBN 0-471-24195-4

[macwilliams1977-16] F. J. MacWilliams; N. J. A. Sloane (1981). The Theory of Error-Correcting Codes. 16 3ª ed. [S.l.]: North-Holland. ISBN 0-444-85009-0

[17] Spencer, Joel; Florescu, Laura (2014). Asymptopia. Col: Student mathematical library. 71. Joel Spencer. [S.l.]: AMS. p. 66. ISBN 978-1-4704-0904-3. OCLC 865574788

[18] Spencer, Joel; Florescu, Laura (2014). Asymptopia. Col: Student mathematical library. 71. Joel Spencer. [S.l.]: AMS. p. 59. ISBN 978-1-4704-0904-3. OCLC 865574788

[19] veja, por exemplo, Ash (1990, p. 121) ou Flum & Grohe (2006, p. 427).

[20] Munarini, Emanuele (2011). «Riordan matrices and sums of harmonic numbers» (PDF). Applicable Analysis and Discrete Mathematics. 5 (2): 176–200. MR 2867317. doi:10.2298/AADM110609014M .

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