|
|
A096976
|
|
Number of walks of length n on P_3 plus a loop at the end.
|
|
9
|
|
|
1, 0, 1, 0, 2, 1, 5, 5, 14, 19, 42, 66, 131, 221, 417, 728, 1341, 2380, 4334, 7753, 14041, 25213, 45542, 81927, 147798, 266110, 479779, 864201, 1557649, 2806272, 5057369, 9112264, 16420730, 29587889, 53317085, 96072133, 173118414, 311945595, 562110290
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Counts closed walks of length n at the start of P_3 to which a loop has been added at the other extremity. a(n+1) counts walks between the first node and the last. Let A be the adjacency matrix of the graph P_3 with a loop added at the end. A is a 'reverse Jordan matrix' [0,0,1;0,1,1;1,1,0]. a(n) is obtained by taking the (1,1) element of A^n.
Sequence is also related to matrices associated with rhombus substitution tilings showing 7-fold rotational symmetry. Let A_{7,1} be the 3 X 3 unit-primitive matrix (see [Jeffery]) A_{7,1}=[0,1,0; 1,0,1; 0,1,1]; then a(n)=[A_{7,1}^n]_(1,1). - L. Edson Jeffery, Jan 05 2012
a(n+2) is the (1,1) element of the n-th power of each of the two 3 X 3 matrices: [0,1,1; 1,0,0; 1,0,1], [0,1,1; 1,1,0; 1,0,0]. - Christopher Hunt Gribble, Apr 03 2014
|
|
LINKS
|
|
|
FORMULA
|
G.f. : (1-x-x^2)/(1-x-2x^2+x^3); a(n)=a(n-1)+2a(n-2)-a(n-3).
|
|
EXAMPLE
|
G.f. = 1 + x^2 + 2*x^4 + x^5 + 5*x^6 + 5*x^7 + 14*x^8 + 19*x^9 + ... - Michael Somos, Dec 12 2023
|
|
MATHEMATICA
|
a[ n_] := {1, 0, 0} . MatrixPower[{{1, 2, -1}, {1, 0, 0}, {0, 1, 0}}, n] . {1, 1, 3}; (* Michael Somos, Dec 12 2023 *)
|
|
PROG
|
(PARI) {a(n) = [1, 0, 0] * [1, 2, -1; 1, 0, 0; 0, 1, 0]^n * [1, 1, 3]~}; /* Michael Somos, Dec 12 2023 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|