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

1, 1, 3, 238, 48828036

Offset

1,3

Links

Table of n, a(n) for n=1..5.

Luc Rousseau, A C program that computes a(n)

Eric Weisstein's World of Mathematics, Hamiltonian Path

Eric Weisstein's World of Mathematics, Hypercube Graph

Formula

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

Example

For n=2, the two Hamiltonian paths of the square that start at (0,0), i.e.,
  (0,0) -->-- (1,0)               (0,0)       (1,0)
                |                   |           |
                V        and        V           ^
                |                   |           |
  (0,1) --<-- (1,1)               (0,1) -->-- (1,1),
only account for one, as one is obtained from the other by the x <-> y permutation; so a(2) = 1.

Prog

(C) See link.

Crossrefs

Cf. A003043, A091299.

Sequence in context: A278318 A103062 A157723 * A142730 A264549 A024044

Adjacent sequences: A342628 A342629 A342630 * A342632 A342633 A342634

Keyword

nonn,hard,more

Author

Luc Rousseau, May 24 2021

Status

approved