login
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
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
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
Sequence in context: A090803 A018015 A080039 * A374699 A265226 A357835
KEYWORD
nonn,easy,walk
AUTHOR
M. Eren Kesim, May 12 2021
STATUS
approved