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

0, 1, 2, 5, 14, 33, 90, 221, 582, 1465, 3794, 9653, 24830, 63441, 162762, 416525, 1067574, 2733673, 7003970, 17938661, 45954542, 117709185, 301527354, 772364093, 1978473510, 5067929881, 12981823922, 33253543445, 85180839134, 218195012913, 558918369450

Offset

0,3

Comments

a(n) is the number of n-step walks from vertex A to vertex C 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) = A344261(n-1) + 2*a(n-2) + 2*A344261(n-2) for n > 1.

a(n) = A344261(n) - (-1)^n.

a(n) = A006131(n) - A344261(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 + x)/(-4*x^3 - 5*x^2 + 1).

a(n) = 5*a(n-2) + 4*a(n-3) for n > 2. - Stefano Spezia, May 13 2021

Example

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

Maple

f := proc(n) option remember; if n <= 2 then n; else 5*f(n - 2) + 4*f(n - 3); end if; end proc

Mathematica

LinearRecurrence[{0, 5, 4}, {0, 1, 2}, 30]

Prog

(Python)
def A344236_list(n):
    list = [0, 1, 2] + [0] * (n - 3)
    for i in range(3, n):
        list[i] = 5 * list[i - 2] + 4 * list[i - 3]
    return list
print(A344236_list(31)) # M. Eren Kesim, Jul 19 2021
(PARI) my(p=Mod('x, 'x^2-'x-4)); a(n) = (vecsum(Vec(lift(p^n))) + n%2) >> 1; \\ Kevin Ryde, May 13 2021

Crossrefs

Cf. A006131, A344261.

Sequence in context: A090803 A018015 A080039 * A374699 A265226 A357835

Adjacent sequences: A344233 A344234 A344235 * A344237 A344238 A344239

Keyword

nonn,easy,walk

Author

M. Eren Kesim, May 12 2021

Status

approved