This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A380451 #36 Jul 06 2025 15:02:53
%S A380451 2,15,95,604,3835,24349,154594,981531,6231827,39566420,251210695,
%T A380451 1594958889,10126534850,64294264119,408209961239,2591761096236,
%U A380451 16455320099427,104476280613925,663329132764770,4211535247894499,26739409243687915,169770870862086564,1077890252944724559,6843620413168932241,43450750418785228802
%N A380451 Number of disjoint-path coverings for 2 X n rectangular grids, admitting zero-length paths.
%C A380451 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.
%C A380451 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:
%C A380451 "two isolated nodes" 1 1 1 1 1 0 1 1 1 0 1
%C A380451 "top tail" 1 1 1 1 1 0 1 1 1 0 1
%C A380451 "bottom tail" 1 1 1 1 1 0 1 1 1 0 1
%C A380451 "vertical edge" 1 1 1 1 0 1 1 1 0 0 1
%C A380451 "two indep. tails" 1 1 1 1 1 0 1 1 1 0 1
%C A380451 "two connected tails" 1 1 1 1 0 1 1 1 0 0 1
%C A380451 "upper hook" 1 0 1 1 0 0 0 1 0 0 1
%C A380451 "lower hook" 1 1 0 1 0 0 1 0 0 0 1
%C A380451 "all three edges" 1 0 0 1 0 0 0 0 0 0 1
%C A380451 start 1 0 0 1 0 0 0 0 0 0 1
%C A380451 end 0 0 0 0 0 0 0 0 0 0 0
%C A380451 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.
%C A380451 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.
%C A380451 Configurations listed in the order as in the transfer matrix (the border on the pictures is to the right):
%C A380451 * -* * * -*
%C A380451 , , , | , ,
%C A380451 * * -* * -*
%C A380451 * -*
%C A380451 ... | ... (the case where tails have been connected earlier),
%C A380451 * -*
%C A380451 *-* * *-*
%C A380451 | , | , |
%C A380451 * *-* *-*
%D A380451 R. P. Stanley, Enumerative Combinatorics, Cambridge University Press (2012).
%H A380451 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (7,-4,-1,1).
%F A380451 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).
%e A380451 For n = 1 the a(1) = 2 solutions are
%e A380451 * * *-*
%e A380451 For n = 2 the a(2) = 15 solutions are
%e A380451 * *
%e A380451 * *
%e A380451 *-* * * * * * *
%e A380451 | |
%e A380451 * * *-* * * * *
%e A380451 *-* *-* * * * * *-* * *
%e A380451 | | | | | |
%e A380451 * * * * *-* *-* *-* * *
%e A380451 *-* *-* * * *-*
%e A380451 | | | | | |
%e A380451 * * *-* *-* *-*
%p A380451 a:=n->`if`(n<5,[2,15,95,604][n],7*a(n-1)-4*a(n-2)-a(n-3)+a(n-4));
%t A380451 a[n_]:=LinearRecurrence[{7,-4,-1,1},{2,15,95,604},n][[-1]]
%o A380451 (Python) from functools import reduce;
%o A380451 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]
%Y A380451 Cf. A003763.
%K A380451 nonn,easy
%O A380451 1,1
%A A380451 _Anton M. Alekseev_, Jun 22 2025
%E A380451 a(16) onwards corrected by _Anton M. Alekseev_, Jul 06 2025