Números binomiais e q-contagem

Na seção anterior supomos que o leitor conhecia a função fatorial. Vamos começar esta seção definindo (n!)_q.

Definição 1.7: Seja n um natural; definimos

$$(n!)_q = \frac{q^n - 1}{q-1} \cdot \frac{q^{n-1} - 1}{q-1} \cdots \frac{q^2 - 1}{q - 1} \cdot \frac{q - 1}{q - 1}.$$

É claro que podemos também definir recursivamente (0!)_q = 1,

$$(n!)_q = \frac{q^n - 1}{q - 1} ((n-1)!)_q = (q^{n-1} + q^{n-2} + \cdots + q + 1) ((n-1)!)_q.$$

Vejamos agora uma interpretação combinatória para estes polinômios.

Lembramos que n! é o número de permutações de $\{1, 2, \ldots, n\}$. Definimos o número de inversões $i(\pi)$ de uma permutação $\pi$como sendo o número de pares (i,j) com $1 \le i < j \le n$tais que $\pi(i) > \pi(j)$.

Proposição 1.8: Seja n um natural; temos

$$\sum_{\pi \in S_n} q^{i(\pi)} = (n!)_q.$$

Ou seja, o polinômio (n!)_q serve para q-contar as permutações $\pi$com relação a este índice $i(\pi)$.

Dem: Usando indução, basta mostrar que

$$\sum_{\pi \in S_{n+1}} q^{i(\pi)} = (1 + q + \cdots + q^n) \sum_{\pi \in S_n} q^{i(\pi)}.$$

Pensando em permutações como listas de números, um elemento de S_n+1 é obtido a partir de um elemento de S_ninserindo o número n+1 em alguma posição. Se n+1 for inserido no final, não criamos nenhuma nova inversão; se for inserido na penúltima posição, criamos uma inversão e finalmente se for inserido no início criamos n inversões. Em geral, a partir de uma permutação com k inversões criamos n+1permutações com $k, k+1, \ldots k+n$ novas inversões, o que demonstra nossa fórmula para (n!)_q.          $\blacksquare$

Definição 1.9: Sejam n e m inteiros. Definimos

