Interruptor de tirón de la secuencia sin repeticiones

Question

Bueno, tiene N interruptores. Son todos fuera. Usted puede girar un interruptor en un momento. Usted debe visitar cada posible estado de los interruptores de ser volteado sin repetir ningún estado. Al final, usted debe ser capaz de volver a la original-off estado con más tirón. Cuántas maneras hay de hacer esto? (Bonus: Ignorando la regla final que usted debe ser capaz de volver al estado original en un flip, cómo muchas otras maneras existen para visitar todos los estados?)

Ejemplos:

Para 2 interruptores, esto es trivial:

  00
10  01
  11

Usted puede ir alrededor del círculo en cualquier dirección, para un total de 2 posibles caminos. No hay manera de ignorar la regla final con 2 interruptores.

Para 3 interruptores, hay más posibilidades:

    000          000          000          000          000          000
 100   001    010   001    100   010    001   010    010   100    001   100
101     011  011     101  110     011  011     110  110     101  101     110
 111   010    111   100    111   001    111   100    111   001    111   010
    110          110          101          101          011          011

Usted puede ir alrededor del círculo en cualquier dirección, para un total de 12. Además, usted puede hacer cualquiera de los siguientes:

000 001 011 010 110 100 101 111
000 001 101 100 110 010 011 111
000 010 011 001 101 100 110 111
000 010 110 100 101 001 011 111
000 100 101 001 011 010 110 111
000 100 110 010 011 001 101 111

Estos 6 pasos van a visitar cada estado posible, pero al final en 111, por lo que no se puede hacer en un ciclo, ya que se llevará a 3 lanzamientos para volver a 000.

Se puede probar que no existen otros caminos que visita todos los estados, sin repeticiones. Ya hay 8 posibles estados, tomará de 7 lanzamientos para llegar a todos ellos, que es un número impar, por lo que debe haber un número impar de 1's en la final de la secuencia. Estos 6 círculos y 6 recta secuencias de haber agotado todos los posibles caminos que no se repita.

La pregunta es: ¿cuántos de esos ciclos existen para N interruptores? He encontrado esto a mano, pero debe haber alguna fórmula que de cuenta de todas las posibilidades en una forma menos tediosa manera. (Y no esta secuencia existen en la OEIS? Probablemente debería.)

Answer 1

El número de ciclos Hamiltonianos en el $n$-dimensional del cubo es A003042 en OEIS. El número de caminos Hamiltonianos es A091299.

Editar:

El número de caminos Hamiltonianos a partir de un punto fijo (por ejemplo, todos off) es A003043.

Answer 2

Lo que he descrito es conocido como un "código Gray," los cuales han sido estudiados ampliamente. No tengo una respuesta completa a su pregunta, pero Liposvski en Introducción a los Microcontroladores ofrece lo siguiente:

Hay un gran número de Gris de los códigos. Supongamos $G(i)$ es una función que genera el código Gray de un número binario $i$. Luego de una $n$-bit código, por cualquier $j$, $G((i+j)\mod 2n)$ es también una $n$-bit del código Gray de $i$.