login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=1..53.

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

Cf. A000142, A033484, A121693, A121694.

Sequence in context: A174669 A140711 A164366 * A264614 A261762 A225062

Adjacent sequences:  A121689 A121690 A121691 * A121693 A121694 A121695

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Aug 17 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 24 01:41 EDT 2021. Contains 346269 sequences. (Running on oeis4.)