Quantos colares existem com n pérolas,

b das quais são brancas, v são vermelhas e p são pretas (b+v+p=n)?

Colorações

Para responder a questões deste tipo, convém generalizar as situações já descritas, colocando-as num quadro mais geral. Para isso analisemos o que há de essencial nos exemplos anteriores.

Essencialmente o que temos é:

${\mathcal{O}}$ um conjunto finito de objectos.

${\mathcal{K}}$ um conjunto finito de ``cores".

Uma aplicação:

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

diz-se uma coloração dos objectos em ${\mathcal{O}}$ , usando as cores de ${\mathcal{K}}$ .

${\mathscr{C}}=\{c:{\mathcal{O}}\to{\mathcal{K}}\}$ diz-se o conjunto das colorações de ${\mathcal{O}}$ .

Na questão que dá o título a esta secção, temos que:

${\mathcal{O}}=$ {vértices de um polígono regular de vértices} (os pontos onde colocamos as pérolas do colar) e
${\mathcal{K}}=$ {Branco, Vermelho, Preto} é o conjunto das cores das pérolas.

Padrões

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 colorações de ${\mathcal{O}}$ , definida por:

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

Isto significa que cada elemento $ g$ do grupo transforma uma dada coloração $ c$ numa outra coloração $ gc$ . Esta última define-se por:

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

(20)

isto é, a côr que $ gc$

atribui ao objecto $o\in{\mathcal{O}}$ é a côr que tem o objecto $g^{-1}\cdot o$ (o objecto $ o$

antes de ``rodar").

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

Uma classe de equivalência (= órbita) diz-se um padrão. O padrão da coloração $ c$ nota-se por $ [c]$ .

O problema

O problema consiste em contar quantos padrões existem e ainda exibir um inventário dos diversos padrões.

Pesos

Para isso, vamos atribuir um peso a cada côr em $k\in{\mathcal{K}}$ . Por exemplo, quando ${\mathcal{K}}=\{\hbox{Branco,Vermelho,Preto}\}$ é o conjunto das cores das pérolas, atribuímos os pesos:

$\displaystyle w(\hbox{Branco})=B, \ \ \ \ \ w(\hbox{Vermelho})=V, \ \ \ \ \ w(\hbox{Preto})=P$

Os pesos são variáveis formais independentes que geram uma álgebra (podem ser adicionados e multiplicados formalmente). Um deles pode ser escolhido para desempenhar o papel de uma unidade $ 1$ .

O peso de uma coloração $c:{\mathcal{O}}\to {\mathcal{K}}$ é, por definição, igual ao produto dos pesos das cores usadas em :

$\displaystyle W(c)=\prod_{o\in {\mathcal{O}}}w(c(o))$

(21)

Note que o peso de duas colorações equivalentes é o mesmo. Portanto faz sentido falar no peso de cada padrão $[c]\in {\mathscr{C}}/G$ . Basta pôr:

$\displaystyle W([c])=W(c)$

O inventário de padrões

Vamos agora construir uma série enumerativa de potências IP, chamada o inventário de padrões, usando os pesos de cada padrão. Define-se por:

$\displaystyle \hbox{\bf IP}=\sum_{[c]\in{\mathscr{C}}/G}\, W([c])$

(22)

Como veremos, no caso dos colares, o coeficiente do monómio $ B^bV^vP^p$ do inventário de padrões $\hbox{\bf IP}(B,V,P)$ , dá o número de colares que têm exactamente b pérolas brancas, v pérolas vermelhas e p pérolas pretas.

Teorema de Polya

O inventário de padrões é dado em termos do índice de ciclos de $ G$

, através da fórmula:

(23)

Como aplicar o teorema de Polya

Apliquemos a fórmula de Polya (23) à situação dos colares.

Quantos padrões de colares existem com 6 pérolas b das quais são brancas, e p são pretas (b+p=6) ?

Aqui $ G=D_6$ . ${\mathcal{K}}$ e os pesos são os que já se indicaram antes. O índice de ciclos de $ D_6$ é, como vimos antes:

$$\displaystyle {\bf Z}_{D_6}(X_1,X_2,\cdots,X_6)=\frac{1}{12}$

Como:

$\displaystyle \sum_{k\in {\mathcal{K}}} w(k)$	$\displaystyle =$	$\displaystyle B+ P$
$\displaystyle \sum_{k\in {\mathcal{K}}} w(k)^2$	$\displaystyle =$	$\displaystyle B^2+ P^2$
		$\displaystyle \vdots$
$\displaystyle \sum_{k\in {\mathcal{K}}} w(k)^6$	$\displaystyle =$	$\displaystyle B^6+ P^6$	(24)

o inventário de padrões é:

$\displaystyle \hbox{\bf IP}(B,V,P)$	$\displaystyle =$	$$\displaystyle {\bf Z}_{D_6}\left(X_1=\sum_{k\in {\mathcal{K}}} w(k),X_2 =\sum_{k\in {\mathcal{K}}}$
	$\displaystyle =$	$\displaystyle \frac{1}{12} \left((B+ P)^6+3(B+ P)^2(B^2+ P^2)^2+\right.$
		$$\displaystyle \ \$

Desenvolvendo, o coeficiente de $ B^bP^p$ dá o número de colares com 6 pérolas, b das quais são brancas, e p são pretas (b+p=6).

Quantos colares existem com 6 pérolas, b das quais são brancas, v são vermelhas e p são pretas (b+v+p=6)?

Aqui $ G=D_6$ e ${\mathcal{K}}$ e os pesos são os que já se indicaram antes. O índice de ciclos de $ D_6$ é, como vimos antes:

$$\displaystyle {\bf Z}_{D_6}(X_1,X_2,\cdots,X_6)=\frac{1}{12}$

Como:

$\displaystyle \sum_{k\in {\mathcal{K}}} w(k)$	$\displaystyle =$	$\displaystyle B+V+P$
$\displaystyle \sum_{k\in {\mathcal{K}}} w(k)^2$	$\displaystyle =$	$\displaystyle B^2+V^2+P^2$
		$\displaystyle \vdots$
$\displaystyle \sum_{k\in {\mathcal{K}}} w(k)^6$	$\displaystyle =$	$\displaystyle B^6+V^6+P^6$	(25)

o inventário de padrões é:

$\displaystyle \hbox{\bf IP}(B,V,P)$	$\displaystyle =$	$$\displaystyle {\bf Z}_{D_6}\left(X_1=\sum_{k\in {\mathcal{K}}} w(k),X_2 =\sum_{k\in {\mathcal{K}}}$
	$\displaystyle =$	$\displaystyle \frac{1}{12} \left((B+V+P)^6+3(B+V+P)^2(B^2+V^2+P^2)^2+\right.$
		$\displaystyle \ \ \left.4(B^2+V^2+P^2)^3+2(B^3+V^3+P^3)^2+2(B^6+V^6+P^6)\right )$

Desenvolvendo, o coeficiente de $ B^bV^vP^p$ dá o número de colares com 6 pérolas, b das quais são brancas, v são vermelhas e p são pretas (b+v+p=6).

Demonstração do Teorema de Polya

Página seguinte
Página anterior
Índice