necklace of numbers with bounded distance

Starting from the numbers 1-2-3-4-5-6-7-8-9-10-11-12 arrange them in a circle so the difference |x-y| between neighbors is 1 or 2.

If we are working mod 12 so that 12 = 0, how many possible arrangements are there?

-
What have you tried? How about doing the problem for small values of $n$? –  Calvin Lin Oct 16 '13 at 23:35

Perhaps I can help put this problem in context. I wrote a Perl program to compute the number of these arrangements for $n\ge 2$ and not just $n=12.$ This gave the following sequence.

$$1, 2, 6, 24, 32, 46, 58, 82, 112, 158, 220, 316, 450, 650, 938, 1364, 1982, 2892, 4220, 6170, 9022,\ldots$$

I then checked the OEIS and found this OEIS link. Apparently this problem reduces to an enumeration of hamiltonian circuits in certain circulant graphs by an obvious bijection. The OEIS entry contains a link to a paper where your problem is solved, so perhaps you can start by studying that. Considering the bibliography of the linked paper it looks like there is quite a bit of relevant literature on this subject.

This was the Perl program:

#! /usr/bin/perl

sub checkdiff {
my ($n,$a, $b) = @_; my$d = $a-$b;
$d +=$n if $d<0; return 1 if$d==1 || $d==2 ||$d==$n-2 ||$d==$n-1; return 0; } sub compute { my ($n, $seq,$rest, $count) = @_; if(!scalar(@$rest)){
if(checkdiff($n,$seq->[0], $seq->[-1])){ # print join(', ', @$seq);
# print "\n";
count++;
}

return;
}

for(my $pos = 0;$pos<scalar(@$rest);$pos++){
my $el =$rest->[$pos]; if(checkdiff($n, $seq->[-1],$el)){
push @$seq,$el;
splice @$rest,$pos, 1;

compute($n,$seq, $rest,$count);

splice @$rest,$pos, 0, $el; pop @$seq;
}
}

}

MAIN: {
my $mx = shift || 5; die "MAX at least two please" if$mx<2;

for(my $n=2;$n<=$mx;$n++){
my $count = 0; compute($n, [0], [1..($n-1)], \$count);
print (($n==2 ? "" : ", ") .$count);
}
print "\n";

exit 0;
}

-
+1 you should mention that it doesn't agree in the first few values. –  Calvin Lin Oct 16 '13 at 23:48
Thank you. This disagreement is mentioned in the description near the top. –  Marko Riedel Oct 16 '13 at 23:51