login
A344261
Number of n-step walks from one of the vertices with degree 3 to itself on the four-vertex diamond graph.
2
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
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
Sequence in context: A293047 A135100 A205485 * A055486 A041665 A052133
KEYWORD
nonn,easy,walk
AUTHOR
M. Eren Kesim, May 13 2021
STATUS
approved