login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A344236 Number of n-step walks from a universal vertex to the other on the diamond graph. 2
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 (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 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 * A265226 A299164 A131408

Adjacent sequences:  A344233 A344234 A344235 * A344237 A344238 A344239

KEYWORD

nonn,easy,walk

AUTHOR

M. Eren Kesim, May 12 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 13:21 EDT 2021. Contains 347668 sequences. (Running on oeis4.)