cp's OEIS Frontend

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

%I A005985 M3366 #49 Sep 08 2022 08:44:34
%S A005985 0,1,4,9,32,65,192,385,1024,2049,5120,10241,24576,49153,114688,229377,
%T A005985 524288,1048577,2359296,4718593,10485760,20971521,46137344,92274689,
%U A005985 201326592,402653185,872415232,1744830465,3758096384,7516192769,16106127360,32212254721
%N A005985 Length of longest trail (i.e., path with all distinct edges) on the edges of an n-cube.
%C A005985 Walk along edges of n-cube without walking along any edge twice; a(n) = number of edges in longest path.
%C A005985 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.
%C A005985 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.
%C A005985 This gives you a longest possible trail. - _Robert Israel_, Jun 02 2015
%D A005985 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005985 T. D. Noe, <a href="/A005985/b005985.txt">Table of n, a(n) for n=0..300</a>
%H A005985 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A005985 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A005985 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,5,-10,-4,8).
%F A005985 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.
%F A005985 a(n) = (2*n*2^n-(1-(-1)^n)*(2^n-2))/4. - _Giovanni Resta_, May 31 2015
%F A005985 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
%e A005985 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).
%p A005985 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
%t A005985 Table[(2*n*2^n - (1 - (-1)^n)(2^n - 2))/4, {n, 0, 20}] (* _Giovanni Resta_, May 31 2015 *)
%t A005985 LinearRecurrence[{2,5,-10,-4,8},{0,1,4,9,32},40] (* _Harvey P. Dale_, Jun 11 2015 *)
%o A005985 (Magma) [(2*n*2^n-(1-(-1)^n)*(2^n-2))/4 : n in [0..50]]; // _Wesley Ivan Hurt_, May 31 2015
%o A005985 (PARI) a(n)=(2*n<<n - (1-(-1)^n)*(2^n-2))/4 \\ _Charles R Greathouse IV_, Jun 03 2015
%Y A005985 Cf. A018215 (bisection).
%K A005985 nonn,nice,easy
%O A005985 0,3
%A A005985 _Colin Mallows_
%E A005985 Revised by _Colin Mallows_, Jun 13 2005
%E A005985 More terms from _Erich Friedman_, Aug 08 2005