This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A005985 Length of longest trail (i.e., path with all distinct edges) on the edges of an 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, 7516192769, 16106127360, 32212254721 (list; graph; refs; listen; history; text; 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. 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. Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 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<

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 17 13:33 EST 2019. Contains 329230 sequences. (Running on oeis4.)