A121466 Triangle read by rows: T(n,k) = is the number of directed column-convex polyominoes of area n having along the lower contour exactly k reentrant corners, i.e., a vertical step that is followed by a horizontal step (n >= 1, k >= 0).

1, 2, 4, 1, 8, 5, 16, 17, 1, 32, 49, 8, 64, 129, 39, 1, 128, 321, 150, 11, 256, 769, 501, 70, 1, 512, 1793, 1524, 338, 14, 1024, 4097, 4339, 1375, 110, 1, 2048, 9217, 11762, 4973, 640, 17, 4096, 20481, 30705, 16508, 3075, 159, 1, 8192, 45057, 77808, 51340, 12918

Offset

1,2

Comments

Also number of nondecreasing Dyck paths of semilength n and such that there are k positive differences in the sequence of the valley altitudes, preceded by a 0. Example: T(5,2)=1 because we have UUDUUDUDDD, where U=(1,1) and D=(1,-1) (the valleys are at the altitudes 1 and 2 with two "jumps" in the sequence 0,1,2).

Row n has ceiling(n/2) terms.

Row sums are the odd-subscripted Fibonacci numbers (A001519).

Links

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

E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.

E. Barcucci, R. Pinzani and R. Sprugnoli, Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.

E. Deutsch and H. Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.

Formula

T(n,0) = 2^(n-1) = A000079(n-1).

T(n,1) = 1 + (n-3)*2^(n-2) = A000337(n-2).

T(n,2) = A055581(n-5).

Sum_{k=0..ceiling(n/2)-1} k*T(n,k) = A001870(n-3).

T(n,k) = Sum_{j=0..n-2*k-1} 2^j*binomial(n-k-2-j,k-1)*binomial(k+j,k) for k >= 1; T(n,0) = 2^(n-1).

G.f.: G(t,z) = z(1-z)/(1-3z+2z^2-tz^2).

Example

T(5,2)=1 because we have the directed column-convex polyomino [(0,2),(1,3),(2,3)] (here the j-th pair gives the lower and upper levels of the j-th column).
Triangle starts:
   1;
   2;
   4,   1;
   8,   5;
  16,  17,   1;
  32,  49,   8;
  64, 129,  39,   1;

Maple

with(combinat): T:=(n, k)->add(2^j*binomial(n-k-2-j, k-1)*binomial(k+j, k), j=0..n-2*k-1): for n from 0 to 15 do seq(T(n, k), k=0..ceil(n/2)-1) od; # yields sequence in triangular form

Crossrefs

Cf. A000079, A000337, A001519, A001870, A055581.

Sequence in context: A127529 A091977 A112829 * A273717 A258065 A065290

Adjacent sequences: A121463 A121464 A121465 * A121467 A121468 A121469

Keyword

nonn,tabf

Author

Emeric Deutsch, Aug 02 2006

Status

approved