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

3, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648

Offset: 0

Author

Wolfdieter Lang, Nov 02 2011

Keywords

• nonn
• easy

Comments

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

Examples

			With the graph P_3 as 1-2-3:
n=0: 3, from the length 0 walks starting at 1, 2 and 3.
n=2: 8, from the walks of length 4, namely 12121, 12321, 21212, 23232, 21232, 23212, 32323 and 32123.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (2).

Crossrefs

Cf. A198632, 2*A005248, A198635.

Essentially the same as A000079, A020707, A077552 etc.

Programs

Mathematica

Join[{3},NestList[2#&,4,30]] (* Harvey P. Dale, Nov 07 2020 *)

PARI

a(n)=if(n,2<Charles R Greathouse IV, Jan 02 2012

Formula

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

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.

Empirical g.f.: (3-2*x)/(1-2*x). - Colin Barker, Jan 02 2012

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.