5
$\begingroup$

Polya Enumeration Formula gives us 6 equivalence classes of 2-colorings of a square. But, in the Polya coloring, the following 2 colorings belong to 2 different equivalence classes:

00
01

and

11
10

(0 and 1 are the 2 colors.)

What is the theory that groups colorings like the above 2 into the same equivalence class? The reason to put the above 2 into the same class would be that we can obtain one from the other by a mapping between the colors (0->1 and 1->0). Is there a formula to obtain the number of equivalence classes of colorings with this constraint?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

There is a paper A survey of generalizations of Pólya's enumeration theorem which discusses a generalization of Polya's theorem involving colors. It gave Enumerative Combinatorial Problems Concerning Structures as a reference for this generalization. I think this is the theorem that you are looking for and and the variant referred to by Yuan in his answer to your question.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks so much! I need to write a program to apply this on a cube with 4-8 colors. Is there a textbook or paper that explains this theorem in a way accessible to non-math folks? $\endgroup$
    – user4355
    Commented Mar 4, 2010 at 0:38
  • 1
    $\begingroup$ There is another nice survey about Polya's work, again by De Bruijn, (Polya's Theory of Counting) in Applied Combinatorial Analysis (editor Ed Beckenbach), Wiley, 1964. There are also nice treatments in the combinatorics books by Fred Roberts and Alan Tucker. $\endgroup$
    – Joseph Malkevitch
    Commented Mar 4, 2010 at 1:28
  • $\begingroup$ Applied Combinatorics by Alan Tuckers covers PET but not the extensions by De Brujin. I will check out the other books you referred to. $\endgroup$
    – user4355
    Commented Mar 7, 2010 at 22:08
  • $\begingroup$ I could not find the Applied Combinatorial Analysis work anywhere. The Fred Roberts book does not cover the PET generalization. However, it did point to the book Introduction to Combinatorial Mathematics by C. L. Liu which I found covers this a bit. $\endgroup$
    – user4355
    Commented Mar 10, 2010 at 15:24
6
$\begingroup$

The PET (if you're referring to the same thing I'm thinking of) is a special case of Burnside's lemma, which still applies here - but the group is slightly larger. Instead of the group $C_4$ of rotations of a square (which I assume is the group of symmetries you care about - it might be $D_4$ instead, so this is ambiguous), you get the direct product of $C_4$ with $C_2$ (the group that permutes the colors). Burnside's lemma still applies to this larger group.

More generally, de Brujin developed a variant of Polya theory in which a group acts on the colors as well as the slots; unfortunately, I don't know a reference for it.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .