Icosagon Coloring

This is really an Algebra question, since it can be solved by a simple application of Burnside's Lemma : if a finite group $G$ acts on a finite set $X$ , then the number of orbits of this group action is equal to $\frac{1}{|G|}\sum_{g \in G}|F_X(g)|$ where $F_X(g) \; = \; \{ x \in X \,:\, g \cdot x = x \}$ is the set of elements of $X$ fixed by the group element $g$ .

In this case, let $X$ be the collection of $2^{20}$ different $2$ -colourings of an icosagon, and let the dihedral group $D_{40}$ , the full symmetry group of the icosagon, act on $X$ by performing the relevant rotation or reflection to any $2$ -colouring. Running through the various elements of $D_{40}$ :

• There is $1$ identity element, which fixes all elements of $X$ . Thus $|F_X(g)| = 2^{20}$ in this case.
• There are $8$ rotations of order $20$ . The $2$ -colourings that are fixed by such rotations are the ones where all sides have the same colour, and so $|F_X(g)| = 2$ in these cases.
• There are $4$ rotations of order $10$ . The $2$ -colourings that are fixed by such rotations are the ones where alternate sides have the same colour, and so $|F_X(g)| = 2^2$ in these cases.
• There are $4$ rotations of order $5$ . The $2$ -colourings that are fixed by such rotations are the ones where every fourth side has the same colour, and so $|F_X(g)| = 2^4$ in these cases.
• There are $2$ rotations of order $4$ . The $2$ -colourings that are fixed by such rotations are the ones where every fifth side has the same colour, and so $|F_X(g)| = 2^5$ in these cases.
• There is $1$ rotation of order $2$ . The $2$ -colourings that are fixed by this rotation are the ones where every tenth side has the same colour, and so $|F_X(g)| = 2^{10}$ in this case.
• There are $10$ reflections in axes through a pair of opposite vertices. There are $2^{10}$ $2$ -colourings fixed by such a reflection.
• There are $10$ reflections in axes through the midpoints of a pair of opposite edges. There are $2^{11}$ $2$ -colourings fixed by such a reflection.

Thus the total number of orbits is $\frac{1 \times 2^{20} + 8 \times 2 + 4 \times 2^2 + 4 \times 2^4 + 2 \times 2^5 + 1 \times 2^{10} + 10 \times 2^{10} + 10 \times 2^{11}}{40} = \boxed{27012}$

Indeeed, a generalisation of this argument shows us that the number of distinct $2$ -colourings of a regular $n$ -gon is $\frac{1}{2n}\sum_{d|n} \varphi\big(\tfrac{n}{d}\big)2^d + \tfrac34 \times 2^{\frac12n}$ when $n$ is even, and $\frac{1}{2n}\sum_{d|n}\varphi\big(\tfrac{n}{d}\big)2^d + 2^{\frac{1}{2}(n-1)}$ when $n$ is odd. The difference between these formulae results from the fact that there is only one type of reflection when $n$ is odd, as opposed to the two types of reflection that occur when $n$ is even.

The following python computer program goes through each possible coloring sequence ( $2^{20}$ of them, represented in binary notation) and uses a $2^{20}$ boolean item list $u$ to count them. If the sequence's corresponding item in $u$ is false, it hasn't been counted yet, so count it and then make that item in $u$ true and every rotation and reflection item in $u$ true as well.

After running the program, we find that the number of ways to color a regular icosagon with only two colors (where rotations or reflections of the same pattern are not considered a different way) is $\boxed{27012}$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

# Polygon Coloring
# Python

# Function that converts a decimal number
#  to a binary number.
def dec_to_bin(n):
    bstr = ""
    while n:
        bstr += str(int(n % 2))
        n = int(n / 2)
    if bstr == "":
        b = 0
    else:
        b = int(bstr[::-1])
    return b

# Function that converts a binary number
#  to a decimal number.
def bin_to_dec(n):
    r = str(n)[::-1]
    d = 0
    for a in range(0, len(r)):
        d += (int(r[a]) * 2 ** a)
    return d

# Function that finds the number of ways
#  to color a regular polygon with n sides
#  with only two colors (without rotations
#  or reflections).
def polycolor(n):
    total = 0
    # u is a list of True/False values, where
    #  each index number, when converted to binary,
    #  corresponds to a coloring pattern.
    #  Each item in u turns to True when its
    #  color sequence (or rotation or reflection
    #  of that color sequence) is counted.
    u = []
    for a in range(0, 2 ** n):
        u.append(False)
    # Go through each possible coloring sequence
    #  and compare it to u to see if it is counted
    #  already.  If not, add 1 to the total and
    #  turn the u index to True, as well as all
    #  the rotations and reflections of that 
    #  coloring sequence.
    for a in range(0, 2 ** n):
        if not u[a]:
            seq = str(dec_to_bin(a)).zfill(n)
            total += 1
            s = seq + seq
            r = s[::-1]
            for b in range(0, n):
                u[bin_to_dec(s[b:b + n])] = True
                u[bin_to_dec(r[b:b + n])] = True
    # Return the total number.
    return total

# Find and display the number of ways to color
#  a regular icosagon with only two colors (without
#  rotations or reflections).
print(polycolor(20))

This kind of object is known as a bracelet (or free necklace). See

https://en.wikipedia.org/wiki/Necklace_(combinatorics)

https://mathworld.wolfram.com/Necklace.html