Números binomiais

Vamos começar com uma definição usual.

Definição 1.1: Definimos os números binomiais pela fórmula

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

Outras possíveis definições são a recursiva e a algébrica, que enunciaremos como proposições.

Proposição 1.2: Os números binomiais satisfazem

$$\binom{n+1}{m+1} = \binom{n}{m} + \binom{n}{m+1}, \qquad n \ge 0$$

e

$$\binom{0}{m} = \begin{cases} 1,& \text{se $m=0$ },\\ 0,& \text{caso contrário.} \end{cases}$$

Além disso, a única função de ${\mathbb{N} }\times {\mathbb{Z} }$ que satisfaz esta recorrência com estas condições iniciais é $\binom{n}{m}$.

Dem: Indução.          $\blacksquare$

Proposição 1.3: (Binômio de Newton) Para todo $n \in {\mathbb{N} }$ vale a identidade de polinômios

$$(X+Y)^n = \sum_{0 \le m \le n} \binom{n}{m} X^m Y^{n-m}.$$

Dem: Indução.          $\blacksquare$

Observemos ainda que

$$\binom{x}{m} = \frac{x(x-1) \cdots (x-(m-1))}{m!}$$

é um polinômio de grau m na variável x. Definimos assim mais geralmente

$$\binom{x}{m} = \begin{cases} \frac{x(x-1) \cdots (x-(m-1))}{m!},& \text{se } m \ge 0,\\ 0,& \text{se } m < 0. \end{cases}$$

para qualquer $x \in {\mathbb{C} }$ (ou mesmo em outro corpo qualquer) e $m \in {\mathbb{Z} }$. A identidade

$$\binom{x+1}{m+1} = \binom{x}{m} + \binom{x}{m+1}$$

ainda vale para quaisquer valores de x e m.

Existem inúmeras interpretações combinatórias para números binomiais: a mais conhecida é que $\binom{n}{m}$ é o número de subconjuntos de m elementos de um conjunto de n elementos dado (por exemplo, $\{1, 2, \ldots, n\}$). Outra interpretação interessante é como o número de caminhos de comprimento n (o valor mínimo) ligando (0,m) e (n-m,0)andando sempre por retas verticais ou horizontais inteiras, conforme ilustrado abaixo. Uma demonstração bijetiva deste fato consiste em tomar para cada caminho o conjunto das posições ao longo do caminho dos segmentos verticais: este é um subconjunto de m elementos de $\{1, 2, \ldots, n\}$. O caminho na figura abaixo corresponde ao subconjunto $\{2,3,5,10,11,14\}$.

Existem muitíssimas identidades interessantes envolvendo números binomiais. Enunciaremos agora algumas que serão usadas mais adiante.

Proposição 1.4: Para quaisquer $n \in {\mathbb{N} }$, $m \in {\mathbb{Z} }$ e $x \in {\mathbb{C} }$ temos

$$\sum_{0 \le j \le n} (-1)^j \binom{n}{j} \binom{x-j}{m} = \binom{x-n}{m-n}.$$

Dem: Por indução em n, sendo trivial o caso n = 0. O caso n = 1 é a identidade recursiva da Proposição 1.2 (apenas mudando o nome das variáveis):

$$\binom{x}{m} - \binom{x-1}{m} = \binom{x-1}{m-1}.$$

Suponha a identidade demonstrada para n; para n+1 temos
$$\begin{align}&\phantom{=} \sum_{0 \le j \le n+1} (-1)^j \binom{n+1}{j} \binom{x-... ...om{x-n}{m-n} - \binom{x-n-1}{m-n} = \binom{x-(n+1)}{m-(n+1)}, \notag \end{align}$$
o que demonstra a identidade para n+1 e conclui a demonstração.          $\blacksquare$

Corolário 1.5: Seja $n \in {\mathbb{Z} }$ um inteiro positivo e $P \in C[x]$, $P(x) = \sum a_i x^i$, um polinômio de grau menor do que n. Então

$$\sum_{j \in {\mathbb{Z} }} (-1)^j \binom{n}{j} P(x-j) = \sum_{0 \le j \le n} (-1)^j \binom{n}{j} P(x-j) = 0.$$

Observe que apenas um número finito de termos do primeiro somatório são diferentes de 0: exatamente aqueles valores considerados no segundo somatório.

Dem: Podemos escrever

$$P(x) = \sum_{0 \le i < n} b_i \binom{x}{i}$$

donde, pela proposição anterior,
$$\begin{align}\sum_{0 \le j \le n} (-1)^j \binom{n}{j} P(x-j) &= \sum_{0 \le i < ... ...ht) \notag\\ &= \sum_{0 \le i < n} b_i \binom{x-n}{i-n} = 0. \notag \end{align}$$
         $\blacksquare$

Proposição 1.6: Para quaisquer naturais a, b, c temos

$$\det \begin{pmatrix} \binom{b+c}{b} & \binom{b+c}{b+1} & \cdo... ... \le i < a, 0 \le j < b, 0 \le k < c} \frac{i+j+k+2}{i+j+k+1}.$$

Observe que a matriz é quadrada de ordem a. Observe também que do lado direito os papéis de a, b e csão intercambiáveis, o que não ocorre do lado esquerdo. Por outro lado, o lado esquerdo é claramente inteiro; o leitor pode tentar mostrar diretamente que o lado direito é inteiro.

Na demonstração da proposição usaremos a equação

$$\binom{n}{m} = (-1)^m \binom{-n+m-1}{m},$$

de fácil demonstração.

Dem: Os casos a = 0 e a = 1 são triviais. Definamos

$$M(a,b,c) = \begin{pmatrix} \binom{b+c}{b} & \binom{b+c}{b+1} ... ...binom{b+c}{b-a+2} & \cdots & \binom{b+c}{b} \\ \end{pmatrix};$$

por indução basta mostrar que

$$\frac{\det M(a,b,c)}{\det M(a-1,b,c)} = \frac{\binom{a+b+c-1}{b}}{\binom{a+b-1}{b}}$$

pois

$$\frac{\binom{a+b+c-1}{b}}{\binom{a+b-1}{b}} = \prod_{0 \le j < b, 0 \le k < c} \frac{a+j+k+1}{a+j+k}.$$

Defina

$$P(x) = \binom{c-1+x}{c-1} \binom{-a+x}{b};$$

$P \in {\mathbb{C} }[x]$ é um polinômio de grau b+c-1. Observe que as raízes de P são $-c+1, -c+2, \ldots, -2, -1$ e $a, a+1, \ldots, a+b-2, a+b-1$; observe também que

$$P(-c) = \binom{-1}{c-1} \binom{-a-c}{b} = (-1)^{b+c-1} \binom{a+b+c-1}{b}.$$

Seja $v \in {\mathbb{C} }^a$ um vetor cuja i-ésima coordenada é v_i = (-1)ⁱ P(a-1-i)(i varia de 0 a a-1):

$$v = \left({ \binom{a+c-2}{c-1} \binom{-1}{b}, - \binom{a+c-3}... ...}, \ldots, (-1)^{a-1} \binom{c-1}{c-1} \binom{-a}{b} }\right).$$

Temos

$$v_{a-1} = (-1)^{a+b-1} \binom{a+b-1}{b}$$

pois $\binom{-a}{b} = (-1)^b \binom{a+b-1}{b}$. Observe que as coordenadas de v são todas não nulas. Vamos calcular o produto w = M(a,b,c) v.

Calculemos a i-ésima coordenada w_i de w. Temos, por uma simples mudança de índices,
$$\begin{align}w_i &= \sum_{0 \le j < a} (-1)^j \binom{b+c}{b-i+j} P(a-1-j) \notag... ...} \sum{b-i \le k < a+b-i} (-1)^k \binom{b+c}{k} P(a+b-i-k-1). \notag \end{align}$$
Mas pelo corolário temos

$$\sum_{k \in {\mathbb{Z} }} (-1)^k \binom{b+c}{k} P(a+b-i-k-1) = 0$$

donde

w_i = (-1)^b-i+1 (S^-_i + S⁺_i)

onde
$$\begin{align}S^-_i &= \sum_{0 \le k < b-i} (-1)^k \binom{b+c}{k} P(a+b-i-k-1) \n... ...\sum_{a+b-i \le k \le b+c} (-1)^k \binom{b+c}{k} P(a+b-i-k-1) \notag \end{align}$$
Mas se $0 \le k < b-i$ temos $a \le a+b-i-k-1 < a+b$, assim P se anula em todos os termos do somatório que define S^-_ie temos S^-_i = 0 para qualquer valor de i. Por outro lado, se $i \le a-2$ e $a+b-i \le k \le b+c$ temos $-c+1 \le a+b-i-k-1 < 0$ e P se anula agora em todos os termos do somatório que define S⁺_i. Assim temos w_i = 0 para i < a-1. Se i = a-1, o único termo do somatório S⁺_i que não se anula é para k = b+c e temos

$$S^+_{a-1} = (-1)^{b+c} \binom{b+c}{b+c} P(-c) = -\binom{a+b+c-1}{b}$$

e

$$w_{a-1} = (-1)^{a+b-1} \binom{a+b+c-1}{b}.$$

Temos assim $w = (-1)^{a+b-1} \binom{a+b+c-1}{b} e_{a-1}$.

Podemos escrever v = (M(a,b,c))^-1 wdonde

$$(M(a,b,c))^{-1} e_{a-1} = (-1)^{a+b-1} {\binom{a+b+c-1}{b}}^{-1} v.$$

Assim, a entrada (a-1,a-1) de (M(a,b,c))^-1 é $\binom{a+b-1}{b} / \binom{a+b+c-1}{b}$. Mas por Cramer esta entrada é $\det M(a-1,b,c) / \det M(a,b,c)$, o que conclui a demonstração.          $\blacksquare$