cp's OEIS Frontend

A144066 T(n, k) is the number of order-preserving partial transformations (of an n-element chain) of height k (height(alpha) = |Im(alpha)|); triangle T read by rows.

%I A144066 #20 Feb 15 2021 22:35:23
%S A144066 1,1,1,1,6,1,1,21,15,1,1,60,102,28,1,1,155,490,310,45,1,1,378,1935,
%T A144066 2220,735,66,1,1,889,6741,12285,7315,1491,91,1
%N A144066 T(n, k) is the number of order-preserving partial transformations (of an n-element chain) of height k (height(alpha) = |Im(alpha)|); triangle T read by rows.
%C A144066 T(n, k) is also the number of elements in the Green's J-classes of the monoid of order-preserving partial transformations (of an n-element chain). Sum of rows of T(n, k) is A123164.
%H A144066 A. Laradji and A. Umar, <a href="http://dx.doi.org/10.1016/j.jalgebra.2003.10.023">Combinatorial results for semigroups of order-preserving partial transformations</a>, Journal of Algebra, 278 (2004), 342-359.
%H A144066 A. Laradji and A. Umar, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Umar/um.html">Combinatorial results for semigroups of order-decreasing partial transformations</a>, J. Integer Seq., 7 (2004), 04.3.8.
%F A144066 T(n,k) = C(n,k)*A112857(n,k) for 0 <= k <= n.
%F A144066 C(n-1,k-1)*T(n,k) = 2((n-k+1)/(n-k))*T(n-1,k) + C(n,k)*T(n-1,k-1). [This is wrong.]
%F A144066 From _Petros Hadjicostas_, Feb 14 2021: (Start)
%F A144066 T(n,k) = 2*n*T(n-1,k)/(n-k) + n*T(n-1,k-1)/k for 1 <= k <= n-1 with T(n,0) = T(n,n) = 1 for n >= 0.
%F A144066 T(n,1) = n*(2^n - 1) = A066524(n) for n >= 1.
%F A144066 T(n,n-1) = n*(2*n - 1) = A000384(n) for n >= 1.
%F A144066 T(n,n-2) = A076454(n-1) for n >= 2. (End)
%e A144066 Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
%e A144066   1;
%e A144066   1,   1;
%e A144066   1,   6,    1;
%e A144066   1,  21,   15,     1;
%e A144066   1,  60,  102,    28,    1;
%e A144066   1, 155,  490,   310,   45,    1;
%e A144066   1, 378, 1935,  2220,  735,   66,  1;
%e A144066   1, 889, 6741, 12285, 7315, 1491, 91, 1;
%e A144066   ...
%e A144066 T(2,1) = 6 because there are exactly 6 order-preserving partial transformations (on a 2-element chain) of height 1, namely: (1)->(1), (1)->(2), (2)->(1), (2)->(2), (1,2)->(1,1), and (1,2)->(2,2) -- the mappings are coordinate-wise.
%Y A144066 Cf. A000384, A066524, A076454, A112857, A123164.
%K A144066 nonn,tabl
%O A144066 0,5
%A A144066 _Abdullahi Umar_, Sep 09 2008