Resultados de contagem

O método das matrizes de Kasteleyn, exposto na seção anterior, permite demonstrar vários resultados de contagem ou q-contagem de coberturas de lozangos ou dominós. Selecionamos para serem enunciados três resultados clássicos deste tipo, devidos a MacMahon [M], Kasteleyn [K] e Elkies, Kuperberg, Larsen e Propp [EKLP].

Teorema 1.15: [K] Considere o retângulo de lados inteiros a e b; seja N o número de coberturas por dominós deste retângulo. Sejam $\alpha = \exp(2 \pi i/(a+1))$ e $\beta = \exp(2 \pi i/(b+1))$Então

$$N^4 = \prod_{i=1\ldots a, j=1\ldots b} \left({4 + \alpha^i + \alpha^{-i} + \beta^j + \beta^{-j}}\right),$$

Para o próximo teorema, definimos o diamante asteca de lado ncomo sendo a união dos quadrados unitários inteiros

$$[i,i+1]\times [j,j+1] \subseteq {\mathbb{R} }^2$$

para os quais

- n - 2 < i+j < n;

a figura mostra o diamante asteca de lado 3.

Teorema 1.16: [EKLP] Considere o diamante asteca de lado n. Temos

$$sum_T q^{h(T)} = \prod_{0 \le k < n} (1 + q^{2k+1})^{n-k}.$$

As demonstrações destes dois teoremas serão omitidas; diga-se apenas que eles admitem demonstrações por um método razoavelmente semelhante ao que usaremos para o Teorema 1.17. Este método é conhecido como matrizes de transferência (transfer matrices).

Teorema 1.17: [M] Considere o hexágono de lados inteiros a, b, c, a, b, ccom todos os ângulos internos iguais a $2\pi/3$. Então

$$\sum_T q^{h(T)} = \prod_{0 \le i < a, 0 \le j < b, 0 \le k < c} \frac{q^{i+j+k+2}-1}{q^{i+j+k+1}-1},$$

onde T varia sobre todas as coberturas por lozangos unitários do hexágono.

A figura mostra um hexágono de lados 2, 2, 2. Lembramos que a interpretação tridimensional diz que estas coberturas podem ser interpretadas como pilhas de cubos.

Dem: Supomos que a é o tamanho do lado vertical e b é o tamanho do lado seguinte (no sentido anti-horário). Pelo que vimos nas seções anteriores, temos

$$\sum_T q^{h(T)} = \pm q^\ast \det(B)$$

onde B é definida por

sendo que o sinal e o fator $q^\ast$ estão presentes para corrigir o valor do monômio correspondente à cobertura de altura zero. Os índices para os vértices podem parecer estranhos mas foram escolhidos de tal forma que se i > a então os vizinhos do vértice branco i todos têm índices maiores ou iguais a i. Assim a matriz B é da forma

$$B = \begin{pmatrix} \ast & \ast & \ast & \ast & \cdots & \ast... ...st \\ \ast & \ast & 0 & 0 & \cdots & 0 & + \\ \end{pmatrix},$$

onde os + representam entradas da forma $q^\ast$; i.e., B tem um grande bloco triangular superior antecedido de a linhas e colunas ``sujas''.

Para calcular o determinante de B bastaria escaloná-la usando as linhas de baixo para limpar as duas primeiras linhas sem alterar o determinante, obtendo assim uma matriz B'da forma

$$B' = \begin{pmatrix} \ast & \ast & 0 & 0 & \cdots & 0 & 0 \\ ... ...st \\ \ast & \ast & 0 & 0 & \cdots & 0 & + \\ \end{pmatrix},$$

cujo determinante é igual ao do bloquinho $a \times a$no canto superior esquerdo; nossa missão é portanto encontrar este bloquinho $\tilde B$.

Mas B' = XB onde X é da forma

$$X = \begin{pmatrix} 1 & 0 & \ast & \ast & \cdots & \ast & \as... ... & 1 & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 \\ \end{pmatrix};$$

a i-ésima linha ($i \le a$) é um vetor (v_i)^t tal que

$$(v_i)^t B = (\ast \ast 0 0 \cdots 0 0) = ((w_i)^t 0 0 \cdots 0 0),$$

i.e., tal que as a primeiras coordenadas são as únicas não nulas; chamando estas a primeiras coordenadas de w_i temos

$$\tilde B = \begin{pmatrix}(w_1)^t \\ (w_2)^t \\ \vdots \\ (w_a)^t \end{pmatrix}$$

e resta-nos encontrar os vetores v_i e w_i.

O vetor v_i associa a cada vértice branco um coeficiente em ${\mathbb{C} }(q)$; a figura mostra v₁ no nosso exemplo favorito (a forma como os coeficientes foram obtidos será explicada a seguir):

O vetor (v_i)^t B, por outro lado, associa um coeficiente a cada vértice preto. Para obter o coeficiente de um vértice devemos somar os coeficientes dos vértices vizinhos multiplicados pelos coeficientes das arestas. Vejamos w₁ no nosso exemplo:

Os coeficientes de v_i podem ser preenchidos obedecendo a ordem dos vértices brancos. Inicialmente tomamos os valores obrigatórios nas primeiras a coordenadas (1 na i-ésima coordenada, 0 nas demais). Depois preenchemos o j-ésimo vértice branco (j > a) com o valor necessário para que a j-ésima coordenada de (v_i)^t B seja igual a 0: a estrutura da matriz B garante que isto é sempre possível de forma única. Finalmente, calculamos os primeiros a coeficientes de (v_i)^t B, que nos dão o vetor w_i.

Os coeficientes de B foram escolhidos de tal forma que os coeficientes de v_i são da forma

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

e o j-ésimo coeficiente de w_i é

$$q^{(b+c)(i-1) + \binom{j}{2}} \binom{b+c}{b-i+j};$$

Assim, a menos de multiplicar linhas e colunas por potências de q, $\tilde B$ coincide com

$$\begin{pmatrix} q^{\binom{b}{2}} \binom{b+c}{b}_q & q^{\binom... ... \cdots & q^{\binom{b}{2}} \binom{b+c}{b}_q \\ \end{pmatrix},$$

a matriz da proposição 1.14 acima. Como $\det {\tilde B} = \pm q^{\ast} \sum_T q^{h(T)}$, usando esta proposição temos

$$\sum_T q^{h(T)} = \pm q^{\ast} \prod_{0 \le i < a, 0 \le j < b, 0 \le k < c} \frac{q^{i+j+k+2}-1}{q^{i+j+k+1}-1};$$

como o coeficiente de q⁰ é igual 1 dos dois lados isto demonstra o teorema.          $\blacksquare$