login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Total number of round trips, each of length 2*n on the graph P_3 (o-o-o).
8

%I #45 Mar 14 2024 13:03:32

%S 3,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,

%T 131072,262144,524288,1048576,2097152,4194304,8388608,16777216,

%U 33554432,67108864,134217728,268435456,536870912,1073741824,2147483648

%N Total number of round trips, each of length 2*n on the graph P_3 (o-o-o).

%C See the array and triangle A198632 for the general case for the graph P_N (there N is n and the length is l=2*k).

%H <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (2).

%F a(n) = w(3,2*n), n>=0, with w(3,l) the total number of closed walks on the graph P_3 (the simple path with 3 points (vertices) and 2 lines (or edges)).

%F O.g.f. for w(3,l) (with zeros for odd l): y*(d/dy)S(3,y)/S(3,y) with y=1/x and Chebyshev S-polynomials (coefficients A049310). See A198632, also for a rewritten form.

%F Empirical g.f.: (3-2*x)/(1-2*x). - _Colin Barker_, Jan 02 2012

%F This g.f. follows from the Chebyshev o.g.f. given above with x -> sqrt(x). Therefore a(0) = 3 and a(n) = 2^(n+1), n >= 1. - _Wolfdieter Lang_, Feb 18 2013.

%e With the graph P_3 as 1-2-3:

%e n=0: 3, from the length 0 walks starting at 1, 2 and 3.

%e n=2: 8, from the walks of length 4, namely 12121, 12321, 21212, 23232, 21232, 23212, 32323 and 32123.

%t Join[{3},NestList[2#&,4,30]] (* _Harvey P. Dale_, Nov 07 2020 *)

%o (PARI) a(n)=if(n,2<<n,3) \\ _Charles R Greathouse IV_, Jan 02 2012

%Y Cf. A198632, 2*A005248, A198635.

%K nonn,easy

%O 0,1

%A _Wolfdieter Lang_, Nov 02 2011