next up previous contents
Next: Coberturas por dominós e Up: Dominós e q-contagem Previous: Números binomiais

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

\begin{displaymath}(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}. \end{displaymath}

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

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

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

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

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

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

Pensando em permutações como listas de números, um elemento de Sn+1 é obtido a partir de um elemento de Sninserindo 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

\begin{displaymath}\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}\end{displaymath}

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

\begin{displaymath}\binom{n}{m}_q = \frac{(n!)_q}{(m!)_q \cdot ((n-m)!)_q}. \end{displaymath}

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,

\begin{displaymath}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)}. \end{displaymath}

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

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

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 qa, 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 q24. O leitor pode verificar diretamente, por exemplo, que

\begin{displaymath}\binom{4}{2}_q = q^4 + q^3 + 2 q^2 + q + 1. \end{displaymath}

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) + qb 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 qm(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 qi e de qm(n-m) - isã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 W1e cada um deles precisa ser engordado com um elemento de V - V1para virar um W: existem qn+1 - qn = qn (q-1) elementos de V - V1mas cada W é gerado por qm+1 - qm = qm (q-1) destes elementos. Assim, temos qn-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) = qn-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 Kn (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 A1 e A2 definem o mesmo subespaço Wse e somente se existe uma matriz quadrada inversível B com A1 = B A2. 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:

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

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

é 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$


\begin{figure}\begin{center}
\epsfig{width=3cm,file=q1-2c.eps}\end{center} \end{figure}

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

\begin{displaymath}\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}.
\end{displaymath}

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):

\begin{displaymath}\binom{\ell}{m}_q - \binom{\ell-1}{m}_q =
q^{\ell-m} \binom{\ell-1}{m-1}_q.\end{displaymath}

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

\begin{displaymath}\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.
\end{displaymath}

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

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

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

\begin{displaymath}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};
\end{displaymath}

por indução, basta mostrar que

\begin{displaymath}\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}.
\end{displaymath}

Defina

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

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

\begin{displaymath}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.
\end{displaymath}

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

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

ou seja

\begin{displaymath}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).
\end{displaymath}

Temos

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

Se w = Mq(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

wi = (-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 Pq 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 wi = 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

\begin{displaymath}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}.
\end{displaymath}

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

\begin{displaymath}(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.\end{displaymath}

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

\begin{displaymath}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}
\end{displaymath}

pois

\begin{displaymath}\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};
\end{displaymath}

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$


next up previous contents
Next: Coberturas por dominós e Up: Dominós e q-contagem Previous: Números binomiais
Nicolau C. Saldanha
1999-08-10