$$\binom{n}{m}_q = \begin{cases} \frac{(q^n - 1)(q^{n-1} - 1)\c... ... 0,\\ 1,&\text{se } m = 0,\\ 0,&\text{se } m < 0. \end{cases}$$

Assim $\binom{n}{m}_q \in {\mathbb{C} }(q)$ fica definido para quaisquer n, m inteiros. Observe que substituindo q por 1 recuperamos os números binomiais. Observe também que quando n é natural e $0 \le m \le n$ temos

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

Estas definições podem ser estendidas a domínios ainda maiores mas isto está fora de nossos interesses neste capítulo.

Proposição 1.10: Sejam n e m um inteiros. Temos
$$\begin{align}\binom{n+1}{m+1}_q &= q^{n-m} \binom{n}{m}_q + \binom{n}{m+1}_q \notag\\ &= \binom{n}{m}_q + q^{m+1} \binom{n}{m+1}_q.\notag \end{align}$$

Dem: Basta substituir.          $\blacksquare$

No caso clássico, vimos que $\binom{x}{m}$ é um polinômio de grau mna variável x. No nosso caso, podemos fazer uma afirmação semelhante. Para todo natural m existe um polinômio $P_m \in {\mathbb{C} }(q)[X]$de grau m na variável X tal que $\binom{n}{m}_q = P_m(q^n)$para todo inteiro n. De fato,

$$P_m(X) = \frac{(X - 1)(X/q - 1)\cdots (X/q^{m-1} - 1)}% {(q^m - 1)(q^{m-1} - 1)\cdots (q - 1)}.$$

Mais geralmente, se $Q \in {\mathbb{C} }(q)[X]$ tem grau menor ou igual a mna variável X então existem $b_0, \ldots, b_n \in {\mathbb{C} }(q)$tais que

$$Q(q^n) = \sum_{0 \le i \le m} b_i \binom{n}{i}_q$$

para todo inteiro n.

Vejamos agora interpretações combinatórias para $\binom{n}{m}_q$. Para isso voltemos à interpretação de $\binom{n}{m}$ como o número de caminhos ligando vértices em um retângulo de lados m e n-m. Para $\binom{n}{m}_q$, cada caminho contribui com q^a, onde a é a área abaixo do caminho. Para um subconjunto de m elementos de $\{1, 2, \ldots n\}$, portanto, o expoente de q é a soma dos elementos do subconjunto menos $1 + 2 + \cdots + m = m(m+1)/2$. Assim, o caminho na nossa figura na seção anterior corresponde a um termo de q²⁴. O leitor pode verificar diretamente, por exemplo, que

$$\binom{4}{2}_q = q^4 + q^3 + 2 q^2 + q + 1.$$

Um raciocínio combinatório simples nos dá a fórmula de recorrência, demonstrando que nossa interpretação é correta. Seja (provisoriamente) F(a,b) o polinômio em q definido como acima em um retângulo $a \times b$. Se a = 0 ou b = 0 temos $F(a,b) = \binom{a+b}{a}_q = 1$. Se $a, b \ge 1$, o último trecho do caminho pode ser vertical ou horizontal. Se for horizontal, retirando este último trecho temos um caminho de mesma área em um retângulo $a \times (b-1)$. Se for vertical, retirando este último trecho temos um caminho em um retângulo $(a-1) \times b$, mas a área diminuiu de b. Somando estas contribuições temos

F(a,b) = F(a,b-1) + q^b F(a-1,b)

o que é equivalente a recorrência da proposição 1.10.

Esta interpretação é útil para ajudar a ver alguns fatos básicos sobre $\binom{n}{m}_q$. Refletindo o retãngulo (e os caminhos) na diagonal x=y temos $\binom{n}{m}_q = \binom{n}{n-m}_q$. O grau de $\binom{n}{m}_q$ é m(n-m), a área total do retângulo; os coeficientes de 1 e de q^m(n-m) são ambos iguais a 1, correspondendo aos caminhos no extremo de baixo e de cima. Girando o caminho de meia volta ao redor do centro do retângulo trocamos o valor da área de i por m(n-m) - i: isto prova que os coeficientes de qⁱ e de q^{m(n-m) - i}são sempre iguais.

Existe uma outra definição combinatória importante para q-números binomiais usando álgebra linear sobre corpos finitos.

Proposição 1.11: Seja ${\mathbb{F} }_q$ o corpo finito com q elementos (onde q é uma potência de primo) e seja V um ${\mathbb{F} }_q$-espaço vetorial de dimensão n; V tem exatamente $\binom{n}{m}_q$subespaços W de dimensão m.

Observemos que aqui, pela primeira vez, q deixa de ser uma variável puramente formal e passa a assumir valores inteiros, de tal forma que $\binom{n}{m}_q$ passa também a assumir valores inteiros. Daremos duas demonstrações independentes para esta nova interpretação combinatória de $\binom{n}{m}_q$: uma por indução, usando as fórmulas de recorrência, e outra relacionando mais diretamente este problema combinatório com o primeiro (que fala de caminhos em uma grade).

Dem: A demonstração é por indução. Chamamos provisoriamente de f(n,m,q)o número de subespaços de dimensão m de $V \equiv {\mathbb{F} }_q^n$. Como só existe um subespaço de dimensão 0 e um subespaço de dimensão n, temos f(n,0,q) = f(n,n,q) = 1 para todo $n \ge 0$. Para calcular f(n+1,m+1,q), consideremos $V_1 = {\mathbb{F} }_q^n \subset V = {\mathbb{F} }_q^{n+1}$. Seja $W \subset V$ um subespaço de dimensão m+1; a dimensão de $W_1 = W \cap V_1$ pode ser m ou m+1. No primeiro caso temos f(n,m,q) possíveis W₁e cada um deles precisa ser engordado com um elemento de V - V₁para virar um W: existem qⁿ⁺¹ - qⁿ = qⁿ (q-1) elementos de V - V₁mas cada W é gerado por q^m+1 - q^m = q^m (q-1) destes elementos. Assim, temos q^n-m f(n,m,q) subespaços Wpara os quais $W \cap V_1$ tem dimensão m. Por outro lado, temos f(n,m+1,q) subespaços Wpara os quais esta dimensão é m+1; somando os dois casos temos

f(n+1,m+1,q) = q^n-m f(n,m,q) + f(n,m+1,q);

como esta recorrência é a mesma que encontramos para $\binom{n}{m}_q$e as condições iniciais também são as mesmas temos $f(n,m,q) = \binom{n}{m}_q$.

Para a segunda demonstração, lembramos que podemos descrever um subespaço W (de dimensão m) de Kⁿ (onde K é um corpo) via uma matriz $A \in K^{m \times n}$ de posto m: W é o espaço gerado pelas linhas de A. Para cada subespaço W existem muitas matrizes A correspondentes: mais precisamente, duas matrizes A₁ e A₂ definem o mesmo subespaço Wse e somente se existe uma matriz quadrada inversível B com A₁ = B A₂. A forma usual de tomar um representante de cada classe de equivalência é considerar matrizes escalonadas por linhas, i.e., para cada $A \in K^{m \times n}$ de posto mexiste uma única matriz inversível B tal que BA é escalonada por linhas. Lembramos que uma matriz escalonada por linhas é aquela que satisfaz as seguintes condições:

• o primeiro elemento não nulo de cada linha é sempre 1,
• em uma coluna onde aparece o primeiro elemento não nulo de uma linha todos os outros elementos são iguais a 0,
• se a linha i₁ está acima da linha i₂, o primeiro elemento não nulo da linha i₁aparece antes do primeiro elemento não nulo da linha i₂.

Um exemplo talvez torne mais claro o significado destas condições; a matriz

$$A = \begin{pmatrix} 0 & 1 & \ast & 0 & 0 & \ast \\ 0 & 0 & 0 & 1 & 0 & \ast \\ 0 & 0 & 0 & 0 & 1 & \ast \end{pmatrix}$$

é escalonada por linhas, onde os $\ast$'s indicam posições que podem ser preenchidas com qualquer elemento de K. Chamemos de tipo de W (ou de A) ao conjunto dos índices (j) das colunas onde aparece o primeiro elemento não nulo de alguma linha: o exemplo acima tem tipo $\{2,4,5\}$; mais precisamente, variando o valor dos $\ast$'s temos todas as matrizes A de tipo $\{2,4,5\}$. Os tipos possíveis são os subespaços de m elementos de $\{1, 2, \ldots n\}$, que equivalem aos caminhos em um retângulo de m linhas e n-m colunas: este caminho é obtido a partir da matriz jogando fora as colunas onde aparece o primeiro elemento não nulo de alguma linha (estas colunas são obrigatoriamente preenchidas pelos vetores da base canônica) e separando as posições 0 (onde devemos obrigatoriamente escrever 0) das posições $\ast$(onde temos liberdade de escrever qualquer elemento de K). O caminho correspondente à matriz A acima está indicado a seguir.          $\blacksquare$

Vejamos agora resultados análogos aos da primeira seção.

Proposição 1.12: Para quaisquer $n \in {\mathbb{N} }$, $m, \ell \in {\mathbb{Z} }$ temos

$$\sum_{0 \le j \le n} (-1)^j q^{\binom{j}{2}} \binom{n}{j}_q \binom{\ell-j}{m}_q = q^{n(\ell-m)} \binom{\ell-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.10 (apenas mudando o nome das variáveis):

$$\binom{\ell}{m}_q - \binom{\ell-1}{m}_q = q^{\ell-m} \binom{\ell-1}{m-1}_q.$$

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

Observe a total analogia entre a Proposição 1.4 e a Proposição 1.12; até a demonstração da proposição mais geral é obtida simplesmente inserindo q nos lugares apropriados.

Corolário 1.13: Seja n um inteiro positivo e $P \in {\mathbb{C} }(q)[X]$ um polinômio de grau menor do que n em X. Então

$$\sum_{j \in {\mathbb{Z} }} (-1)^j q^{\binom{j}{2}} \binom{n}{... ...n} (-1)^j q^{\binom{j}{2}} \binom{n}{j}_q P(q^{\ell - j}) = 0.$$

Dem: Análoga à do Corolário 1.5, usando a Proposição 1.12.          $\blacksquare$

Finalmente, a Proposição 1.14 abaixo é análoga à Proposição 1.6.

Proposição 1.14: Para quaisquer naturais a, b, c temos
$$\begin{align}&\det \begin{pmatrix} q^{\binom{b}{2}} \binom{b+c}{b}_q & q^{\binom... ... \le j < b, 0 \le k < c} \frac{q^{i+j+k+2}-1}{q^{i+j+k+1}-1}. \notag \end{align}$$

Novamente o lado direito é invariante por permutações de a, b, c, o que não é evidente para o lado esquerdo. Por outro lado, o lado esquerdo é claramente um polinômio em q; o leitor é convidado a tentar demonstrar diretamente que o lado direito é um polinômio em q.

Usaremos na demonstração a equação

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

que vem de escrevermos
$$\begin{align}\frac{\binom{n}{m}_q}{\binom{-n+m-1}{m}_q} &= \frac{(q^n - 1)(q^{n-... ...)(-q^{n-m+1}) = (-1)^m q^{\binom{n+1}{2} - \binom{n-m+1}{2}}. \notag \end{align}$$
Como a demonstração segue muito de perto a da Proposição 1.6 seremos um pouco mais sucintos.

Dem: Seja

$$M_q(a,b,c) = \begin{pmatrix} q^{\binom{b}{2}} \binom{b+c}{b}_... ... \cdots & q^{\binom{b}{2}} \binom{b+c}{b}_q \\ \end{pmatrix};$$

por indução, basta mostrar que

$$\frac{\det M_q(a,b,c)}{\det M_q(a-1,b,c)} = = q^{\binom{b}{2}} \frac{\binom{a+b+c-1}{b}_q}{\binom{a+b-1}{b}_q}.$$

Defina

$$P_q(\ell) = \binom{c-1+\ell}{c-1}_q \binom{-a+\ell}{b}_q;$$

observe que $P_q(\ell)$ pode ser escrito como $P(q^\ell)$onde $P \in {\mathbb{C} }(q)[X]$ tem grau b+c-1. Temos $P_q(-c+1) = P_q(-c+2) = \cdots = P_q(-2) = P_q(-1) = 0$, $P_q(a) = P_q(a+1) = \cdots = P_q(a+b-2) = P_q(a+b-1) = 0$e

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

Seja $v \in ({\mathbb{C} }(q))^a$ dado por v_i = (-1)ⁱ P_q(a-i-1):

$$v = \left({P_q(a-1), -P_q(a-2), \ldots, (-1)^{a-2} P_q(1), (-1)^{a-1} P_q(0)}\right)$$

ou seja

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

Temos

$$v_{a-1} = (-1)^{a+b-1} q^{- \binom{a+b}{2} + \binom{a}{2}} \binom{a+b-1}{b}_q.$$

Se w = M_q(a,b,c) v temos
$$\begin{align}w_i &= \sum_{0 /le j < a} (-1)^j q^{\binom{b-i+j}{2}} \binom{b+c}{... ...+b-i} (-1)^k q^{\binom{k}{2}} \binom{b+c}{k}_q P_q(a+b-i-k-1) \notag \end{align}$$
e usando o corolário acima temos que

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

onde
$$\begin{align}S^-_i &= \sum_{0 \le k < b-i} (-1)^k q^{\binom{k}{2}} \binom{b+c}{k... ...b+c} (-1)^k q^{\binom{k}{2}} \binom{b+c}{k}_q P_q(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_q 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 < a-1 e $a+b-i \le k \le b+c$ temos -c < 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
$$\begin{align}S^+_{a-1} &= (-1)^{b+c} q^{\binom{b+c}{2}} \binom{b+c}{b+c}_q P_q(-... ...{2} - \binom{a+b+c}{2} + \binom{a+c}{2}} \binom{a+b+c-1}{b}_q \notag \end{align}$$
e

$$w = (-1)^{a+b-1} q^{\binom{b+c}{2} -\binom{c}{2} - \binom{a+b+c}{2} + \binom{a+c}{2}} \binom{a+b+c-1}{b}_q e_{a-1}.$$

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

$$(M_q(a,b,c))^{-1} e_{a-1} = (-1)^{a+b-1} q^{- \binom{b+c}{2} ... ...inom{a+b+c}{2} - \binom{a+c}{2}} {\binom{a+b+c-1}{b}_q}^{-1} v.$$

Assim, a entrada (a-1,a-1) de (M_q(a,b,c))^-1 é

$$q^{- \binom{a+b}{2} + \binom{a}{2} - \binom{b+c}{2} + \binom{... ...{\binom{b}{2}} \frac{\binom{a+b-1}{b}_q}{\binom{a+b+c-1}{b}_q}$$

pois

$$\binom{a+b+c}{2} - \binom{a+b}{2} - \binom{a+c}{2} + \binom{a... ...= \binom{b+c}{2} - \binom{b}{2} - \binom{c}{2} + \binom{0}{2};$$

de fato, basta observar que $\binom{x}{2}$ é um polinômio de grau 2. Mas por Cramer esta entrada é $\det M_q(a-1,b,c) / \det M_q(a,b,c)$, o que conclui a demonstração.          $\blacksquare$