login
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.
1

%I #20 Feb 15 2021 22:35:23

%S 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 2220,735,66,1,1,889,6741,12285,7315,1491,91,1

%N 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 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 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 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 T(n,k) = C(n,k)*A112857(n,k) for 0 <= k <= n.

%F 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 From _Petros Hadjicostas_, Feb 14 2021: (Start)

%F 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 T(n,1) = n*(2^n - 1) = A066524(n) for n >= 1.

%F T(n,n-1) = n*(2*n - 1) = A000384(n) for n >= 1.

%F T(n,n-2) = A076454(n-1) for n >= 2. (End)

%e Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:

%e 1;

%e 1, 1;

%e 1, 6, 1;

%e 1, 21, 15, 1;

%e 1, 60, 102, 28, 1;

%e 1, 155, 490, 310, 45, 1;

%e 1, 378, 1935, 2220, 735, 66, 1;

%e 1, 889, 6741, 12285, 7315, 1491, 91, 1;

%e ...

%e 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 Cf. A000384, A066524, A076454, A112857, A123164.

%K nonn,tabl

%O 0,5

%A _Abdullahi Umar_, Sep 09 2008