Question: Using, Burnside's Lemma, how many ways are there to $3$-color the $n$ bands of a baton if adjacent bands must be a different color?

Workings:

The first band has $3$ choices for color, the next bands has only $2$ choices since it can not be the same color as adjacent bands.

So $3 \times 2^{n-1}$ is the number of ways to chose these rings of a fixed baton.

If the baton revolves $180^o$ then

$3 \times 2^{\frac{n-1}{2}}$

So $N = \frac{1}{2} (3 \times 2^{\frac{n-1}{2}})$

I'm not sure if what I said is right. Any help will be appreciated

Answer: 
These batons represent the flip permutation group $F\_n$ on $n$
elements that contain two permutations. The cycle indices are

$$Z(F\_n) = \frac{1}{2}(a\_1^n + a\_2^{n/2})$$

for $n$ even and

$$Z(F\_n) = \frac{1}{2}(a\_1^n + a\_1 a\_2^{(n-1)/2})$$

for $n$ odd.

In order to apply Burnside we ask how many colorings are fixed by
these two permutations. This gives for the first case
$$\frac{1}{2}(3\times 2^{n-1} + 0)
= 3\times 2^{n-2}$$

when $n$ even and $n\ge 2$, because in order to be fixed by
$a\_2^{n/2}$ the two middle slots would have to have the same color
which is not admissible, and for the second case

$$\frac{1}{2}(3\times 2^{n-1} + 2\times 3\times 2^{(n-1)/2-1})
= 3\times 2^{n-2} + 3\times 2^{(n-1)/2-1}.$$

where $n\gt 1$. There are three colorings when $n=1$ and the formula
also applies here.

This gives the following sequence $\{A\_n\}$:
$$3, 3, 9, 12, 30, 48, 108, 192, 408, 768, 1584, 3072,\ldots$$

Admittedly this problem is *extremely simple* but since there was no
OEIS entry for the sequence I wrote a Maple program to compute it for
small $n$ by total enumeration. The program confirmed the values of
the sequence. This is the Maple code.

```

A :=
proc(n)
    if type(n, even) then return 3*2^(n-2) fi;

    3*2^(n-2)+3*2^((n-1)/2-1);
end;

verif :=
proc(n)
    option remember;
    local ind, res, ent, digits, str1, str2, pos;

    res := {};

    for ind from 3^n to 2*3^n-1 do
        digits := convert(ind, base, 3);

        for pos to n-1 do
            if digits[pos] = digits[pos+1] then
                break;
            fi;
        od;

        if pos = n then
            str1 := [seq(digits[pos], pos=1..n)];
            str2 := [seq(digits[n+1-pos], pos=1..n)];

            res := {op(res), {str1, str2}};
        fi;
    od;

    nops(res);
end;

```
The problem is that some colourings are invariant under reversal, so dividing by $2$ will under-count them. This is where Burnside comes in.