Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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(checkdiff($n, $seq->[0], $seq->[-1])){
          # print join(', ', @$seq);
          # print "\n";


    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;


    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;
share|cite|improve this answer
+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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.