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.

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.

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 by S. Plouffe in his 1992 dissertation.]

Sequence in context: A111160 A071378 A053192 this_sequence A057819 A129196 A119574

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