OFFSET
2,2
COMMENTS
Row n contains n+1 terms.
Equivalently, the n-th row gives the coefficients of the matching-generating polynomial of the n-prism graph. - Eric W. Weisstein, Apr 03 2018
LINKS
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. (19) and Table IV).
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial
Eric Weisstein's World of Mathematics, Prism Graph
FORMULA
G.f.: -z^2*(5t^4*z^2-1+t^4*z^3+t^5*z^3-6t-5t^2-2tz-7zt^2+zt^3-t^2*z^2)/[(1+tz)(t^3*z^3-tz^2-2tz-z+1)].
The row generating polynomials A[n] satisfy A[n]=(1+t)A[n-1]+2t(1+t)A[n-2]+ t^2*(1-t)A[n-3]-t^4*A[n-4] with A[2]=1+6t+5t^2, A[3]=1+9t+18t^2+4t^3, A[4]=1+12t+42t^2+44t^3+9t^4 and A[5]=1+15t+75t^2+145t^3+95t^4+11t^5.
EXAMPLE
T(3,3)=4 because in the graph C_3 X P_2 with vertex set {A,B,C,A',B',C'} and edge set {AB,AC,BC, A'B',A'C',B'C',AA',BB',CC'} we have the following
3-matchings: {AA',BB',CC'}, {AA',BC,B'C'}, {BB',AC,A'C'} and {CC',AB,A'B'} (as a matter of fact, these are perfect matchings).
Triangle starts:
1, 6, 5;
1, 9, 18, 4;
1, 12, 42, 44, 9;
1, 15, 75, 145, 95, 11;
MAPLE
G:=-z^2*(5*t^4*z^2-1+z^3*t^4+z^3*t^5-6*t-5*t^2-2*z*t-7*z*t^2+z*t^3-z^2*t^2)/(z*t+1)/(z^3*t^3-z^2*t-2*z*t-z+1) : Gser:=simplify(series(G, z=0, 13)): for n from 2 to 11 do P[n]:=coeff(Gser, z^n) od:for n from 2 to 11 do seq(coeff(t*P[n], t^k), k=1..n+1) od; # yields sequence in triangular form
MATHEMATICA
CoefficientList[LinearRecurrence[{1 + x, 2 x (1 + x), -(-1 + x) x^2, -x^4}, {1 + x, 1 + 6 x + 5 x^2, 1 + 9 x + 18 x^2 + 4 x^3, 1 + 12 x + 42 x^2 + 44 x^3 + 9 x^4}, {2, 10}], x] // Flatten (* Eric W. Weisstein, Apr 03 2018 *)
CoefficientList[CoefficientList[Series[-( -1 - 6 x - 5 x^2 - 2 x z - 7 x^2 z + x^3 z - x^2 z^2 + 5 x^4 z^2 + x^4 z^3 + x^5 z^3)/((1 + x z) (1 - z - 2 x z - x z^2 + x^3 z^3)), {z, 0, 10}], z], x] // Flatten (* Eric W. Weisstein, Apr 03 2018 *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Dec 29 2004
STATUS
approved