0,5

Equivalently, T(n,k) is the number of k-matchings in the ladder graph L_n = P_2 X P_n. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 25 2004

In other words, triangle of number of monomer-dimer tilings on (2,n)-block with k dimers. If z marks the size of the block and t marks the dimers, then it is easy to see that the g.f. for indecomposable tilings i.e. those that cannot be split vertically into smaller tilings, is g=(1+t)z + t^2*z^2 + 2tz^2 + 2t^2*z^3+2t^3*z^4+...= (1+t)z+t^2*z^2+2tz^2/(1-tz); then G.f.= 1/(1-g)=(1-tz)/(1-z-2tz-tz^2+t^3z^3) (see eq. (4) of the Grimson reference). From this the recurrence of the McQuistan & Lichtman reference follows at once. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 16 2006

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.

D. G. Rogers, An application of renewal sequences to the dimer problem, pp. 142-153 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979.

R. C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15 (1974), 214-216.

R. B. McQuistan and S. J. Lichtman, Exact recursion relation for 2 x N arrays of dumbbells, J. Math. Phys., 11 (1970), 3095-3099.

The row generating polynomials P[n] satisfy P[n]=(1+2t)P[n-1]+tP[n-2]-t^3*P[n-3] with P[0]=1, P[1]=1+t, P[2]=1+4t+2t^2. G.f.=(1-tz)/(1-z-2tz-tz^2+t^3z^3). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 25 2004

T(k, n)=T(k, n-1)+2T(k-1, n-1)+T(k-1, n-2)-T(k-3, n-3).

T(3, 2)=11 because in the 2 X 3 grid with vertex set {O(0, 0), A(1, 0), B(2, 0), C(2, 1), D(1, 1), E(0, 1)} and edge set {OA, AB, ED, DC, UE, AD, BC} we have the following eleven 2-matchings: {OA, BC}, {OA, DC}, {OA, ED}, {AB, DC}, {AB, ED}, {AB, OE}, {BC, AD}, {BC, ED}, {BC, OA}, {BC, OE}, and {DC, OE}. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 25 2004

Triangle starts:

1;

1,1;

1,4,2;

1,7,11,3;

1,10,29,26,5;

F[0]:=1:F[1]:=1+t:F[2]:=1+4*t+2*t^2:for n from 3 to 10 do F[n]:=sort(expand((1+2*t)*F[n-1]+t*F[n-2]-t^3*F[n-3])) od: for n from 0 to 10 do seq(coeff(t*F[n], t^k), k=1..n+1) od; # yields sequence in triangular form (Deutsch)

Diagonals give A002940, A002941, A002889.

Row sums yield A030186. T(n,n)=Fibonacci(n+1) (A000045).

Sequence in context: A119953 A010645 A039962 this_sequence A136249 A135294 A117016

Adjacent sequences: A046738 A046739 A046740 this_sequence A046742 A046743 A046744

nonn,easy,nice,tabl

njas

More terms from Larry Reeves (larryr(AT)acm.org), Apr 07 2000