OFFSET
1,1
COMMENTS
Can be computed using transfer matrix method. Suppose we build the coverage column-by-column, extending the "border" with each step by adding edges and vertices.
Upon enumerating all configurations of the border (8 configurations + a case of two paths connected earlier) and adding the start/end states, one can analyze which configuration can be obtained at the next step and build an 11 X 11 transfer matrix:
"two isolated nodes" 1 1 1 1 1 0 1 1 1 0 1
"top tail" 1 1 1 1 1 0 1 1 1 0 1
"bottom tail" 1 1 1 1 1 0 1 1 1 0 1
"vertical edge" 1 1 1 1 0 1 1 1 0 0 1
"two indep. tails" 1 1 1 1 1 0 1 1 1 0 1
"two connected tails" 1 1 1 1 0 1 1 1 0 0 1
"upper hook" 1 0 1 1 0 0 0 1 0 0 1
"lower hook" 1 1 0 1 0 0 1 0 0 0 1
"all three edges" 1 0 0 1 0 0 0 0 0 0 1
start 1 0 0 1 0 0 0 0 0 0 1
end 0 0 0 0 0 0 0 0 0 0 0
The sequence of interest can be obtained by multiplying the matrix to the power of N by a vector -- all zeros except the "start" position value equal to 1.
Also, characteristic polynomial of the transfer matrix is x^6 * (x+1) * (x^4-7x^3+4x^2+x-1), hence the recurrence relation is also easily obtainable through the Cayley-Hamilton theorem: x^(n) = 7*x^(n-1) - 4*x^(n-2) - x^(n-3) + x^(n-4) => a(n) = 7 * a(n-1) - 4 * a(n-2) - a(n-1) + a(n-4). Roots 0 and -1 do not contribute to the formula.
Configurations listed in the order as in the transfer matrix (the border on the pictures is to the right):
* -* * * -*
, , , | , ,
* * -* * -*
* -*
... | ... (the case where tails have been connected earlier),
* -*
*-* * *-*
| , | , |
* *-* *-*
REFERENCES
Richard P. Stanley, Enumerative Combinatorics, Cambridge University Press (2012).
LINKS
Index entries for linear recurrences with constant coefficients, signature (7,-4,-1,1).
FORMULA
Recurrence: a(n) = 7*a(n-1) - 4*a(n-2) - a(n-3) + a(n-4), where a(1) = 2, a(2) = 15, a(3) = 95, a(4) = 604 (for proof, see the comments section).
G.f.: x*(2 + x - 2*x^2 + x^3)/(1 - 7*x + 4*x^2 + x^3 - x^4). - Elmo R. Oliveira, Apr 11 2026
EXAMPLE
For n = 1 the a(1) = 2 solutions are
* * *-*
For n = 2 the a(2) = 15 solutions are
* *
* *
*-* * * * * * *
| |
* * *-* * * * *
*-* *-* * * * * *-* * *
| | | | | |
* * * * *-* *-* *-* * *
*-* *-* * * *-*
| | | | | |
* * *-* *-* *-*
MAPLE
a:=n->`if`(n<5, [2, 15, 95, 604][n], 7*a(n-1)-4*a(n-2)-a(n-3)+a(n-4));
MATHEMATICA
a[n_]:=LinearRecurrence[{7, -4, -1, 1}, {2, 15, 95, 604}, n][[-1]]
PROG
(Python) from functools import reduce;
a=lambda n:reduce(lambda s, _:s+[7*s[-1]-4*s[-2]-s[-3]+s[-4]], range(4, n), [2, 15, 95, 604])[n-1]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Anton M. Alekseev, Jun 22 2025
EXTENSIONS
a(16) onwards corrected by Anton M. Alekseev, Jul 06 2025
STATUS
approved