Black and white beads on a circle There are $n$ beads placed on a circle, $n\ge 3$. They are numbered in random order as viewed clockwise. Beads for which the number of the previous bead is less than the number of a next bead are painted in white color,and others - in black.

Two colourations that can be made equal by rotation are considered identical. How many different colourations can occur?

I've write a programm and for $n=3...11$ I've got answers $2 , 1 , 6 , 7 ,  18 , 25 , 58 , 93 , 186$
What follows  is not  an answer but  a conjecture and  some additional
material. We  start by working  with permutations. I assumed  that the
bit  pattern  /  black-white  pattern  at position  $q$  reflects  the
less-than  greater-than relation  at position  $q$ in  the permutation
(whether the  pair at $q$  and $q+1$ is  an ascent or a  descent, with
circular wrap-around).

I  wrote   a  Perl  program  to  investigate   these  necklaces  (Perl
aficionados are invited to verify  and improve this work, e.g. the bit
strings can be produced with pack/unpack). The program
iterates  over  all bit  patterns  and  attempts  to find  a  circular
permutation  that fits  the  pattern using  a backtracking  algorithm,
which I hope I've implemented correctly.

The program produced the following table:


&#36; time ./blg2.pl 12 2>/dev/null
3: 4 2/2
4: 6 4/2
5: 8 6/2
6: 14 12/2
7: 20 18/2
8: 36 34/2
9: 60 58/2
10: 108 106/2
11: 188 186/2
12: 352 350/2

real    7m9.188s
user    7m7.926s
sys     0m0.045s


This table shows the total number of circular colorations obtained and
indicates furthermore that for all  $n$ all possible bit patterns were
realized except two. The totals give the sequence

$$4,6,8,14,20,36,60,108,188,352,\ldots $$

which is  OEIS A00031 which  is simply the
substituted cycle index of the cyclic group
$$\left.Z(C_n)(A+B)\right|_{A=1,B=1},$$
and can be  taken as evidence that the program is  working since it is
the  correct  answer  (total  number  of circular  patterns  with  two
colors.)

Observe that the exact values which are
$$2,4,6,12,18,34,58,106,186,350,\ldots $$
also have an OEIS entry namely
OEIS A052823
which  reflects  the underlying  necklace  combinatorics  but not  the
permutation aspect.


The   program  can  also   output  permutations   that  fit   a  given
pattern. Here are the examples for $n=3,4,5$ and $n=6$:


&#36; time ./blg2.pl 5
100 3-1-2
110 3-2-1
111 FAIL
000 FAIL
3: 4 2/2
1010 3-1-4-2
1000 4-1-2-3
1110 4-3-2-1
1100 4-2-1-3
1111 FAIL
0000 FAIL
4: 6 4/2
11100 5-3-2-1-4
11110 5-4-3-2-1
10100 4-1-5-2-3
11010 4-2-1-5-3
11000 5-2-1-3-4
10000 5-1-2-3-4
00000 FAIL
11111 FAIL
5: 8 6/2
100000 6-1-2-3-4-5
111000 6-3-2-1-4-5
101000 5-1-6-2-3-4
110100 5-2-1-6-3-4
100100 4-1-5-6-2-3
111110 6-5-4-3-2-1
110000 6-2-1-3-4-5
110110 4-2-1-6-5-3
111100 6-4-3-2-1-5
101010 3-1-5-4-6-2
111010 5-3-2-1-6-4
101100 4-1-6-5-2-3
111111 FAIL
000000 FAIL
6: 14 12/2


Studying the  examples we immediately  have a conjecture,  namely that
all black-white  patterns can be  realized except the  monochrome ones
(this is obvious  as the circularity makes it  impossible to have just
one run in a circular permutation since not all $n$ elements can be to
the left  of a larger/smaller  element).  The conjectured  formula is
thus

$$-2 + \left.Z(C_n)(A+B)\right|_{A=1,B=1}.$$
This is
$$-2 + 
\left.\frac{1}{n} \sum_{d|n} \varphi(d) (A^d+B^d)^{n/d}\right|
_{A=1, B=1}.$$

