|
%I #4 Mar 30 2012 17:36:10
%S 1,2,5,1,16,7,1,65,43,11,1,326,279,98,16,1,1957,1999,867,194,22,1,
%T 13700,15949,8068,2225,348,29,1,109601,141291,80493,25868,5009,580,37,
%U 1,986410,1381219,865728,313305,70949,10229,913,46,1,9864101,14798599
%N Triangle read by rows: T(n,k) is the number of deco polyominoes of height n such that the bottom of the last column is at level k (n>=1; k>=0). A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column.
%C Row n has n-1 terms (n>=2). Row sums are the factorials (A000142). T(n,0)=A000522(n-1). Sum(k*T(n,k), k>=0)=A121633(n).
%C T(n,k)=number of permutations of {1,2,...,n} that have k left-to-right maxima not in the initial string of consecutive left-to-right maxima. Example: T(4,1)=7 because we have (13)24, (3)124, (3)142, (2)143, (23)14, (3)214 and (3)241; in each of these permutations 4 is the only left-to-right maximum not in the initial string of left-to-right maxima (shown between parentheses). T(4,2)=1 because we have 2134. - _Emeric Deutsch_, Apr 04 2008
%D E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
%F The row generating polynomials satisfy P(n,t)=1-t+(t+n-1)P(n-1,t) for n>=2 with P(1,t)=1. T(n,k)=T(n-1,k-1)+(n-1)T(n-1,k) for k>=2.
%e T(2,0)=2 because the deco polyominoes of height 2 are the vertical and horizontal dominoes; the last column of each starts at level 0.
%e Triangle starts:
%e 1;
%e 2;
%e 5,1;
%e 16,7,1;
%e 65,43,11,1;
%e 326,279,98,16,1;
%p P[1]:=1: for n from 2 to 12 do P[n]:=sort(expand(1+t*(P[n-1]-1)+(n-1)*P[n-1])) od: 1; for n from 2 to 11 do seq(coeff(P[n],t,j),j=0..n-2) od; # yields sequence in triangular form
%Y Cf. A000142, A000522, A121633.
%K nonn,tabf
%O 1,2
%A _Emeric Deutsch_, Aug 12 2006
|
