login
A100265
Triangle read by rows: T(n,k) is the number of k-matchings in the P_4 X P_n lattice graph.
2
1, 1, 3, 1, 1, 10, 29, 26, 5, 1, 17, 102, 267, 302, 123, 11, 1, 24, 224, 1044, 2593, 3388, 2150, 552, 36, 1, 31, 395, 2696, 10769, 25835, 36771, 29580, 12181, 2111, 95, 1, 38, 615, 5566, 31106, 111882, 261965, 395184, 372109, 206206, 60730, 7852, 281, 1, 45
OFFSET
0,3
COMMENTS
Row sums yield A033507. T(n,2n) yields A005178.
REFERENCES
H. Hosoya and A. Motoyama, An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices, J. Math. Physics 26 (1985) 157-167 (eq. (46) and Table VI).
FORMULA
G.f.= (1 - zt^2)(z^6*t^12 + z^5*t^10 - 2z^5*t^9 - 4z^4*t^8 - 5z^4*t^7 - 3z^4*t^6 - 2z^3*t^6 + 4z^2*t^4 + 11z^2*t^3 + 3z^2*t^2 + zt^2 + 2zt - 1)/( - 1 + z + t^18*z^9 + z^3*t^2 + 4z^3*t^3 - 4z^3*t^4 - 27z^3*t^5 - 15z^3*t^6 + 5z*t + 3zt^2 + 2tz^2 + 13z^2*t^2 + 21z^2*t^3 + 5z^2*t^4 - 2z^7*t^11 - 3z^7*t^12 - 9z^7*t^13 - 9z^7*t^14 - 3z^4*t^4 - 18z^4*t^5 - 41z^4*t^6 - 40z^4*t^7 - 9z^4*t^8 - z^8*t^14 - z^8*t^16 + z^8*t^15 + 3z^5*t^6 + 14z^5*t^7 + 29z^5*t^8 + 24z^5*t^9 + 21z^5*t^10 - z^6*t^8 + 6z^6*t^10 + 19z^6*t^11 + 5z^6*t^12).
The row generating polynomials A[n] satisfy A[n] = (5t + 1 + 3t^2)A[n - 1] + (13t^2 + 21t^3 + 5t^4 + 2t)A[n - 2] + ( - 27t^5 - 15t^6 + t^2 - 4t^4 + 4t^3)A[n - 3] + ( - 40t^7 - 9t^8 - 41t^6 - 18t^5 - 3t^4)A[n - 4] + (29t^8 + 21t^10 + 3t^6 + 24t^9 + 14t^7)A[n - 5] + (6t^10 + 5t^12 - t^8 + 19t^11)A[n - 6] + ( - 9t^13 - 2t^11 - 3t^12 - 9t^14)A[n - 7] + ( - t^16 - t^14 + t^15)A[n - 8] + t^18*A[n - 9]
EXAMPLE
T(2,4)=5 because in the graph P_4 X P_2 with vertices a(0,0), b(0,1), c(0,2),
d(0,3),a'(1,0),b'(1,1),c'(1,2),d'(1,3), we have the following 4-matchings
{aa',bb',cc',dd'},{aa',bb',cd,c'd'},{ab,a'b',cc',dd'},{ab,a'b',cd,c'd'} and {aa',bc,b'c',dd'} (perfect matchings, of course).
Triangle starts:
1;
1, 3, 1;
1, 10, 29, 26, 5;
1, 17, 102, 267, 302, 123, 11;
1, 24, 224, 1044, 2593, 3388, 2150, 552, 36;
MAPLE
G:= - (1 + 3*z^3*t^4 + 11*z^3*t^5 + 6*z^3*t^6 - 2*z*t - 2*z*t^2 - 3*z^2*t^2 - 9*z^2*t^3 - 3*z^2*t^4 + z^7*t^14 + 3*z^4*t^6 + 5*z^4*t^7 + 2*z^4*t^8 - 3*z^5*t^8 - 3*z^5*t^9 - 5*z^5*t^10 - 2*z^6*t^11)/( - 1 + z + t^18*z^9 + z^3*t^2 + 4*z^3*t^3 - 4*z^3*t^4 - 27*z^3*t^5 - 15*z^3*t^6 + 5*z*t + 3*z*t^2 + 2*z^2*t + 13*z^2*t^2 + 21*z^2*t^3 + 5*z^2*t^4 - 2*z^7*t^11 - 3*z^7*t^12 - 9*z^7*t^13 - 9*z^7*t^14 - 3*z^4*t^4 - 18*z^4*t^5 - 41*z^4*t^6 - 40*z^4*t^7 - 9*z^4*t^8 - z^8*t^14 - z^8*t^16 + z^8*t^15 + 3*z^5*t^6 + 14*z^5*t^7 + 29*z^5*t^8 + 24*z^5*t^9 + 21*z^5*t^10 - z^6*t^8 + 6*z^6*t^10 + 19*z^6*t^11 + 5*z^6*t^12):
Gser:=simplify(series(G, z=0, 11)): P[0]:=1: for n from 1 to 8 do P[n]:=coeff(Gser, z^n) od:for n from 0 to 8 do seq(coeff(t*P[n], t^k), k=1..2*n + 1) od; # yields sequence in triangular form
CROSSREFS
Sequence in context: A342972 A060540 A087647 * A086766 A078688 A082466
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Dec 28 2004
STATUS
approved