A199572 Number of round trips of length n on the cycle graph C_2 from any of the two vertices.

1, 0, 4, 0, 16, 0, 64, 0, 256, 0, 1024, 0, 4096, 0, 16384, 0, 65536, 0, 262144, 0, 1048576, 0, 4194304, 0, 16777216, 0, 67108864, 0, 268435456, 0, 1073741824, 0, 4294967296, 0, 17179869184, 0, 68719476736, 0, 274877906944, 0

Offset: 0

Author

Wolfdieter Lang, Nov 08 2011

Keywords

• nonn
• easy
• walk

Comments

See the array and triangle A199571 for the general cycle graph C_N counting.

This is A000302 and A000004 interleaved. - Omar E. Pol, Nov 09 2011

With offset = 1: Number of ways to separate n distinguishable objects into an odd size pile and an even size pile. For example: a(3) = 4 because we have: {{1},{2,3}}; {{2},{1,3}}; {{3},{1,2}}; {{1,2,3},{}}. - Geoffrey Critzer, Jun 10 2013

Inverse Stirling transform of A065143. - Vladimir Reshetnikov, Nov 01 2015

Examples

			a(2) = 4 from starting with vertex no. 1, with edges e1 and e2 to vertex no. 2: e1e1, e2e2, e1e2 and e2e1.
		

Links

• R. J. Mathar, Counting Walks on Finite Graphs, Section 1.
• Index entries for linear recurrences with constant coefficients, signature (0,4).

Crossrefs

Cf. A000007 (N=1), A078008 (N=3). a(n) is second row of array w(N,L) A199571, and second column of the triangle a(K,N) A199571.

Cf. A065143 (Stirling transform).

Programs

Mathematica

nn = 39; Drop[Range[0, nn]! CoefficientList[Series[ Sinh[x] Cosh[x], {x, 0, nn}],x], 1] (* Geoffrey Critzer, Jun 10 2013 *)

PARI

vector(100, n, n--; (2^(n) +(-2)^n)/2) \\ Altug Alkan, Nov 02 2015

Formula

a(n) = (2^n + (-2)^n)/2 = 2^(n-1)*(1 + (-1)^n).

O.g.f.: 1/(1-(2*x)^2).

E.g.f.: cosh(2*x)=U(0) where U(k) = 1 + 2*x^2/((4*k+1)*(2*k+1) - x^2*(4*k+1)*(2*k+1)/(x^2 + (4*k+3)*(k+1)/U(k+1))); (continued fraction). - Sergei N. Gladkovskii, Oct 23 2012