A102079 - OEIS

%I #14 Aug 25 2019 13:47:55

%S 1,6,5,1,9,18,4,1,12,42,44,9,1,15,75,145,95,11,1,18,117,336,420,192,

%T 20,1,21,168,644,1225,1085,371,29,1,24,228,1096,2834,3880,2588,696,49,

%U 1,27,297,1719,5652,10656,11097,5823,1278,76,1,30,375,2540,10165,24626,35645,29380,12535,2310,125

%N 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).

%C Row n contains n+1 terms.

%C Equivalently, the n-th row gives the coefficients of the matching-generating polynomial of the n-prism graph. - _Eric W. Weisstein_, Apr 03 2018

%H H. Hosoya and A. Motoyama, <a href="http://dx.doi.org/10.1063/1.526778">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</a>, J. Math. Physics 26 (1985) 157-167 (eq. (19) and Table IV).

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching-GeneratingPolynomial.html">Matching-Generating Polynomial</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrismGraph.html">Prism Graph</a>

%F 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)].

%F 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.

%e 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

%e 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).

%e Triangle starts:

%e 1, 6, 5;

%e 1, 9, 18, 4;

%e 1, 12, 42, 44, 9;

%e 1, 15, 75, 145, 95, 11;

%p 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

%t 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 *)

%t 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 *)

%Y Cf. A102080, A068397.

%K nonn,tabf

%O 2,2

%A _Emeric Deutsch_, Dec 29 2004