0,3

Walk along edges of n-cube without walking along any edge twice; a(n) = number of edges in longest path.

For even n we can traverse all the edges, so a(n) = number of edges = n*2^(n-1). For n odd, every vertex has odd degree, so we need (# vertices)/2 = 2^(n-1) separate paths to cover them all; we will not be able to traverse more than n*2^(n-1) - (2^(n-1)-1) edges before Euler blocks the way. There is a recursive construction (temporarily lost) which achieves this bound.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..300

S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.

S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.

n=3: let the vertices be labeled with Cartesian coordinates 000, 001, ..., 111. An example of a maximal path (of length 9) visits the ten vertices 000, 100, 101, 111, 011, 001, 000, 010, 110, 100.

A005985:=-(1+2*z-4*z**2+4*z**3)/(z-1)/(2*z+1)/(z+1)/(-1+2*z)**2; [Conjectured (correctly) by S. Plouffe in his 1992 dissertation, apart from the initial zero.]

Cf. A018215 (bisection) - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 21 2009

Sequence in context: A111160 A071378 A053192 this_sequence A151271 A149115 A149116

Adjacent sequences: A005982 A005983 A005984 this_sequence A005986 A005987 A005988

nonn,nice

C. L. Mallows (colinm(AT)research.avayalabs.com); revised Jun 13 2005

More terms from Erich Friedman (efriedma(AT)stetson.edu), Aug 08 2005