collar de números con distancia limitada

Question

A partir de los números arreglar en un círculo así que la diferencia entre los vecinos es 1 o 2.

Si estamos trabajando mod 12 para que `` , ¿cuántos arreglos posibles existen?

Answer 1

Tal vez me puede ayudar a poner este problema en su contexto. Escribí un programa Perl para calcular el número de estos acuerdos para $n\ge 2$ y no sólo a $n=12.$ Esto le dio a la siguiente secuencia.

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

Luego comprueba la OEIS y encontré este OEIS enlace. Al parecer, este problema se reduce a una enumeración de los circuitos hamiltonianos en ciertos circulantes gráficas por una evidente bijection. La OEIS entrada contiene un enlace a un documento donde se solucionó su problema, así que tal vez usted puede comenzar por estudiar. Teniendo en cuenta la bibliografía de las páginas de papel parece que hay un poco de la literatura relevante sobre este tema.

Este fue el programa Perl:

#! /usr/bin/perl

sub checkdiff {
 my ($n, $a, $b) = @_;

 mi $d = $a-$b;
 $d += $n si $d<0;

 devuelve 1 si $d==1 || $d==2 || $d==$n-2 || $d==$n-1;
 return 0;
}

sub calcular {
 my ($n, $seq, $resto, $count) = @_;

si(!escalar(@$rest)){
 si(checkdiff($n, $seq->[0], $seq->[-1])){
 # impresión join(', ', @$seq);
 # print "\n";
$$count++;
}

de retorno;
}

 para(mi $pos = 0; $pos<escalar(@$rest); $pos++){
 mi $el = $rest->[$pos];

 si(checkdiff($n, $seq->[-1], $el)){
 push @$seq, $el;
 empalme @$resto, $pos, 1;

 calcular($n, $seq, $resto, $count);

 empalme @$resto, $pos, 0, $el;
 pop @$seq;
}
}

}


PRINCIPAL: {
 mi $mx = shift || 5;

 mueren "MAX al menos dos por favor" si $mx<2;

 para(mi $n=2; $n<=$mx; $n++){
 mi $contador = 0;

 calcular($n, [0], [1..($n-1)], \$count);
 print (($n==2 ? "" : ", ") . $count);
}
 print "\n";

 exit 0;
}