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,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

Crossrefs

Cf. A006131, A344236.

Sequence in context: A293047 A135100 A205485 * A055486 A041665 A052133

Adjacent sequences: A344258 A344259 A344260 * A344262 A344263 A344264

Keyword

nonn,easy,walk

Author

M. Eren Kesim, May 13 2021

Status

approved