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

Offset: 0

Author

M. Eren Kesim, May 13 2021

Keywords

• nonn
• easy
• walk

Comments

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

B--C

| /|

|/ |

A--D

Examples

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

Links

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

Crossrefs

Cf. A006131, A344236.

Programs

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

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

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