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,3

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

Links

Table of n, a(n) for n=0..39.

R. J. Mathar, Counting Walks on Finite Graphs, Section 1.

Index entries for linear recurrences with constant coefficients, signature (0,4).

Formula

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

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

Example

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

Mathematica

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

Prog

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

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

Sequence in context: A079986 A134746 A210067 * A003195 A190759 A086262

Adjacent sequences: A199569 A199570 A199571 * A199573 A199574 A199575

Keyword

nonn,easy,walk

Author

Wolfdieter Lang, Nov 08 2011

Status

approved