|
| |
|
|
A121692
|
|
Triangle read by rows: T(n,k) is the number of deco polyominoes of height n and vertical height (i.i. number of rows) k (1<=k<=n). A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.
|
|
2
|
|
|
|
1, 1, 1, 1, 4, 1, 1, 10, 12, 1, 1, 22, 57, 39, 1, 1, 46, 216, 293, 163, 1, 1, 94, 741, 1651, 1664, 888, 1, 1, 190, 2412, 8181, 12458, 11143, 5934, 1, 1, 382, 7617, 37739, 81255, 102558, 87066, 46261, 1, 1, 766, 23616, 166573, 489753, 823597, 941572, 773772
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
Row sums are the factorials (A000142). T(n,1)=1, T(n,2)=3*2^(n-2)-2=A033484(n-2) for n>=2. T(n,3)=A121693(n). Sum(k*T(n,k), k=1..n)=A121694(n).
|
|
|
REFERENCES
|
E. Barcucci, S. Brunetti and F. Del Ristoro, Succession rules and deco polyominoes, Theoret. Informatics Appl., 34, 2000, 1-14.
E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29- 42.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Rec. relation: T(n,1)=1; T(n,n)=1; T(n,k)=k*T(n-1,k)+2*T(n-1,k-1)+Sum(T(n-1,j), j=1..k-2) for k<=n; T(n,k)=0 for k>n. Rec. relation for the row generating polynomials P[n](t): P[1]=t, P[n]=tP[n-1]+(t+t^2+...+t^(n-1))#P[n-1] for n>=2. Here # stands for the "max-multiplication" of polynomials, a distributive operation, following the rule t^a # t^b = t^max(a,b). The second Maple program is based on these polynomials (seems to be faster).
|
|
|
EXAMPLE
|
T(2,1)=1 and T(2,2)=1 because the deco polyominoes of height 2 are the horizontal and vertical dominoes, having, respectively, 1 and 2 rows.
Triangle starts:
1;
1,1;
1,4,1;
1,10,12,1;
1,22,57,39,1;
1,46,216,293,163,1;
|
|
|
MAPLE
|
T:=proc(n, k): if k=1 then 1 elif k=n then 1 elif k>n then 0 else k*T(n-1, k)+2*T(n-1, k-1)+add(T(n-1, j), j=1..k-2) fi: end: for n from 1 to 11 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form
with(linalg): a:=proc(i, j) if i=j then i elif i>j then 1 else 0 fi end: p:=proc(Q) local n, A, b, w, QQ: n:=degree(Q): A:=matrix(n, n, a): b:=j->coeff(Q, t, j): w:=matrix(n, 1, b): QQ:=multiply(A, w): sort(expand(add(QQ[k, 1]*t^k, k=1..n)+t*Q)): end: P[1]:=t: for n from 2 to 11 do P[n]:=p(P[n-1]) od: for n from 1 to 11 do seq(coeff(P[n], t, j), j=1..n) od; # yields sequence in triangular form
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
