A102089 Triangle read by rows: T(n,k) is the number of k-matchings in the C_n X P_3 graph (C_n is the cycle graph on n vertices and P_3 is the path graph on 3 vertices).
1, 10, 24, 12, 1, 15, 69, 107, 36, 1, 20, 142, 440, 588, 288, 32, 1, 25, 240, 1125, 2710, 3227, 1645, 240, 1, 30, 363, 2290, 8139, 16446, 18141, 9870, 2148, 108, 1, 35, 511, 4060, 19222, 55867, 99085, 103231, 58310, 15267, 1274, 1, 40, 684, 6560, 38934
Offset: 2
Examples
T(2,3)=12 because in the graph C_2 X P_3 with vertex set {A,B,C,A',B',C'} and edge set {AB,AC,A'B',B'C',a,a',b,b',c,c'}, where a and a' are two edges between A and A', b and b' are two edges between B and B' and c and c' are two edges between C and C', we have the following twelve3-matchings (as a matter of fact they are perfect matchings): eight 3-matchings by taking one edge from each of the pairs {a,a'},{b,b'} and {c,c'}; two 3-matchings by taking AB, A'B' and either edge from the pair {c,c'}; two 3-matchings by taking BC, B'C' and either edge from the pair {a,a'}.
Triangle starts:
1, 10, 24, 12;
1, 15, 69, 107, 36;
1, 20, 142, 440, 588, 288, 32;
1, 25, 240, 1125, 2710, 3227, 1645, 240;
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. (51) and Table VII).
Programs
-
Maple
G:= - z^2*( - 1 - 10*t + z^6*t^9 - 3*z^5*t^7 - 3*z^2*t^2 - 17*z^2*t^3 - z^3*t^3 + z^3*t^4 + 3*z^4*t^5 + 9*z^4*t^6 - 8*z^4*t^7 + 33*z^3*t^5 - 2*z^2*t^4 - 8*z^5*t^8 + t^12*z^7 - 4*t^8*z^4 + 49*t^6*z^3 + 48*t^5*z^2 - 3*t^9*z^5 - 4*t^11*z^6 - 36*t^9*z^4 + 40*t^7*z^3 + 40*t^6*z^2 - 26*t^10*z^5 + 2*z^7*t^13 + 8*t^12*z^6 - 25*z*t^2 - 47*z*t^3 - 12*z*t^4 - 3*z*t - 24*t^2 - 12*t^3)/(z^2*t^3 - 1 - z*t)/(z^6*t^9 - z^5*t^7 + z^5*t^6 - 5*z^4*t^6 - 3*z^4*t^5 - 2*z^4*t^4 - 2*z^3*t^4 + z^3*t^3 + 5*z^2*t^3 + z^3*t^2 + 7*z^2*t^2 + 2*z^2*t + 3*z*t + z - 1): Gser:=simplify(series(G,z=0,13)): for n from 2 to 9 do P[n]:=coeff(Gser,z^n) od: b:=proc(n) if n mod 2 = 0 then 1 + 3*n/2 else 1 + b(n - 1) fi end:for n from 2 to 9 do seq(coeff(t*P[n],t^k),k=1..b(n)) od; # yields sequence in triangular form
Formula
The row generating polynomials A[n] satisfy A[n] =(1 + 2t)A[n - 1] + t(3 + 10t + 6t^2)A[n - 2] + t^2*(3 + 7t)A[n - 3] - t^3*( - 1 + 3t + 12t^2 + 10t^3)A[n - 4] - t^5*(3 + 3t + 4t^2)A[n - 5] + t^7*(3 + 2t + 6t^2)A[n - 6] - t^9*(1 - 2t)A[n - 7] - t^12*A[n - 8] G.f.= - z^2*( - 1 - 10t + z^6*t^9 - 3z^5*t^7 - 3z^2*t^2 - 17z^2*t^3 - z^3*t^3 + z^3*t^4 + 3z^4*t^5 + 9z^4*t^6 - 8z^4*t^7 + 33z^3*t^5 - 2z^2*t^4 - 8z^5*t^8 + t^12*z^7 - 4t^8*z^4 + 49t^6*z^3 + 48t^5*z^2 - 3t^9*z^5 - 4t^11*z^6 - 36t^9*z^4 + 40t^7*z^3 + 40t^6*z^2 - 26t^10*z^5 + 2z^7*t^13 + 8t^12*z^6 - 25zt^2 - 47zt^3 - 12zt^4 - 3zt - 24t^2 - 12t^3)/[(z^2*t^3 - 1 - zt)(z^6*t^9 - z^5*t^7 + z^5*t^6 - 5z^4*t^6 - 3z^4*t^5 - 2z^4*t^4 - 2z^3*t^4 + z^3*t^3 + 5z^2*t^3 + z^3*t^2 + 7z^2*t^2 + 2z^2*t + 3zt + z - 1)].
Comments