A342631 - OEIS

%I #40 Feb 16 2025 08:34:01

%S 1,1,3,238,48828036

%N Number of Hamiltonian paths (or Gray codes) on n-cube with the origin as the starting node, up to a permutation of the coordinates.

%H Luc Rousseau, <a href="/A342631/a342631.c.txt">A C program that computes a(n)</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HamiltonianPath.html">Hamiltonian Path</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>

%F a(n) = A003043(n) / n!.

%e For n=2, the two Hamiltonian paths of the square that start at (0,0), i.e.,

%e   (0,0) -->-- (1,0)               (0,0)       (1,0)

%e                 |                   |           |

%e                 V        and        V           ^

%e                 |                   |           |

%e   (0,1) --<-- (1,1)               (0,1) -->-- (1,1),

%e only account for one, as one is obtained from the other by the x <-> y permutation; so a(2) = 1.

%o (C) /* See Rousseau link. */

%Y Cf. A003043, A091299.

%K nonn,hard,more

%O 1,3

%A _Luc Rousseau_, May 24 2021