dempolya

Demonstração do Teorema de Polya

A demonstração do teorema de Polya depende de uma versão generalizada do Lema de Burnside:

Lema de Burnside (com pesos)

Seja um grupo finito que actua como um grupo de permutações num conjunto ${\mathcal{O}}$ de objectos. Seja uma função peso que toma o mesmo valor constante em cada órbita (podemos pois ver como uma função em ${\mathscr{C}}/G$ - o espaço dos padrões.

Então a soma dos pesos das diversas órbitas é dado por:

(26)

Nota: O lema usual (8) obtem-se tomando os pesos todos iguais a 1 - $w(k)\equiv 1 \Rightarrow W(c)\equiv 1$ .

Demonstração do Lema de Burnside ... Quantas vezes é que uma dada ``coloração, $c\in {\mathscr{C}}$ entra na soma $\sum_{g\in G}\sum_{c\in {\hbox{\small Fix($g$)}}}\, W(c)$ ? Tantas vezes quantas o cardinal $\vert\hbox{Isotr}(c)\vert$ do subgrupo de isotropia de $ c$ .

Todas as colorações que estão na mesma órbita de $ c$ entram na soma o mesmo número de vezes uma vez que todos os seus estabilizadores têm o mesmo cardinal. Portanto, a contribuição da órbita de $ c$ é $\vert\hbox{Isotr}(c)\vert \cdot \vert\hbox{Orb}(c)\vert$ que, pela fórmula (4), é igual a:

$\displaystyle \vert\hbox{Isotr}(c)\vert\cdot \vert\hbox{Orb}(c)\vert=\vert G\vert$

Vemos pois que cada órbita dá a mesma contribuição $\vert G\vert$ , para a soma $\sum_{g\in G}\sum_{c\in {\hbox{\small Fix($g$)}}}\, W(c)$ . A soma total é portanto $\vert G\vert\times$ a soma dos pesos das órbita $[c]\in {\mathscr{C}}/G$ , isto é:

$\displaystyle \vert G\vert\cdot \sum_{[c]\in{\mathscr{C}}/G} W([c])= \sum_{g\in G}\sum_{c\in {\hbox{\small Fix($g$)}}}\, W(c)$

que é exactamente a igualdade que se pretendia provar.

$\blacksquare.$

Demonstração do Teorema de Polya

Por definição do inventário de padrões e pelo lema de Burnside, temos que:

$\displaystyle \hbox{\bf IP}= \sum_{[c]\in {\mathscr{C}}/G}\, W([c])=\frac{1}{\vert G\vert} \sum_{g\in G}\,\sum_{c\in {\hbox{\small Fix($g$)}}}\, W(c)$

Recordando a definição (11) do índice de ciclos , resta pois mostrar que:

$\displaystyle \left(\sum_{k\in {\mathcal{K}}} w(k)\right)^{\ell_1(g)} \left(\su... ...} w(k)^2\right)^{\ell_2(g)} \cdots =\sum_{c\in {\hbox{\small Fix($g$)}}}\, W(c)$

(27)

onde $\ell_j(g)=$ é o número de ciclos de comprimento $ j$

na decomposição de $ g$

em ciclos disjuntos.

Fixemos um $g\in G$ , visto como uma permutação dos objectos (vértices) de ${\mathcal{O}}$ , e calculemos $\sum_{c\in {\hbox{\small Fix($g$)}}}\, W(c)$ .

Suponhamos que $ g$ decompõe ${\mathcal{O}}$ em ciclos disjuntos ${\mathcal{O}}_1,{\mathcal{O}}_1,\cdots,{\mathcal{O}}_m$ . Como já vimos:

$\displaystyle c\in \hbox{Fix}(g) \ \ \ \ \Leftrightarrow \ \ \ \ \hbox{ $c$ é constante em cada ${\mathcal{O}}_i,\, i=1,\cdots,m$}$

Portanto a soma $\sum_{c\in {\hbox{\small Fix($g$)}}}\, W(c)$ não é mais do que a soma:

$\displaystyle \sum\left\{W(c): \ \ c\in{\mathscr{C}}\ \ \hbox{é constante em cada ${\mathcal{O}}_i$}\right\}$

(28)

Recordando que o peso $ W(c)$ de uma coloração $c:{\mathcal{O}}\to {\mathcal{K}}$ é, por definição, igual ao produto dos pesos das cores usadas em $ c$ : $W(c)=\prod_{o\in {\mathcal{O}}}w(c(o))$ , vemos que a soma (28) é igual ao produto:

$\displaystyle \prod_{i=1}^m\sum_{k\in{\mathcal{K}}}(w(k))^{\vert{\mathcal{O}}_i... ...cal{O}}_1\vert}\sum_{k\in{\mathcal{K}}}(w(k))^{\vert{\mathcal{O}}_2\vert}\cdots$

(29)

Suponhamos agora que a decomposição de $ g$ em ciclos disjuntos tem $\ell_1(g)=$ ciclos de comprimento $ 1$ , $\ell_2(g)=$ ciclos de comprimento $ 2$ , $\ell_3(g)=$ ciclos de comprimento $ 3$ , etc.

Entre os números $\vert D_1\vert$ , $\vert D_2\vert$ , $\vert D_3\vert$ , ...

$\begin{displaymath}\begin{array}{ccccc} \hbox{o número} & 1 & \hbox{ocorre} & \... ...re} & \ell_3(g) & \hbox{vezes} \\ ... & & & & \\ \end{array}\end{displaymath}$

Portanto o produto (29) pode ser escrito na forma:

$\begin{displaymath}\begin{array}{ccccc } & \sum w(k)\cdot \sum w(k)\cdot\sum w(... ..._2(g) & \hbox{vezes} \\ \times & \cdots & & & \\ \end{array}\end{displaymath}$

isto é, é igual a:

$\displaystyle \left(\sum_{k\in {\mathcal{K}}} w(k)\right)^{\ell_1(g)}\left(\sum... ...ht)^{\ell_2(g)} \left(\sum_{k\in {\mathcal{K}}} w(k)^3\right)^{\ell_3(g)}\cdots$

como se pretendia.

$\blacksquare.$

Regresso ao texto principal

Página seguinte
Página anterior
Índice