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