|
|
A095931
|
|
Number of walks of length 2n between two nodes at distance 4 in the cycle graph C_10.
|
|
1
|
|
|
1, 7, 36, 165, 715, 3004, 12393, 50559, 204820, 826045, 3321891, 13333932, 53457121, 214146295, 857417220, 3431847189, 13733091643, 54947296924, 219828275865, 879415437615, 3517929664756, 14072420067757, 56291516582931, 225170873858700, 900696081703825
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,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=4.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 7*a(n-1) - 13*a(n-2) + 4*a(n-3).
G.f.: x^2/((1-4*x)*(1-3*x+x^2)).
a(n) = 4^n/(10*Sum_{r=0..9} cos(4*Pi*r/5)*cos(Pi*r/5)^(2*n) ).
a(n) = (4^n - (2*cos(Pi/5))^(2*n+1) + (2*cos(2*Pi/5))^(2*n+1))/5.
a(n) = (4^n - ((sqrt(5)+1)/2)^(2*n+1) + ((sqrt(5)-1)/2)^(2*n+1))/5.
a(n) = Sum_{k=1..floor((n+3)/5)} C(2*n+1,n+3-5*k). (End)
|
|
MAPLE
|
seq(sum(binomial(2*n+1, n+3-5*k), k=1..floor((n+3)*(1/5))), n=2..20) # Mircea Merca, Jun 25 2011
|
|
MATHEMATICA
|
f[n_]:=FullSimplify[TrigToExp[(4^n/10)Sum[Cos[4Pi*k/5]Cos[Pi*k/5]^(2n), {k, 0, 9}]]]; Table[f[n], {n, 2, 35}]
|
|
PROG
|
(PARI) x='x+O('x^66); /* that many terms */
Vec(x^2/((1-4*x)*(1-3*x+x^2))) /* show terms */ /* Joerg Arndt, Jun 25 2011 */
(GAP) a:=[1, 7, 36];; for n in [4..25] do a[n]:=7*a[n-1]-13*a[n-2]+4*a[n-3]; od; a; # Muniru A Asiru, Dec 19 2018
(Magma) I:=[1, 7, 36]; [n le 3 select I[n] else 7*Self(n-1)-13*Self(n-2)+4*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Dec 20 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|