3
$\begingroup$

Given a circle divided into 2n equal sectors, how many ways can it be painted with two colors so that opposite sectors are not the same color? I'm interested in the number of solutions that are unique under rotation.

I've tried to enumerate the early situations and see patterns but haven't seen a path to a general solution. I think I only have three rules of thumb at the moment:

  1. There will be n sectors of each color
  2. An alternating paint job is only legal when n is odd.
  3. I think we're bounded on top by 2^(n-2) for n>1.

I may have missed some examples but this link has my work so far: http://i.imgur.com/ZQylapu.png

If I've gotten everything, then the series goes:

  • n=1, 1
  • n=2, 1
  • n=3, 2
  • n=4, 2
  • n=5, 4
  • n=6, 6

n=6 is notable as two of the combinations are left- and right-handed versions of a similar arrangement. I imagine this becomes much more common beyond n=6. I counted these separately, but a general solution that wouldn't would be nice as well.

$\endgroup$
  • $\begingroup$ How do you define opposite sector? If each sector has just one opposite then why wouldn't they answer by $2^n$? $\endgroup$ – fleablood Oct 12 '15 at 0:31
  • $\begingroup$ Oh, I guess the unique under rotation puts a damper on it. $\endgroup$ – fleablood Oct 12 '15 at 0:33
  • $\begingroup$ Huh, I have difficulty putting words to what I mean by opposite. What comes to mind is two sectors are opposites if the number of sectors between them in the clockwise direction is equal to the number in the counter-clockwise direction. $\endgroup$ – Polyhog Oct 12 '15 at 0:37
  • $\begingroup$ No I get your definition. As a pair of sectors has no relation to other sectors the answer would be $2^n$ as each pair of sectors has two choices. But if they are unique to rotation, we have to calculate how many are equivalent under rotation. Good question. $\endgroup$ – fleablood Oct 12 '15 at 0:54
  • $\begingroup$ Here's a thought. Fix sector 1. then for sector i = 2 to n give a binary value for color and add $2^i$ for green and nothing for yellow. Thus you'll have a 1-1 correspondence between colorings and the numbers from 1 to $2^{n - 1}. Now, we have to come up with a formula for determining if two numbers represent the same coloring under rotation. $\endgroup$ – fleablood Oct 12 '15 at 1:00
3
$\begingroup$

This can be done using Burnside's lemma. We need to count the assignments of colors being fixed by each type of permutation from among the $2n$ permutations total in the cycle index $Z(C_{2n})$ of the cyclic group acting on the sectors.

There are $$\varphi(d)$$ permutations having cycle structure $$a_d^{2n/d}$$ in the cycle index $Z(C_{2n})$ where $d|2n.$

For a permutation to fix an assignment it needs to be constant on the cycles. Suppose that the cycle length $d$ is even and pick one of its elements. The slot opposing this element is also located on this cycle. But they must have different colors, so there are no valid assignments fixed by a permutation of shape $a_d^{2n/d}$ when $d$ is even.

On the other hand when $d$ is odd the $2n/d$ cycles of length $d$ are grouped into $n/d$ pairs which are reflections of each other and hence must have opposite colors. Therefore there are two possible assignments of colors to these cycles forming a pair (as opposed to four if there were no constraint). This yields a contribution of $$\varphi(d) 2^{n/d}.$$

Averaging this over the total $2n$ permutations we get $$\frac{1}{2n} \sum_{d|2n,\;d\;\mathrm{odd}} \varphi(d) 2^{n/d}$$

which is $$\frac{1}{2n} \sum_{d|n,\;d\;\mathrm{odd}} \varphi(d) 2^{n/d}.$$

This yields the sequence $$1, 1, 2, 2, 4, 6, 10, 16, 30, 52, 94, 172, 316, 586, 1096, \\ 2048, 3856, 7286,\ldots$$

which is OEIS A000016 where additional material awaits.

I found the OEIS entry by using a simple total enumeration algorithm (definitely not optimized) to compute the first few values (practical to about $n=10$ which is enough to conclusively identify the sequence). This was the Maple code:

with(numtheory);

sectors :=
proc(n)
    option remember;
    local d, ind, orbits, orbit, rot, pos;

    orbits := {};

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

        for pos to n do
            if d[pos] = d[pos+n] then
                break;
            fi;
        od;

        if pos = n+1 then
            orbit := {};
            for rot from 0 to 2*n-1 do
                orbit := {op(orbit),
                          [seq(d[q], q=1+rot..2*n),
                           seq(d[q], q=1..rot)]};
            od;

            orbits := {op(orbits), orbit};
        fi;
    od;

    nops(orbits);
end;

Q :=
proc(n)
    1/2/n*
    add(phi(d)*2^(n/d), d in
        select(d->type(d,odd), divisors(n)));
end;
$\endgroup$
  • $\begingroup$ That is brilliant. The equation you reached is also is the same for number of binary sequences coming from a shift register complementing the last output (equivalent to going through the circle and outputting the sector's color as binary number). Thank you! $\endgroup$ – Weaam Oct 12 '15 at 3:04
  • $\begingroup$ This was not original work. The calculation is just about included in the OEIS entry, it only needed filling in the details. $\endgroup$ – Marko Riedel Oct 12 '15 at 3:06
  • $\begingroup$ Still! It is a great answer. $\endgroup$ – Weaam Oct 12 '15 at 3:22

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.