# 3 Coloring a Baton of n Bands

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

• You are very near. Maybe it helps when you look carefully at the cases $n=3$, $n=4$, and $n=5$. In this way you can avoid invoking the full "Polya theory". – Christian Blatter Mar 20 '15 at 19:13
• If $n = 3$ the ways to colr the baton are $RBR, RBO, ROR, ROB, BRB, BRO, BOB, ORO, OBO$ these are 9. Using the formula I printed gives $3$. – ineedanewnames Mar 20 '15 at 19:21

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;

• Alright, thanks I never used Maple before and as far as I'm aware my university has no courses that deals with Maple which is odd considering I am getting a Computational Math degree. I do intend on learning it though. Thanks for the help! – ineedanewnames Mar 21 '15 at 0:55

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