A096976 Number of walks of length n on P_3 plus a loop at the end.

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

Offset: 0

Author

Paul Barry, Jul 16 2004

Keywords

• easy
• nonn

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

Examples

			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
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..3914
• Robin Chapman and Nicholas C. Singer, Eigenvalues of a bidiagonal matrix, Amer. Math. Monthly, 111 (2004) 441.
• Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, On a variant of Flory model, arXiv:2210.12411 [math.CO], 2022.
• L. E. Jeffery, Unit-primitive matrices
• Kai Wang, Fibonacci Numbers And Trigonometric Functions Outline, (2019).
• Index entries for linear recurrences with constant coefficients, signature (1,2,-1).

Crossrefs

Cf. A006053, A052547, A077998.

Programs

Mathematica

LinearRecurrence[{1, 2, -1}, {1, 0, 1}, 60] (* Vladimir Joseph Stephan Orlovsky, Feb 13 2012 *)
a[ n_] := {1, 0, 0} . MatrixPower[{{1, 2, -1}, {1, 0, 0}, {0, 1, 0}}, n] . {1, 1, 3}; (* Michael Somos, Dec 12 2023 *)

PARI

{a(n) = [1, 0, 0] * [1, 2, -1; 1, 0, 0; 0, 1, 0]^n * [1, 1, 3]~}; /* Michael Somos, Dec 12 2023 */

Formula

G.f. : (1-x-x^2)/(1-x-2x^2+x^3); a(n)=a(n-1)+2a(n-2)-a(n-3).

a(n) = 5a(n-2)-6a(n-4)+a(n-6). - Floor van Lamoen, Nov 02 2005

a(n) = A077998(-n) for all n in Z. - Michael Somos, Dec 12 2023