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

Author

M. Eren Kesim, May 12 2021

Keywords

• nonn
• easy
• walk

Comments

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

B--C

| /|

|/ |

A--D

Examples

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

Links

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

Crossrefs

Cf. A006131, A344261.

Programs

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]

PARI

my(p=Mod('x,'x^2-'x-4)); a(n) = (vecsum(Vec(lift(p^n))) + n%2) >> 1; \\ Kevin Ryde, May 13 2021

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

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