A380451 Number of disjoint-path coverings for 2 X n rectangular grids, admitting zero-length paths.

2, 15, 95, 604, 3835, 24349, 154594, 981531, 6231827, 39566420, 251210695, 1594958889, 10126534850, 64294264119, 408209961239, 2591761096236, 16455320099427, 104476280613925, 663329132764770, 4211535247894499, 26739409243687915, 169770870862086564, 1077890252944724559, 6843620413168932241, 43450750418785228802

Offset: 1

Author

Anton M. Alekseev, Jun 22 2025

Keywords

• nonn
• easy

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),

* -*

*-* * *-*

| , | , |

* *-* *-*

Examples

			For n = 1 the a(1) = 2 solutions are
  * *    *-*
For n = 2 the a(2) = 15 solutions are
  * *
  * *
  *-*    * *    * *    * *
                |        |
  * *    *-*    * *    * *
  *-*    *-*    * *    * *    *-*    * *
  |        |      |    |             | |
  * *    * *    *-*    *-*    *-*    * *
  *-*    *-*    * *    *-*
  | |      |    | |    |
  * *    *-*    *-*    *-*
		

References

• R. P. Stanley, Enumerative Combinatorics, Cambridge University Press (2012).

Links

• Index entries for linear recurrences with constant coefficients, signature (7,-4,-1,1).

Crossrefs

Cf. A003763.

Programs

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]]

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]

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).

Extensions

a(16) onwards corrected by Anton M. Alekseev, Jul 06 2025