2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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". $\endgroup$ – Christian Blatter Mar 20 '15 at 19:13
  • $\begingroup$ 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$. $\endgroup$ – ineedanewnames Mar 20 '15 at 19:21
1
$\begingroup$

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;
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – ineedanewnames Mar 21 '15 at 0:55
1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.