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

%I #17 Aug 29 2024 02:40:40

%S 1,0,4,0,15,1,56,9,210,56,792,299,3003,1470,11441,6868,43776,31008,

%T 168151,136629,648208,591261,2507046,2523676,9726080,10656387,

%U 37839375,44612702,147600981,185477216,577147212,766744608,2261792303

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

%C 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.

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,5,-4,-5,2).

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

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

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

%Y Cf. A095364, A095368, A095369.

%K nonn,easy

%O 2,3

%A _Herbert Kociemba_, Jul 03 2004