|
%I #6 Oct 29 2012 07:58:35
%S 1,1,3,1,1,10,29,26,5,1,17,102,267,302,123,11,1,24,224,1044,2593,3388,
%T 2150,552,36,1,31,395,2696,10769,25835,36771,29580,12181,2111,95,1,38,
%U 615,5566,31106,111882,261965,395184,372109,206206,60730,7852,281,1,45
%N Triangle read by rows: T(n,k) is the number of k-matchings in the P_4 X P_n lattice graph.
%C Row sums yield A033507. T(n,2n) yields A005178.
%D 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).
%F 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).
%F 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]
%e T(2,4)=5 because in the graph P_4 X P_2 with vertices a(0,0), b(0,1), c(0,2),
%e d(0,3),a'(1,0),b'(1,1),c'(1,2),d'(1,3), we have the following 4-matchings
%e {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).
%e Triangle starts:
%e 1;
%e 1, 3, 1;
%e 1, 10, 29, 26, 5;
%e 1, 17, 102, 267, 302, 123, 11;
%e 1, 24, 224, 1044, 2593, 3388, 2150, 552, 36;
%p 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):
%p 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
%Y Cf. A033507, A005178.
%K nonn,tabf
%O 0,3
%A _Emeric Deutsch_, Dec 28 2004
|
