Outra versão do teorema de Polya

Introdução

Existem várias aplicações muito importantes do teorema de Polya. Por exemplo:

contagem de grafos
contagem de compostos químicos (isómeros)
contagem de objectos musicais (acordes, padrões rítmicos, séries tonais, etc)

Estas aplicações serão tratadas brevemente nesta Área de Divulgação Matemática do CMUP.

Para essas aplicações é conveniente reformular o teorema de Polya usando uma linguagem mais abrangente e figurativa.

Conteúdo
de uma figura

Como na secção anterior, seja:

${\mathcal{O}}$ um conjunto finito de objectos (caixas, posições, etc).

${\mathcal{F}}$ um conjunto finito de ``figuras", "cores", etc.

A cada figura $f\in {\mathcal{F}}$ é atribuído um conteúdo que é um inteiro não negativo:

$$\displaystyle f\in {\mathcal{F}}\longmapsto$

Série enumerativa
de figuras

A série enumerativa de figuras é, por definição, a série:

$\displaystyle F(x)=F_0+F_1\,x+F_2\,x^2+ \cdots+F_k\,x^k+\cdots$

(30)

onde:

$\displaystyle F_0$	$\displaystyle =$	$$\displaystyle \hbox{número de$
$\displaystyle F_1$	$\displaystyle =$	$$\displaystyle \hbox{número de figuras de$
$\displaystyle F_2$	$\displaystyle =$	$\displaystyle \hbox{número de figuras de conteúdo $2$}$
	$\displaystyle \vdots$		(31)

Configurações
Padrões

Uma aplicação:

$\displaystyle c:{\mathcal{O}}\longrightarrow {\mathcal{F}}$

diz-se uma configuração (ou coloração, como antes) . Uma configuração é pois uma maneira de pôr uma figura em cada caixa, permitindo que a mesma figura seja posta em duas ou mais caixas ( $ c$

não precisa de ser injectiva).

${\mathscr{C}}=\{c:{\mathcal{O}}\to{\mathcal{F}}\}$ é o conjunto das configurações em ${\mathcal{O}}$ .

Suponhamos agora que temos um grupo que actua (à esquerda) no conjunto ${\mathcal{O}}$ dos objectos:

$\begin{displaymath}\begin{array}{cccc}$

Esta acção induz uma acção (à esquerda) no conjunto ${\mathscr{C}}=\{c:{\mathcal{O}}\to{\mathcal{K}}\}$ das configurações de ${\mathcal{O}}$ , definida por:

$\begin{displaymath}\begin{array}{cccc}$

onde:

$\displaystyle (gc)(o)=c(g^{-1}\cdot o)$

(32)

Como antes, duas configurações dizem-se equivalentes se e só se pertencem à mesma órbita da acção de em ${\mathscr{C}}$ , isto é, sse existe $g\in G$ tal que .

Uma classe de equivalência (=órbita) diz-se um padrão. O padrão da configuração nota-se, como antes, por .

O problema

O problema consiste em contar quantos padrões $ [c]$

existem e exibir um inventário dos diversos padrões.

Conteúdo
de uma configuração

O conteúdo $\hbox{cont}(c)$ de uma configuração é a soma dos conteúdos das figuras utilizadas por essa configuração:

$\displaystyle \hbox{cont}(c)=\sum_{o\in {\mathcal{O}}}{\hbox{conteúdo $c(o)$}}$

(33)

Por exemplo, no caso dos colares de pérolas brancas e pretas ${\mathcal{F}}=$ {Branca, Preta}, com conteúdo(Branca)=0 e conteúdo(Preta)=1, a série enumerativa de figuras reduz-se a:

$\displaystyle F(x)=1 + x$

O conteúdo $\hbox{cont}(c)$ de uma configuração (=coloração) $ c$

é pois igual ao seu número de bolas pretas.

Se atribuírmos o peso a cada figura $f\in {\mathcal{F}}$ de conteúdo :

$\displaystyle w(f)=x^k, \ \ \ \ \ \ \ \hbox{se} \ \ \hbox{conteúdo}(f)=k$

vemos que:

$\begin{displaymath}\begin{array}{ccccc} \sum_f\, w(f) & = & F_0+F_1\,x+F_2\,x^2+... ... & F_0+F_1\,x^k+F_2\,x^{2k}+ \cdots & = & F(x^k) \\ \end{array}\end{displaymath}$

(34)

Por outro lado, o peso total $W(c)=\prod_{o\in{\mathcal{O}}}\,w(c(o))$ de uma configuração ${\mathcal{O}}\to{\mathcal{F}}$ (veja (21)), é dado por:

$\displaystyle W(c)$	=	$\displaystyle \prod_{o\in{\mathcal{O}}}\,w(c(o))$
	=	$\displaystyle \prod_{o\in{\mathcal{O}}}\, x^{ \hbox{\small conteúdo de $c(o)$} }$
	=	$\displaystyle x^{\sum_{o\in{\mathcal{O}}}\,(\hbox{\small conteúdo de $c(o)$)} }$
	=	$\displaystyle x^{ \hbox{\small cont $c $} }$	(35)

Como antes, o peso $ W(c)$ é o mesmo para todos os elementos da órbita de $ c$ : $ W(c)=W(gc)$ . Podemos pois falar do peso de um padrão (=órbita): $ W([c])=W(c)$ . Por (35) tem-se que:

$\displaystyle W([c])=x^{ \hbox{\small cont $c $} }$

(36)

Série enumerativa de padrões

A série enumerativa de padrões conta o número total de padrões. Como a cada padrão está atribuído um peso, de acordo com (36), essa série é:

$\displaystyle P(x)=P_0+P_1\,x+P_2\,x^2+ \cdots+P_k\,x^k+\cdots$

(37)

onde

$\displaystyle P_0$	=	$\displaystyle \hbox{número de padrões de conteúdo $0$}$
$\displaystyle P_1$	=	$\displaystyle \hbox{número de padrões de conteúdo $1$}$
$\displaystyle P_2$	=	$\displaystyle \hbox{número de padrões de conteúdo $2$}$
	$\displaystyle \vdots$		(38)

De novo o inventário de padrões

Recorde que o inventário de padrões $\hbox{\bf IP}$ foi definido por $\hbox{\bf IP}=\sum_{[c]\in{\mathscr{C}}/G}\, W([c])$ . Portanto:

$\displaystyle \hbox{\bf IP}=P(x)$

Por outro lado, o teorema de Polya diz que:

$\displaystyle \hbox{\bf IP}={\bf Z}_G\left(\sum_{f\in {\mathcal{F}}} w(f), \sum_{f\in {\mathcal{F}}} w(f)^2, \sum_{f\in {\mathcal{F}}} w(f)^3 \cdots\right)$

e, usando as relações (34) vemos que:

$\displaystyle P(x)= \hbox{\bf IP}= {\bf Z}_G\left(F(x), F(x^2),\cdots\right)$

(39)

Obtemos assim a seguinte reformulação do teorema de Polya:

Teorema de Polya
(segunda versão)

Teorema de Polya II

Suponhamos que um grupo $ G$ actua num conjunto de configurações ${\mathscr{C}}=\{c:{\mathcal{O}}\to{\mathcal{F}}\}$ e seja $ F(x)$ a série enumerativa de figuras.

Então o número de padrões é contado pela série $ P(x)$ , obtida substituindo $ F(x^k)$ em cada $ X^k$ no índice de ciclos de $ G$ :

(40)

Aplicação

Quantos padrões de colares de 8 pérolas brancas e pretas existem??

Como vimos o índice de ciclos de $ D_8$ é:

$\displaystyle Z_{D_8}=\frac{1}{16}\, \left(X_1^8+4X_1X_2^3+5X_2^4+2X_4^2+4X_8\right)$

Substituindo $ F(x)=1+x$ obtemos a série enumerativa de padrões:

$\displaystyle P(x)=\frac{1}{16}\, \left((1+x)^8+4(1+x)(1+x^2)^3+5(1+x^2)^4+2(1+x^4)^2+4(1+x^8)\right)$

que se reduz a:

$\displaystyle P(x)=1+x+4x^2+5x^3+8x^4+5x^5+4x^6+x^7+x^8$

Logo existem 30 colares. Destes existem, por exemplo, 8 com 4 brancas e 4 pretas, etc....

REFERÊNCIAS

V. Krishnamurthy, "Combinatorics, theory and applications", John Wiley & Sons, 1986
de Brujn, N.G. "Polya's theory of counting" in Applied Combinatorial Mathematics, eds. Beckenbach, pag. 144-184, Wiley, 1964
Tucker, A. "Applied Combinatorics", Wiley, 1980.

Página anterior
Índice