2
$\begingroup$

I would like to apply Polya's Enumeration Theorem on some small case Problems.

I have some Solutions from the Book I have found, which is great by the way: "Graphical Enumeration by Harary and Palmer", but I am lacking some understand of algebra (and a lot of other stuff I don't even know about).

Problems:

a)"necklaces problem" 4 Beads, 2 Colors(black and white)

b)"necklaces problem" 4 Beads, 3 Colors(red, white and blue)

c) Any modification of these two but with limits on pearls<4, this will be clear later why. (Maybe I am mistaken on this point)

Lets start with a)

img

What I have understood so far, that A is Group determined by the object I want to enumerate. For the necklace problem its the $D_4$ Group. This here I don't get quite. I mean I can understand why its $D_4$. But I can modify it.

Qestion1: Maybe someone could provide an example what could be counted.

Let it now be the $D_4$ Group.

Now I am facing the next Problem, I need to evaluate $Z(D_4)$ I have no clue what this is, BUT the book tells me exactly how to calculate it.(Great Book by the way)

img2

Why the hell no one told me this before?! I need to calculate $Z(C_4)$ then plug in. On the page before one could find the Formula for $Z(C_4)$.

img2

Awesome! n=4, The Limitation k|n means k is in range of {1,2,4}, and $\varphi(k)$ take values $\varphi(1)=1,\varphi(2)=1,\varphi(4)=2$. The $s_i$ are variables, at least that's the book says, but the have a meaning. For example in $S_3$ Permutation Group on 3 letters:

img2

Question2: I have at this point no clue what $s_4$ in $S_4$ is.

Okey lets evaluate $$Z(C_4)=4^{-1}(s_1^4+1s_2^2+2s_4)$$ I have simply plugged in the values from above! Now I am applying the Corollary from above to get $D_4$ (used the even option since n=4)

$$D_4=\frac{1}{2}Z(C_4)+\frac{1}{4}(s_2^{2}+s_1^2s_2)$$ $$D_4=\frac{1}{2}4^{-1}(s_1^4+1s_2^2+2s_4)+\frac{1}{4}(s_2^{2}+s_1^2s_2)$$ $$D_4=\frac{1}{8}(s_1^4+2s_1^2s_2+3s_3^2+2s_4)$$

nice this is also what the book says at this point.

img2

Question 3: How now the 1+x comes into play? Will this part by modified if I have more beads? It definitely gets modified if I get more colors.

Now the great finale!

img2

Question4: Why is the Number of Necklaces C(1), What do i get for C(0),C(2),C(4) The book says its C(1)

Now short version of b)

img2

Question 5: Why is $c(x)=1+x_1+x_2$ and $Z(D_4,3)$ ?

Maybe someone could help me with these Problems/Questions or point in the right direction to look it up? Obviously it is not that hard(from the calculations point of view) to apply. But my algebra skills are,.....

$\endgroup$
  • 3
    $\begingroup$ A rather long question! $\endgroup$ – Peter Aug 1 '17 at 19:10
  • 2
    $\begingroup$ A question with numerous ramifications. There is this link at MSE meta that collects posts on PET and Burnside by various users. $\endgroup$ – Marko Riedel Aug 1 '17 at 20:10
  • $\begingroup$ @MarkoRiedel thanks great collection. I will go through them,....will take some time. When applied on small cases, its very compact and can be calculated by hand. But I am lacking some understanding, on what going on inside. The book covered the Algebra I needed. But, still some questions remained. This 1+x, if connected to the weighted funtion i guess? $\endgroup$ – thetha Aug 2 '17 at 7:32
  • 1
    $\begingroup$ I prepared a set of notes on this some time ago which you may find useful: Polya Enumeration Theorem. It might have helped to narrow the scope of the question by presenting the components one at a time, one component per post. $\endgroup$ – Marko Riedel Aug 5 '17 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.