This gives the following 
CONJECTURE:
$$\large{\color{#0A0}{
-2 + \frac{1}{n} \sum_{d|n} \varphi(d) 2^{n/d}}}.$$

Concluding  remark.  With  the  amount  of data  and  context  now
available it should not be difficult to produce a combinatorial proof,
which I suspect will turn out to be simple.

This is the Perl code that was used to compute the above data.


#! /usr/bin/perl -w
#

sub search {
    my(&#36;n, &#36;bits, &#36;q, &#36;avail, &#36;key, &#36;seen, &#36;sofar) = @_;

    if(&#36;q==&#36;n){
        if((&#36;bits-&gt;[&#36;n-1] == 0 &&
            &#36;sofar-&gt;[&#36;n-1] &lt; &#36;sofar-&gt;[0]) ||
           (&#36;bits-&gt;[&#36;n-1] == 1 &&
            &#36;sofar-&gt;[&#36;n-1] &gt; &#36;sofar-&gt;[0])){
            &#36;seen-&gt;{&#36;key} = join('-', @&#36;sofar);
        }

        return;
    }

    my &#36;pos = 0;
    while(!exists(&#36;seen-&gt;{&#36;key}) && &#36;pos&lt;&#36;n-&#36;q){
        my &#36;nxttry = &#36;avail-&gt;[&#36;pos];

        if(&#36;q==0 || 
           ((&#36;bits-&gt;[&#36;q-1] == 0 && 
             &#36;sofar-&gt;[&#36;q-1] &lt; &#36;nxttry) ||
            (&#36;bits-&gt;[&#36;q-1] == 1 && 
             &#36;sofar-&gt;[&#36;q-1] &gt; &#36;nxttry))){
            push @&#36;sofar, &#36;nxttry;
            splice @&#36;avail, &#36;pos, 1;

            search(&#36;n, &#36;bits, &#36;q+1, 
                   &#36;avail, &#36;key, &#36;seen, &#36;sofar);

            splice @&#36;avail, &#36;pos, 0, &#36;nxttry;
            pop @&#36;sofar;
        }

        &#36;pos++;
    }
}

 MAIN: {
     my &#36;mx = shift || 6; 

     for(my &#36;n=3; &#36;n&lt;=&#36;mx; &#36;n++){
         my &#36;seen = {};  my &#36;failed = {};

         for(my &#36;ind=0; &#36;ind&lt;2**&#36;n; &#36;ind++){
             my &#36;bits = [];

             for(my (&#36;pos, &#36;indx)=(0, &#36;ind); 
                 &#36;pos&lt;&#36;n; &#36;pos++){
                 push @&#36;bits, (&#36;indx %2);
                 &#36;indx = (&#36;indx-&#36;bits-&gt;[-1])/2;
             }

             my &#36;rot;
             for(&#36;rot=0; &#36;rot&lt;&#36;n; &#36;rot++){
                 my @rotbits =
                     (@&#36;bits[&#36;rot..(&#36;n-1)],
                      @&#36;bits[0..(&#36;rot-1)]);
                 my &#36;rotkey = join('', @rotbits);

                 last if
                     exists(&#36;seen-&gt;{&#36;rotkey}) ||
                     exists(&#36;failed-&gt;{&#36;rotkey});
             }

             if(&#36;rot==&#36;n){
                 my &#36;key = join('', @&#36;bits);
                 search(&#36;n, &#36;bits, 0, [1..&#36;n], &#36;key, &#36;seen, []);

                 &#36;failed-&gt;{&#36;key} = 'FAIL' 
                     if !exists(&#36;seen-&gt;{&#36;key});
             }
         }

         my &#36;total = scalar(keys %&#36;seen) + scalar(keys %&#36;failed);

         foreach my &#36;pat (keys %&#36;seen){
             print STDERR "&#36;pat " . &#36;seen-&gt;{&#36;pat} . "\n";
         }
         foreach my &#36;pat (keys %&#36;failed){
             print STDERR "&#36;pat " . &#36;failed-&gt;{&#36;pat} . "\n";
         }

         print "&#36;n: &#36;total " . scalar(keys(%&#36;seen)) . "/" .
             scalar(keys(%&#36;failed)) . "\n";
     }
}


There is a radically simplified  version of the above program which is
not  as fast,  however. Instead  of  iterating over  bit patterns  and
backtracking  to  find a  matching  permutation  we  iterate over  all
permutations and collect the  bit patterns / black-white patterns that
appear. The slow-down in the speed  when solving the case of $n=10$ is
on the order of a factor  of $60$. This code uses the factorial number
system to iterate over permutations  and never allocates more than one
permutation at a time.


#! /usr/bin/perl -w
#

sub fact { 
    my (&#36;n) = @_;

    return 1 if (&#36;n == 0 || &#36;n == 1);
    return &#36;n*fact(&#36;n-1);
}

 MAIN: {
     my &#36;mx = shift || 6; 

     for(my &#36;n=3; &#36;n&lt;=&#36;mx; &#36;n++){
         my &#36;seen = {};

         for(my &#36;ind=0; &#36;ind&lt;fact(&#36;n); &#36;ind++){
             my @perm = (1..&#36;n);

             for(my (&#36;pos, &#36;indx) = (&#36;n-1, &#36;ind);
                 &#36;pos &gt; 0; &#36;pos--){
                 my &#36;targ = &#36;indx % (&#36;pos+1);
                 &#36;indx = (&#36;indx-&#36;targ)/(&#36;pos+1);

                 my &#36;tmp = &#36;perm[&#36;pos];
                 &#36;perm[&#36;pos] = &#36;perm[&#36;targ];
                 &#36;perm[&#36;targ] = &#36;tmp;
             }

             my @bits = ();

             for(my &#36;pos=0; &#36;pos&lt;&#36;n-1; &#36;pos++){
                 my &#36;bit = 
                     (&#36;perm[&#36;pos] &lt; &#36;perm[&#36;pos+1] ? 1 : 0);
                 push @bits, &#36;bit;
             }
             push @bits, (&#36;perm[&#36;n-1] &lt; &#36;perm[0] ? 1 : 0);

             my &#36;rot;
             for(&#36;rot=0; &#36;rot&lt;&#36;n; &#36;rot++){
                 my @rotbits =
                     (@bits[&#36;rot..(&#36;n-1)],
                      @bits[0..(&#36;rot-1)]);
                 my &#36;rotkey = join('', @rotbits);

                 last if exists(&#36;seen-&gt;{&#36;rotkey});
             }

             if(&#36;rot==&#36;n){
                 my &#36;key = join('', @bits);
                 &#36;seen-&gt;{&#36;key} = join('-', @perm);
             }
         }

         foreach my &#36;pat (keys %&#36;seen){
             print STDERR "&#36;pat " . &#36;seen-&gt;{&#36;pat} . "\n";
         }

         print "&#36;n: " . scalar(keys(%&#36;seen)) . "\n";
     }
}
Let $a_n$ be the number of configurations for this problem
and let $b_n$ be the number of two-colored necklaces with $n$ beads (no flips allowed).
It is well-known that $b_n=\frac 1n\sum_{d\mid n}\phi(d)2^\frac nd$ (this is OEIS A000031).

Computer runs suggest that for odd $n$ all these patterns also occur for this problem,
except the two monochromatic ones, so $a_n=b_n-2$.

They also suggest that for even $n$ all patterns occur except the ones where one color occurs every second spot.
In this case the number of necklaces where black occurs every second spot is $b_{\frac n2}$.
We get the same number for the patterns where white occurs every second spot,
and then we have double counted the one pattern where black and white alternate all around the necklace,
so we get $a_n=b_n-2b_{\frac n2}+1$.