A100265 Triangle read by rows: T(n,k) is the number of k-matchings in the P_4 X P_n lattice graph.
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
Examples
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;
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).
Programs
-
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
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]
Comments