A344261 - OEIS

A344261

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

1, 0, 3, 4, 15, 32, 91, 220, 583, 1464, 3795, 9652, 24831, 63440, 162763, 416524, 1067575, 2733672, 7003971, 17938660, 45954543, 117709184, 301527355, 772364092, 1978473511, 5067929880, 12981823923, 33253543444, 85180839135, 218195012912, 558918369451

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

a(n) is the number of n-step walks from vertex A to itself on the graph below.

B--C

| /|

|/ |

A--D

LINKS

Table of n, a(n) for n=0..30.

Index entries for linear recurrences with constant coefficients, signature (0,5,4).

FORMULA

a(n) = a(n-1) + 4*a(n-2) - (-1)^n for n > 1.

a(n) = 5*a(n-2) + 4*a(n-3) for n > 2.

a(n) = A344236(n-1) + 2*a(n-2) + 2*A344236(n-2) for n > 1.

a(n) = A344236(n) + (-1)^n.

a(n) = A006131(n) - A344236(n).

a(n) = (A006131(n) + (-1)^n)/2.

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.

G.f.: (2*x^2 - 1)/(4*x^3 + 5*x^2 - 1).

EXAMPLE

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).

MAPLE

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

MATHEMATICA

LinearRecurrence[{0, 5, 4}, {1, 0, 3}, 30] (* Amiram Eldar, May 13 2021 *)

PROG

(Python)

def A344261_list(n):

list = [1, 0, 3] + [0] * (n - 3)

for i in range(3, n):

list[i] = 5 * list[i - 2] + 4 * list[i - 3]

return list

print(A344261_list(31)) # M. Eren Kesim, Jul 19 2021