|
| |
|
|
A005985
|
|
Length of longest walk on edges of n-cube.
(Formerly M3366)
|
|
2
| |
|
|
0, 1, 4, 9, 32, 65, 192, 385, 1024, 2049, 5120, 10241, 24576, 49153, 114688, 229377, 524288, 1048577, 2359296, 4718593, 10485760, 20971521, 46137344, 92274689, 201326592, 402653185, 872415232, 1744830465, 3758096384
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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.
|
|
|
REFERENCES
| N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| 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.
|
|
|
EXAMPLE
| 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.
|
|
|
MAPLE
| 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.]
|
|
|
CROSSREFS
| Cf. A018215 (bisection) - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 21 2009
Sequence in context: A201689 A071378 A053192 * A151271 A149115 A149116
Adjacent sequences: A005982 A005983 A005984 * A005986 A005987 A005988
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| C. L. Mallows (colinm(AT)research.avayalabs.com); revised Jun 13 2005
|
|
|
EXTENSIONS
| More terms from Erich Friedman (efriedma(AT)stetson.edu), Aug 08 2005
|
| |
|
|
