Counting necklace with no adjacent beads are of the same color

Question

I've read that one can use the Polya enumeration theorem or the Burnside's lemma to count the number of necklaces using $n$ beads from $k$ colors. Can we then find a way to count the number of necklaces such that no adjacent beads are of the same color?

Answer 1

To solve this using Burnside we start with the cycle index of the cyclic group $Z(C_n)$ which is given by

$$Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d} = \frac{1}{n} \sum_{d|n} \varphi(n/d) a_{n/d}^d.$$

The next step is to determine how many proper colorings are fixed by a permutation with cycle structure $a_{n/d}^d.$ Now when $d=1$ all slots are on the same cycle so there cannot possibly be a proper coloring when $n\ge 2$ and we must record for later that this case yields a zero contribution. On the other hand when $d\ge 2$ the cycles partition the slots into adjacent segments of length $d$ where the slots on each segment are all situated on different cycles. (One cycle is mapped to the next by a rotation of $2\pi/n.$) Observe that by the cyclic symmetry every such segment is preceded and followed by another segment just like it. The segments are directed and the colorings on all segments are the same because the cycles are monochrome as required by Burnside. Therefore we may regard the segments as circular because the last slot of a segment is followed by a repeat of the color from the first slot of the segment. Hence the colorings fixed by a permutation of cycle structure $a_{n/d}^d$ are precisely the proper colorings of a cycle on $d$ nodes (no symmetries) given by the chromatic polynomial $P_d(t)$ at $t=k$ which is

$$P_d(k) = (k-1)^d + (-1)^d\times (k-1).$$

This produces zero when $d=1$ as pointed out earlier. We thus get the closed form

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{n} \sum_{d|n} \varphi(n/d) P_d(k).}$$

We get $k$ colorings when $n=1$ as a special case where we replace the zero value from the formula. This is open to discussion, we could also argue that a singleton is adjacent to itself and hence admits no proper colorings.

This material is not original and was sourced at mathoverflow.net.

Remark. The technique from the hint (AIME 2016) provided in the comments to the OP can be used to compute the chromatic polynomial that was used. We encode the fact that adjacent colors must be different in a generating function, as follows:

$$f(z) = \prod_{q=1}^d (z + z^2 + z^3 + \cdots + z^{k-1}) = (z + z^2 + z^3 + \cdots + z^{k-1})^d.$$

Here the colors are represented by residues modulo $k$ and the terms from the body of the product are the differences between adjacent colors and encode transition to the next color by adding a value between $1$ and $k-1$ to the current color. (We are not adding zero because then the color would stay the same). Only the terms that are multiples of $k$ contribute to the count as this precisely represents a return to the first color of the cycle.

With $\zeta_p = \exp(2\pi i p/k)$ a root of unity the number of difference schemes is given by

$$\frac{1}{k} \sum_{p=0}^{k-1} f(\zeta_p)$$

but note that we are free to choose the first color so we get

$$\sum_{p=0}^{k-1} f(\zeta_p).$$

Distinguishing between $p$ zero which yields $$(k-1)^d$$ and non-zero ($k-1$ values) where $z + z^2 + z^3 + \cdots + z^{k-1} = -1$

we obtain the answer

$$\bbox[5px,border:2px solid #00A000]{ (k-1)^d + (k-1)\times (-1)^d.}$$

There is some Perl code as well.

#! /usr/bin/perl -w
#

MAIN : {
    my $mx = shift || 10;
    my $k = shift || 2;

    my @res = ($k);

    for(my $n=2; $n <= $mx; $n++){
        my %orbits;

        for(my $ind = 0; $ind < $k ** $n; $ind++){
            my ($pos, $idx, @d);

            for(($pos, $idx) = (0, $ind); 
                $pos < $n; $pos++){
                my $digit = $idx % $k;

                push @d, $digit;
                $idx = ($idx-$digit) / $k;
            }

            for($pos=0; $pos < $n; $pos++){
                last if $d[$pos] == $d[($pos+1) % $n];
            }

            if($pos == $n){
                my %orbit;
                for(my $shft = 0; $shft < $n; $shft++){
                    my $str =
                        join('-', 
                             @d[$shft..$n-1], @d[0..$shft-1]);
                    $orbit{$str} = 1;
                }

                my $orbstr = (sort(keys %orbit))[0];
                $orbits{$orbstr} = 1;
            }
        }

        push @res, scalar(keys %orbits);
    }

    print join(', ', @res);
    print "\n";

    1;
}

The Perl script will produce e.g. the sequence for $k=5$ starting at $n=2:$

$$5, 10, 20, 70, 204, 700, 2340, 8230, 29140, \ldots$$

which matches the output from the closed form and points us to OEIS A106367 where we see that we have the right values.