cp's OEIS Frontend

A344261 Number of n-step walks from one of the vertices with degree 3 to itself on the four-vertex diamond graph.

%I A344261 #32 Aug 18 2021 16:28:49
%S A344261 1,0,3,4,15,32,91,220,583,1464,3795,9652,24831,63440,162763,416524,
%T A344261 1067575,2733672,7003971,17938660,45954543,117709184,301527355,
%U A344261 772364092,1978473511,5067929880,12981823923,33253543444,85180839135,218195012912,558918369451
%N A344261 Number of n-step walks from one of the vertices with degree 3 to itself on the four-vertex diamond graph.
%C A344261 a(n) is the number of n-step walks from vertex A to itself on the graph below.
%C A344261 B--C
%C A344261 | /|
%C A344261 |/ |
%C A344261 A--D
%H A344261 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (0,5,4).
%F A344261 a(n) = a(n-1) + 4*a(n-2) - (-1)^n for n > 1.
%F A344261 a(n) = 5*a(n-2) + 4*a(n-3) for n > 2.
%F A344261 a(n) = A344236(n-1) + 2*a(n-2) + 2*A344236(n-2) for n > 1.
%F A344261 a(n) = A344236(n) + (-1)^n.
%F A344261 a(n) = A006131(n) - A344236(n).
%F A344261 a(n) = (A006131(n) + (-1)^n)/2.
%F A344261 a(n) = ((sqrt(17)-1)/(4*sqrt(17)))*((1-sqrt(17))/2)^n + ((sqrt(17)+1)/(4*sqrt(17)))*((1+sqrt(17))/2)^n + (1/2)*(-1)^n.
%F A344261 G.f.: (2*x^2 - 1)/(4*x^3 + 5*x^2 - 1).
%e A344261 Let A, B, C and D be the vertices of the four-vertex diamond graph, where A and C are the vertices with degree 3. Then, a(3) = 4 walks from A to itself are: (A, B, C, A), (A, C, B, A), (A, C, D, A) and (A, D, C, A).
%p A344261 f := proc(n) option remember; if n = 0 then 1; elif n = 1 then 0; elif n = 2 then 3; else 5*f(n - 2) + 4*f(n - 3); end if; end proc
%t A344261 LinearRecurrence[{0, 5, 4}, {1, 0, 3}, 30] (* _Amiram Eldar_, May 13 2021 *)
%o A344261 (Python)
%o A344261 def A344261_list(n):
%o A344261     list = [1, 0, 3] + [0] * (n - 3)
%o A344261     for i in range(3, n):
%o A344261         list[i] = 5 * list[i - 2] + 4 * list[i - 3]
%o A344261     return list
%o A344261 print(A344261_list(31)) # _M. Eren Kesim_, Jul 19 2021
%Y A344261 Cf. A006131, A344236.
%K A344261 nonn,easy,walk
%O A344261 0,3
%A A344261 _M. Eren Kesim_, May 13 2021