|
|
A095307
|
|
Number of walks of length n between two nodes at distance 2 in the cycle graph C_7.
|
|
3
|
|
|
1, 0, 4, 1, 15, 7, 56, 37, 210, 176, 793, 793, 3017, 3458, 11561, 14756, 44592, 62017, 172995, 257775, 674520, 1062601, 2641366, 4352660, 10381281, 17742621, 40927033, 72048354, 161766061, 291693136, 640758252, 1178135905, 2542557383, 4749439975, 10103745288
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,3
|
|
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=7 and k=2.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2^n/7*Sum_{r=0..6} cos(4*Pi*r/7)*cos(2*Pi*r/7)^n).
a(n) = a(n-1) + 4*a(n-2) - 3*a(n-3) - 2*a(n-4).
G.f.: x^2*(1-x) / ((1-2*x)*(1+x-2*x^2-x^3)).
|
|
MATHEMATICA
|
LinearRecurrence[{1, 4, -3, -2}, {1, 0, 4, 1}, 40] (* Harvey P. Dale, Sep 22 2019 *)
|
|
PROG
|
(PARI) Vec(x^2*(1-x)/((1-2*x)*(1+x-2*x^2-x^3)) + O(x^40)) \\ Colin Barker, Nov 28 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|