A095367 Number of walks of length n between two nodes at distance 2 in the cycle graph C_9.

1, 0, 4, 0, 15, 1, 56, 9, 210, 56, 792, 299, 3003, 1470, 11441, 6868, 43776, 31008, 168151, 136629, 648208, 591261, 2507046, 2523676, 9726080, 10656387, 37839375, 44612702, 147600981, 185477216, 577147212, 766744608, 2261792303

Offset: 2

Author

Herbert Kociemba, Jul 03 2004

Keywords

• nonn
• easy

Comments

In general (2^n/m)*Sum_{r=0..m-1} cos(2*Pi*k*r/m)*cos(2*Pi*r/m)^n is the number of walks of length n between two nodes at distance k in the cycle graph C_m. Here we have m=9 and k=2.

Links

• Index entries for linear recurrences with constant coefficients, signature (1,5,-4,-5,2).

Crossrefs

Cf. A095364, A095368, A095369.

Formula

a(n) = (2^n/9)*Sum_{r=0..8} cos(4*Pi*r/9)*cos(2*Pi*r/9)^n.

G.f.: x^2(-1+x+x^2)/((1+x)*(-1+2x)*(1-3x^2+x^3));

a(n) = a(n-1) + 5*a(n-2) - 4*a(n-3) - 5*a(n-4) + 2*a(n-5).