OFFSET
1,1
COMMENTS
The characteristic polynomial x^4 - 19*x^3 + 41*x^2 - 19*x + 1 is palindromic. Using y = x + 1/x, it reduces to y^2 - 19*y + 39, with roots (19 +- sqrt(205))/2. The dominant root is approximately 16.599.
LINKS
Jean Lauro Muller, Table of n, a(n) for n = 1..30
Jean Lauro Muller, Python program for computing the sequence
Index entries for linear recurrences with constant coefficients, signature (19,-41,19,-1).
FORMULA
a(n) = 19*a(n-1) - 41*a(n-2) + 19*a(n-3) - a(n-4) for n >= 5, with a(1) = 38, a(2) = 558, a(3) = 9158, a(4) = 151838.
G.f.: 2*x*(19 - 82*x + 57*x^2 - 4*x^3)/(1 - 19*x + 41*x^2 - 19*x^3 + x^4).
EXAMPLE
For n=1, the 5 X 2 grid on the Klein bottle has a(1) = 38 perfect matchings (multigraph convention).
MATHEMATICA
LinearRecurrence[{19, -41, 19, -1}, {38, 558, 9158, 151838}, 18] (* Stefano Spezia, Aug 20 2026 *)
PROG
(Python) # See links section for program.
CROSSREFS
KEYWORD
nonn,easy,new
AUTHOR
Jean Lauro Muller, Aug 19 2026
STATUS
approved