A102079 Triangle read by rows: T(n,k) is the number of k-matchings in the C_n X P_2 graph (C_n is the cycle graph on n vertices and P_2 is the path graph on 2 vertices).

1, 6, 5, 1, 9, 18, 4, 1, 12, 42, 44, 9, 1, 15, 75, 145, 95, 11, 1, 18, 117, 336, 420, 192, 20, 1, 21, 168, 644, 1225, 1085, 371, 29, 1, 24, 228, 1096, 2834, 3880, 2588, 696, 49, 1, 27, 297, 1719, 5652, 10656, 11097, 5823, 1278, 76, 1, 30, 375, 2540, 10165, 24626, 35645, 29380, 12535, 2310, 125

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

Table of n, a(n) for n=2..64.

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

Cf. A102080, A068397.

Sequence in context: A242000 A238181 A197517 * A177938 A112282 A098866

Adjacent sequences: A102076 A102077 A102078 * A102080 A102081 A102082

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 29 2004

Status

approved