cp's OEIS Frontend

A344236 Number of n-step walks from a universal vertex to the other on the diamond graph.

%I A344236 #49 Jul 19 2021 05:31:09
%S A344236 0,1,2,5,14,33,90,221,582,1465,3794,9653,24830,63441,162762,416525,
%T A344236 1067574,2733673,7003970,17938661,45954542,117709185,301527354,
%U A344236 772364093,1978473510,5067929881,12981823922,33253543445,85180839134,218195012913,558918369450
%N A344236 Number of n-step walks from a universal vertex to the other on the diamond graph.
%C A344236 a(n) is the number of n-step walks from vertex A to vertex C on the graph below.
%C A344236 B--C
%C A344236 | /|
%C A344236 |/ |
%C A344236 A--D
%H A344236 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (0,5,4).
%F A344236 a(n) = a(n-1) + 4*a(n-2) + (-1)^n for n > 1.
%F A344236 a(n) = A344261(n-1) + 2*a(n-2) + 2*A344261(n-2) for n > 1.
%F A344236 a(n) = A344261(n) - (-1)^n.
%F A344236 a(n) = A006131(n) - A344261(n).
%F A344236 a(n) = (A006131(n) - (-1)^n)/2.
%F A344236 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 A344236 G.f.: (2*x^2 + x)/(-4*x^3 - 5*x^2 + 1).
%F A344236 a(n) = 5*a(n-2) + 4*a(n-3) for n > 2. - _Stefano Spezia_, May 13 2021
%e A344236 Let A, B, C and D be the vertices of the diamond graph, where A and C are the universal vertices. Then, a(3) = 5 walks from A to C are: (A, B, A, C), (A, C, A, C), (A, C, B, C), (A, C, D, C), and (A, D, A, C).
%p A344236 f := proc(n) option remember; if n <= 2 then n; else 5*f(n - 2) + 4*f(n - 3); end if; end proc
%t A344236 LinearRecurrence[{0, 5, 4}, {0, 1, 2}, 30]
%o A344236 (Python)
%o A344236 def A344236_list(n):
%o A344236     list = [0, 1, 2] + [0] * (n - 3)
%o A344236     for i in range(3, n):
%o A344236         list[i] = 5 * list[i - 2] + 4 * list[i - 3]
%o A344236     return list
%o A344236 print(A344236_list(31)) # _M. Eren Kesim_, Jul 19 2021
%o A344236 (PARI) my(p=Mod('x,'x^2-'x-4)); a(n) = (vecsum(Vec(lift(p^n))) + n%2) >> 1; \\ _Kevin Ryde_, May 13 2021
%Y A344236 Cf. A006131, A344261.
%K A344236 nonn,easy,walk
%O A344236 0,3
%A A344236 _M. Eren Kesim_, May 12 2021