A095929 Number of closed walks of length 2n at a vertex of the cyclic graph on 10 nodes C_10.

1, 2, 6, 20, 70, 254, 948, 3614, 13990, 54740, 215766, 854702, 3396916, 13530350, 53971350, 215492564, 860941798, 3441074654, 13757249460, 55010542910, 219993856006, 879848932052, 3519064567926, 14075391282830, 56299295324980, 225191238869774

Offset

0,2

Comments

In general 2^n/m*Sum_{r=0..m-1} cos(2Pi*k*r/m)*cos(2Pi*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=10 and k=0.

The number of round trips of odd length is zero. See the array w(N,L) and triangle a(K,N) given in A199571 for the general case. - Wolfdieter Lang, Nov 08 2011

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (7,-13,4).

Formula

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

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

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

a(n/2) = ( 2^n +2*phi^n +2*(phi-1)^n )*(1+(-1)^n)/10, with the golden section phi = A001622. - Wolfdieter Lang, Nov 08 2011

a(n) = (2^(-n)*(8^n+2*(3-sqrt(5))^n+2*(3+sqrt(5))^n))/5. - Colin Barker, Apr 27 2016

a(n) = (4^n + 2*Lucas(2*n))/5. - Ehren Metcalfe, Apr 04 2019

a(n) = Sum_{k=-n..n} binomial(2*n, n+5*k). - Greg Dresden, Jan 05 2023

Example

a(2)=6 from the six round trips from, say, vertex no. 1: 12121, 1(10)1(10)1, 121(10)1, 1(10)121, 12321 and 1(10)9(10)1. - Wolfdieter Lang, Nov 08 2011

Mathematica

f[n_]:=FullSimplify[TrigToExp[(4^n/10)Sum[Cos[Pi*k/5]^(2n), {k, 0, 9}]]]; Table[f[n], {n, 0, 35}]
LinearRecurrence[{7, -13, 4}, {1, 2, 6}, 30] (* Harvey P. Dale, Dec 09 2018 *)

Prog

(PARI) Vec((1-5*x+5*x^2)/((1-4*x)*(1-3*x+x^2)) + O(x^50)) \\ Colin Barker, Apr 27 2016

Crossrefs

Cf. A094233, A199571.

Sequence in context: A360292 A151284 A049138 * A078482 A049128 A192540

Adjacent sequences: A095926 A095927 A095928 * A095930 A095931 A095932

Keyword

nonn,easy

Author

Herbert Kociemba, Jul 12 2004

Status

approved