|
| |
|
|
A046741
|
|
Triangle read by rows giving number of arrangements of k dumbbells on 2 X n grid (n >= 0, k >= 0).
|
|
25
|
|
|
|
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;
text;
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
|
|
|
LINKS
|
|
|
|
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). (End)
T(n,k) = T(n-1,k) + 2*T(n-1,k-1) + T(n-2,k-1) - T(n-3,k-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 - Emeric 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]] (* Jean-François Alcover, Jul 13 2011, after Emeric Deutsch *)
CoefficientList[LinearRecurrence[{1 + 2 x, x, -x^3}, {1 + x, 1 + 4 x + 2 x^2, 1 + 7 x + 11 x^2 + 3 x^3}, {0, 10}], x] // Flatten (* Eric W. Weisstein, Apr 03 2018 *)
CoefficientList[CoefficientList[Series[-(1 + x z) (-1 - x + x^2 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 *)
|
|
|
PROG
|
(Haskell)
a046741 n k = a046741_tabl !! n !! k
a046741_row n = a046741_tabl !! n
a046741_tabl = [[1], [1, 1], [1, 4, 2]] ++ f [1] [1, 1] [1, 4, 2] where
f us vs ws = ys : f vs ws ys where
ys = zipWith (+) (zipWith (+) (ws ++ [0]) ([0] ++ map (* 2) ws))
(zipWith (-) ([0] ++ vs ++ [0]) ([0, 0, 0] ++ us))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Apr 07 2000
|
|
|
STATUS
|
approved
|
| |
|
|
