Counting necklace with no adjacent beads are of the same color 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?  
 A: 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.
