Black and white beads on a circle
Solution 1:
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:
$ 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$:
$ 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($n, $bits, $q, $avail, $key, $seen, $sofar) = @_;
if($q==$n){
if(($bits->[$n-1] == 0 &&
$sofar->[$n-1] < $sofar->[0]) ||
($bits->[$n-1] == 1 &&
$sofar->[$n-1] > $sofar->[0])){
$seen->{$key} = join('-', @$sofar);
}
return;
}
my $pos = 0;
while(!exists($seen->{$key}) && $pos<$n-$q){
my $nxttry = $avail->[$pos];
if($q==0 ||
(($bits->[$q-1] == 0 &&
$sofar->[$q-1] < $nxttry) ||
($bits->[$q-1] == 1 &&
$sofar->[$q-1] > $nxttry))){
push @$sofar, $nxttry;
splice @$avail, $pos, 1;
search($n, $bits, $q+1,
$avail, $key, $seen, $sofar);
splice @$avail, $pos, 0, $nxttry;
pop @$sofar;
}
$pos++;
}
}
MAIN: {
my $mx = shift || 6;
for(my $n=3; $n<=$mx; $n++){
my $seen = {}; my $failed = {};
for(my $ind=0; $ind<2**$n; $ind++){
my $bits = [];
for(my ($pos, $indx)=(0, $ind);
$pos<$n; $pos++){
push @$bits, ($indx %2);
$indx = ($indx-$bits->[-1])/2;
}
my $rot;
for($rot=0; $rot<$n; $rot++){
my @rotbits =
(@$bits[$rot..($n-1)],
@$bits[0..($rot-1)]);
my $rotkey = join('', @rotbits);
last if
exists($seen->{$rotkey}) ||
exists($failed->{$rotkey});
}
if($rot==$n){
my $key = join('', @$bits);
search($n, $bits, 0, [1..$n], $key, $seen, []);
$failed->{$key} = 'FAIL'
if !exists($seen->{$key});
}
}
my $total = scalar(keys %$seen) + scalar(keys %$failed);
foreach my $pat (keys %$seen){
print STDERR "$pat " . $seen->{$pat} . "\n";
}
foreach my $pat (keys %$failed){
print STDERR "$pat " . $failed->{$pat} . "\n";
}
print "$n: $total " . scalar(keys(%$seen)) . "/" .
scalar(keys(%$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 ($n) = @_;
return 1 if ($n == 0 || $n == 1);
return $n*fact($n-1);
}
MAIN: {
my $mx = shift || 6;
for(my $n=3; $n<=$mx; $n++){
my $seen = {};
for(my $ind=0; $ind<fact($n); $ind++){
my @perm = (1..$n);
for(my ($pos, $indx) = ($n-1, $ind);
$pos > 0; $pos--){
my $targ = $indx % ($pos+1);
$indx = ($indx-$targ)/($pos+1);
my $tmp = $perm[$pos];
$perm[$pos] = $perm[$targ];
$perm[$targ] = $tmp;
}
my @bits = ();
for(my $pos=0; $pos<$n-1; $pos++){
my $bit =
($perm[$pos] < $perm[$pos+1] ? 1 : 0);
push @bits, $bit;
}
push @bits, ($perm[$n-1] < $perm[0] ? 1 : 0);
my $rot;
for($rot=0; $rot<$n; $rot++){
my @rotbits =
(@bits[$rot..($n-1)],
@bits[0..($rot-1)]);
my $rotkey = join('', @rotbits);
last if exists($seen->{$rotkey});
}
if($rot==$n){
my $key = join('', @bits);
$seen->{$key} = join('-', @perm);
}
}
foreach my $pat (keys %$seen){
print STDERR "$pat " . $seen->{$pat} . "\n";
}
print "$n: " . scalar(keys(%$seen)) . "\n";
}
}
Solution 2:
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$.
For the proof of these observations we look at the cases of even $n$ and odd $n$ separately.
First we prove the case for even $n$. Note that in this case the odd beads and the even beads form two disjoint circular sequences. The colors on the odd beads prescribe the ordering on the even beads (and v.v.), but there is a huge amount of freedom in assigning the values, and what is more important: the value assignments on the subsequences are independent: any value assignment on the odd beads consistent with the colors on the even beads can be combined with any value assignment on the even beads that is consistent with the colors on the odd beads (as long as no values are duplicated).
We first show that for any non-monochromatic color sequence on the odd beads we can find a value assignment for the even beads that is consistent with it. Let $n=2t$ and let $p_1,\ldots,p_t$ be the odd beads and $q_1,\ldots,q_t$ the even beads, so that the complete necklace is $p_1,q_1,p_2,q_2,\ldots$.
Because the color sequence is not monochromatic and because we have cyclic arrangements we may assume that $p_1$ is black and $p_2$ is white. We give $q_1$ the value 1. Now assume we have assigned a value to $q_i$. If $p_{i+1}$ is white, we assign value $q_i+n$ to $q_{i+1}$, otherwise we assign value $q_i-1$. Because we have less than $n$ values to assign this we end up in $q_t$ having a larger value than $q_1$, which shows that indeed all value assignments on the even beads are consistent with the colors on the odd beads.
We can similarly find a value assignment for the odd beads consistent with the colors on the even beads (just make sure to use a different range of numbers).
Combining these value assignments and 'flattening' the values to make the valueset equal to $1,\ldots,n$ finishes the proof that for even $n$ any color sequence that is not monochromatic on the odd beads or the even beads is realizable.
Now we turn to the case that $n$ is odd. In this case we take $n=2t-1$ and we consider the beads to be numbered $p_1,p_{t+2},p_2,p_{t+3},\ldots,p_n,p_{t+1}$. Since we have excluded monochromatic patterns we may again assume that $p_1$ is black and $p_2$ is white. We use the same procedure. We start with value 1 on $p_{t+1}$ and assuming we have assigned a value to $p_i$ we assign value $p_i+n$ to $p_{i+2}$ if the bead after $p_i$ is white and value $p_i-1$ if the bead after $p_i$ is black. This will eventually assign a value to $p_n$ that is larger than 1, so again we have managed a value assignment consistent with the colors.
Btw, the values found by computer simulation were (starting with $n=3$) 2, 1, 6, 7, 18, 25, 58, 93, 186, 325 which coincides with the given formulas and with the values reported in the question.
Solution 3:
The facts observed in the answer by Leen Droogendijk can easily be explained. I recall that it says that for odd$~n$ all colour patters except the monochromatic (all-white or all-black) ones can be obtained, and for even $n$ all patters except those where either the odd-position or the even-position subsequences are monochromatic (and possibly both simultaneously).
Since one is not counting the actual numberings of the beads, let us start with a given colouring and try to see if the conditions it gives on the associated permutation (which are a collection of inequalities among pairs of permutation entries) are contradictory (in which case the colouring is rejected) or not. It is easy to see that a collection of inequalities is contradictory if it contains any oriented cycles, and consistent otherwise. (Formally, in the latter case the inequalities define by transitivity a partial ordering among the positions of the entries, and partial orderings can always be extended to a total ordering; this prescribes a permutation.)
Now starting at the first bead, write down the colour of every other bead (so starting with positions $1$, $3$, $5$,...) wrapping back to the beginning of the necklace at the end, and continuing until bead $1$ is encountered again. If $n$ is odd this happens when all beads have been seen (and two tours of the necklace are completed) while if $n$ is even it happens after the first tour, after which all odd-position beads have been seen. In the latter case similarly make a separate tour for the even-position beads. So we have one or two cyclic chains of colours (according as $n$ is odd or even), and what we wish to show is that the colouring is contradictory if and only if at least one of those chains is monotonic.
Between each pair of successive colours (in cyclic order) of one chain we can place the permutation entry (position) whose value is involved in the both inequalities for those colours. (For instance if the first chain starts BW... then between the B and the W is placed permutation entry $p_2$, which is involved in the inequality $p_n>p_2$ for the black bead coming from position$~1$ and in the inequality $p_2<p_4$ for the white bead coming from position$~3$.) Thus the permutation entries are arranged in one or two cyclic chains linked by inequalities, and all required inequalities are thus taken into account. As observed above the inequalities are contradictory if they are all of the same kind (all "$<$" or all "$>$"; either gives an oriented cycle), and else non-contradictory.
Solution 4:
In response to the clarification / explanation in the comments to my other post I am sending a modified version of my initial program to account for the fact that the bit at position $q$ reflects the ordering of the beads at position $q-1$ and $q+1$ with circular wrap-around.
The result is the following sequence which I could not find in the OEIS.
$ time ./blg-nb.pl 11 2>/dev/null 2 1 6 7 18 25 58 93 186 real 2m48.880s user 2m42.802s sys 0m0.062s
Here it is for easy inspection once more: $$2,1,6,7,18,25,58,93,186,\ldots$$
It is remarkable that for odd $n$ these values agree with the case where the bit at $q$ indicates the ordering of positions $q$ and $q+1.$
Some examples that one can check with pen-and-paper and thereby verify the correctness of the program:
$ time ./blg-nb.pl 7 100 2-1-3 110 3-1-2 2 1100 2-3-1-4 1 11100 3-4-1-2-5 11110 5-2-4-1-3 10100 2-3-4-1-5 11010 5-1-3-4-2 11000 4-1-2-3-5 10000 3-1-4-2-5 6 100100 2-3-4-5-1-6 110000 3-4-1-5-2-6 110110 3-4-2-6-1-5 111100 3-5-2-4-1-6 101100 2-4-5-3-1-6 111000 3-5-1-4-2-6 110100 3-4-2-5-1-6 7 1011000 3-4-6-1-5-2-7 1011100 2-4-6-3-5-1-7 1010100 2-4-5-3-6-1-7 1010000 3-4-5-1-6-2-7 1111100 4-6-2-5-1-3-7 1101000 6-1-3-4-2-5-7 1111110 7-3-6-2-5-1-4 1100100 3-4-1-5-6-2-7 1000000 4-1-5-2-6-3-7 1101010 7-1-4-5-3-6-2 1111000 5-6-2-3-1-4-7 1101100 4-5-2-6-1-3-7 1111010 7-2-5-1-4-6-3 1001000 4-1-6-2-5-3-7 1110000 4-5-1-2-6-3-7 1110100 3-5-1-4-6-2-7 1110110 3-5-1-4-7-2-6 1100000 5-1-2-3-6-4-7 18 real 0m0.272s user 0m0.109s sys 0m0.077s
This is the modified version of the program.
#! /usr/bin/perl -w
#
sub search {
my($n, $bits, $q, $avail, $key, $seen, $sofar) = @_;
if($q==$n){
my $admit = 0;
if(($bits->[$n-1] == 0 &&
$sofar->[$n-2] < $sofar->[0]) ||
($bits->[$n-1] == 1 &&
$sofar->[$n-2] > $sofar->[0])){
$admit++;
}
if(($bits->[0] == 0 &&
$sofar->[$n-1] < $sofar->[1]) ||
($bits->[0] == 1 &&
$sofar->[$n-1] > $sofar->[1])){
$admit++;
}
$seen->{$key} = join('-', @$sofar)
if $admit == 2;
return;
}
my $pos = 0;
while(!exists($seen->{$key}) && $pos<$n-$q){
my $nxttry = $avail->[$pos];
if($q < 2 ||
(($bits->[$q-1] == 0 &&
$sofar->[$q-2] < $nxttry) ||
($bits->[$q-1] == 1 &&
$sofar->[$q-2] > $nxttry))){
splice @$avail, $pos, 1;
$sofar->[$q] = $nxttry;
search($n, $bits, $q+1,
$avail, $key, $seen, $sofar);
$sofar->[$q] = -1;
splice @$avail, $pos, 0, $nxttry;
}
$pos++;
}
}
MAIN: {
my $mx = shift || 6;
for(my $n=3; $n<=$mx; $n++){
my $seen = {};
for(my $ind=0; $ind<2**$n; $ind++){
my $bits = [];
for(my ($pos, $indx)=(0, $ind);
$pos<$n; $pos++){
push @$bits, ($indx %2);
$indx = ($indx-$bits->[-1])/2;
}
my $rot;
for($rot=0; $rot<$n; $rot++){
my @rotbits =
(@$bits[$rot..($n-1)],
@$bits[0..($rot-1)]);
last if
exists($seen->{join('', @rotbits)});
}
if($rot==$n){
my $key = join('', @$bits);
my $sofar = [(-1) x $n];
search($n, $bits, 0, [1..$n], $key,
$seen, $sofar);
}
}
foreach my $pat (keys %$seen){
print STDERR "$pat " . $seen->{$pat} . "\n";
}
print scalar(keys %$seen) . "\n";
}
}
Addendum. What we see in the above is the problem of iterating in $\mathcal{O}(n)$ space over all unique necklaces of $n$ beads with $k$ colors without checking all $k^n$ assignments. Commentary and algorithms for this would be most welcome.
Addendum II. By removing list splicing from the backtracking code I was able to compute the next value, which is $325.$ I might post this if I manage to compute a second additional value.
Addendum III Oct 19 2014. The speed-up gained by not using list splicing and some other optimizations among them not searching necklaces that have already been seen not to admit a matching permutation made it possible to calculate two additional values in a reasonable amout of time. Here is the list.
Good to see the problem has been solved, maybe the data from the Perl program were useful here.
$ time ./blg-nb4.pl 14 2>/dev/null 2 1 6 7 18 25 58 93 186 325 630 1143 real 148m49.703s user 133m49.043s sys 0m4.710s
This is the improved program.
#! /usr/bin/perl -w
#
sub search {
my($n, $bits, $q, $avail, $key, $seen, $sofar) = @_;
if($q==$n){
my $admit = 0;
if(($bits->[$n-1] == 0 &&
$sofar->[$n-2] < $sofar->[0]) ||
($bits->[$n-1] == 1 &&
$sofar->[$n-2] > $sofar->[0])){
$admit++;
}
if(($bits->[0] == 0 &&
$sofar->[$n-1] < $sofar->[1]) ||
($bits->[0] == 1 &&
$sofar->[$n-1] > $sofar->[1])){
$admit++;
}
$seen->{$key} = join('-', @$sofar)
if $admit == 2;
return;
}
my @possibles = keys %$avail;
my $pos = 0;
while(!exists($seen->{$key}) && $pos<$n-$q){
my $nxttry = $possibles[$pos];
if($q < 2 ||
(($bits->[$q-1] == 0 &&
$sofar->[$q-2] < $nxttry) ||
($bits->[$q-1] == 1 &&
$sofar->[$q-2] > $nxttry))){
delete $avail->{$nxttry};
$sofar->[$q] = $nxttry;
search($n, $bits, $q+1,
$avail, $key, $seen, $sofar);
$sofar->[$q] = -1;
$avail->{$nxttry} = 1;
}
$pos++;
}
}
MAIN: {
my $mx = shift || 6;
for(my $n=3; $n<=$mx; $n++){
my $seen = {}; my $failed = {};
my $bits = [(0) x $n];
for(my $ind=0; $ind<2**$n; $ind++){
my $rot;
for($rot=0; $rot<$n; $rot++){
my @rotbits =
(@$bits[$rot..($n-1)],
@$bits[0..($rot-1)]);
my $key = join('', @rotbits);
last if
exists($seen->{$key}) ||
exists($failed->{$key});
}
if($rot==$n){
my $key = join('', @$bits);
my $sofar = [(-1) x $n];
my %initavail;
@initavail{(1..$n)} = (1 x $n);
search($n, $bits, 0, \%initavail, $key,
$seen, $sofar);
$failed->{$key} = 'FAIL'
if !exists($seen->{$key});
}
my $pos = 0;
while($pos<$n && $bits->[$pos] == 1){
$bits->[$pos++] = 0;
}
$bits->[$pos] = 1;
}
foreach my $pat (keys %$seen){
print STDERR "$pat " . $seen->{$pat} . "\n";
}
print scalar(keys %$seen) . "\n";
}
}