A005985 Length of longest trail (i.e., path with all distinct edges) on the edges of an n-cube.

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, 7516192769, 16106127360, 32212254721

Offset: 0

Author

Colin Mallows

Keywords

• nonn
• nice
• easy

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

Examples

			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).
		

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).

Crossrefs

Cf. A018215 (bisection).

Programs

Magma

[(2*n*2^n-(1-(-1)^n)*(2^n-2))/4 : n in [0..50]]; // Wesley Ivan Hurt, May 31 2015

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 *)

PARI

a(n)=(2*n<Charles R Greathouse IV, Jun 03 2015

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

Extensions

Revised by Colin Mallows, Jun 13 2005

More terms from Erich Friedman, Aug 08 2005