|
| |
|
|
A046741
|
|
Triangle read by rows giving number of arrangements of k dumbbells on 2 X n grid (n >= 0, k >= 0).
|
|
13
| |
|
|
1, 1, 1, 1, 4, 2, 1, 7, 11, 3, 1, 10, 29, 26, 5, 1, 13, 56, 94, 56, 8, 1, 16, 92, 234, 263, 114, 13, 1, 19, 137, 473, 815, 667, 223, 21, 1, 22, 191, 838, 1982, 2504, 1577, 424, 34, 1, 25, 254, 1356, 4115, 7191, 7018, 3538, 789, 55, 1, 28, 326, 2054, 7646, 17266, 23431
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,5
|
|
|
COMMENTS
| Equivalently, T(n,k) is the number of k-matchings in the ladder graph L_n = P_2 X P_n. - Emeric Deutsch, 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 + 2*t*z^2 + 2*t^2*z^3+2*t^3*z^4+...= (1+t)*z+t^2*z^2+2*t*z^2/(1-t*z); then the g.f. is 1/(1-g)=(1-t*z)/(1-z-2*t*z-t*z^2+t^3*z^3) (see eq. (4) of the Grimson reference). From this the recurrence of the McQuistan & Lichtman reference follows at once. - Emeric Deutsch, Oct 16 2006
|
|
|
REFERENCES
| R. C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15 (1974), 214-216.
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.
R. B. McQuistan and S. J. Lichtman, Exact recursion relation for 2 x N arrays of dumbbells, J. Math. Phys., 11 (1970), 3095-3099.
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.
|
|
|
LINKS
| Eric Weisstein's World of Mathematics, Matching Polynomial [From Eric W. Weisstein, Sep 27 2008]
|
|
|
FORMULA
| The row generating polynomials P[n] satisfy P[n]=(1+2*t)*P[n-1]+t*P[n-2]-t^3*P[n-3] with P[0]=1, P[1]=1+t, P[2]=1+4*t+2*t^2. G.f.: (1-t*z)/(1-z-2*t*z-t*z^2+t^3*z^3). - Emeric Deutsch, Dec 25 2004
T(k, n)=T(k, n-1)+2*T(k-1, n-1)+T(k-1, n-2)-T(k-3, n-3).
|
|
|
EXAMPLE
| 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, Dec 25 2004
Triangle starts:
1;
1,1;
1,4,2;
1,7,11,3;
1,10,29,26,5;
|
|
|
MAPLE
| 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)
|
|
|
MATHEMATICA
| p[n_] := p[n] = (1 + 2t) p[n-1] + t*p[n-2] - t^3*p[n-3]; p[0] = 1; p[1] = 1+t; p[2] = 1 + 4t + 2t^2; Flatten[ Table[ CoefficientList[ Series[p[n], {t, 0, n}], t], {n, 0, 10}]][[;; 62]] (* From Jean-François Alcover, Jul 13 2011, after E. Deutsch *)
|
|
|
CROSSREFS
| Diagonals give A002940, A002941, A002889.
Row sums yield A030186. T(n, n)=Fibonacci(n+1) (A000045).
Sequence in context: A119953 A010645 A039962 * A136249 A142147 A142073
Adjacent sequences: A046738 A046739 A046740 * A046742 A046743 A046744
|
|
|
KEYWORD
| nonn,easy,nice,tabl
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Larry Reeves (larryr(AT)acm.org), Apr 07 2000
|
| |
|
|
