login
This site is supported by donations to The OEIS Foundation.

 

Logo


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<<n - (1-(-1)^n)*(2^n-2))/4 \\ Charles R Greathouse IV, Jun 03 2015

CROSSREFS

Cf. A018215 (bisection).

Sequence in context: A270634 A324020 A265645 * A322780 A151271 A149115

Adjacent sequences:  A005982 A005983 A005984 * A005986 A005987 A005988

KEYWORD

nonn,nice,easy

AUTHOR

Colin Mallows

EXTENSIONS

Revised by Colin Mallows, Jun 13 2005

More terms from Erich Friedman, Aug 08 2005

STATUS

approved

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.

License Agreements, Terms of Use, Privacy Policy. .

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