cp's OEIS Frontend

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).

%I A121466 #16 Mar 04 2025 17:22:04
%S A121466 1,2,4,1,8,5,16,17,1,32,49,8,64,129,39,1,128,321,150,11,256,769,501,
%T A121466 70,1,512,1793,1524,338,14,1024,4097,4339,1375,110,1,2048,9217,11762,
%U A121466 4973,640,17,4096,20481,30705,16508,3075,159,1,8192,45057,77808,51340,12918
%N 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).
%C A121466 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).
%C A121466 Row n has ceiling(n/2) terms.
%C A121466 Row sums are the odd-subscripted Fibonacci numbers (A001519).
%H A121466 E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, <a href="http://dx.doi.org/10.1016/S0012-365X(97)82778-1">Nondecreasing Dyck paths and q-Fibonacci numbers</a>, Discrete Math., 170, 1997, 211-217.
%H A121466 E. Barcucci, R. Pinzani and R. Sprugnoli, <a href="http://dx.doi.org/10.1007/3-540-56610-4_71">Directed column-convex polyominoes by recurrence relations</a>, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.
%H A121466 E. Deutsch and H. Prodinger, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00222-6">A bijection between directed column-convex polyominoes and ordered trees of height at most three</a>, Theoretical Comp. Science, 307, 2003, 319-325.
%H A121466 Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL28/Florez/florez51.html">Counting Subwords in Non-Decreasing Dyck Paths</a>, Journal of Integer Sequences, Vol. 28 (2025), Article 25.1.6. See pp. 11, 19.
%F A121466 T(n,0) = 2^(n-1) = A000079(n-1).
%F A121466 T(n,1) = 1 + (n-3)*2^(n-2) = A000337(n-2).
%F A121466 T(n,2) = A055581(n-5).
%F A121466 Sum_{k=0..ceiling(n/2)-1} k*T(n,k) = A001870(n-3).
%F A121466 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).
%F A121466 G.f.: G(t,z) = z(1-z)/(1-3z+2z^2-tz^2).
%e A121466 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).
%e A121466 Triangle starts:
%e A121466    1;
%e A121466    2;
%e A121466    4,   1;
%e A121466    8,   5;
%e A121466   16,  17,   1;
%e A121466   32,  49,   8;
%e A121466   64, 129,  39,   1;
%p A121466 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
%Y A121466 Cf. A000079, A000337, A001519, A001870, A055581.
%K A121466 nonn,tabf
%O A121466 1,2
%A A121466 _Emeric Deutsch_, Aug 02 2006