Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
What have you tried? How about doing the problem for small values of $n$? –  Calvin Lin Oct 16 '13 at 23:35

1 Answer 1

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;
}
share|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

 
discard

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.