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.
Suppose n is odd. Delete all but one edge between {0,1}^(n-1) x {0} = A and {0,1}^(n-1) x {1} = B. Starting at the vertex v of A that has an edge to B, do an Euler tour of A coming back to v, then cross over to B and do an Euler tour of B.
This gives you a longest possible trail. - Robert Israel, Jun 02 2015
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
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (2,5,-10,-4,8).
FORMULA
G.f.: -x*(1 + 2*x - 4*x^2 + 4*x^3) / ( (x - 1)*(2*x + 1)*(1 + x)*(-1 + 2*x)^2 ). - Simon Plouffe in his 1992 dissertation.
a(n) = (2*n*2^n-(1-(-1)^n)*(2^n-2))/4. - Giovanni Resta, May 31 2015
a(n) = 2*a(n-1)+5*a(n-2)-10*a(n-3)-4*a(n-4)+8*a(n-5), n>5. - Wesley Ivan Hurt, May 31 2015
EXAMPLE
For n=3, let the vertices be labeled with Cartesian coordinates (0,0,0), (0,0,1), ..., (1,1,1). An example of a maximal path (of length 9) visits the ten vertices: (0,0,0), (1,0,0), (1,0,1), (1,1,1), (0,1,1), (0,0,1), (0,0,0), (0,1,0), (1,1,0), (1,0,0).
MAPLE
A005985:=n->(2*n*2^n-(1-(-1)^n)*(2^n-2))/4: seq(A005985(n), n=0..50); # Wesley Ivan Hurt, May 31 2015
MATHEMATICA
Table[(2*n*2^n - (1 - (-1)^n)(2^n - 2))/4, {n, 0, 20}] (* Giovanni Resta, May 31 2015 *)
LinearRecurrence[{2, 5, -10, -4, 8}, {0, 1, 4, 9, 32}, 40] (* Harvey P. Dale, Jun 11 2015 *)
PROG
(Magma) [(2*n*2^n-(1-(-1)^n)*(2^n-2))/4 : n in [0..50]]; // Wesley Ivan Hurt, May 31 2015
(PARI) a(n)=(2*n<<n - (1-(-1)^n)*(2^n-2))/4 \\ Charles R Greathouse IV, Jun 03 2015
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
Revised by Colin Mallows, Jun 13 2005
More terms from Erich Friedman, Aug 08 2005
STATUS
approved