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.

1, 1, 1, 1, 6, 1, 1, 21, 15, 1, 1, 60, 102, 28, 1, 1, 155, 490, 310, 45, 1, 1, 378, 1935, 2220, 735, 66, 1, 1, 889, 6741, 12285, 7315, 1491, 91, 1

Offset: 0

Author

Abdullahi Umar, Sep 09 2008

Keywords

• nonn
• tabl

Comments

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.

Examples

			Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
  1;
  1,   1;
  1,   6,    1;
  1,  21,   15,     1;
  1,  60,  102,    28,    1;
  1, 155,  490,   310,   45,    1;
  1, 378, 1935,  2220,  735,   66,  1;
  1, 889, 6741, 12285, 7315, 1491, 91, 1;
  ...
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.
		

Links

• A. Laradji and A. Umar, Combinatorial results for semigroups of order-preserving partial transformations, Journal of Algebra, 278 (2004), 342-359.
• A. Laradji and A. Umar, Combinatorial results for semigroups of order-decreasing partial transformations, J. Integer Seq., 7 (2004), 04.3.8.

Crossrefs

Cf. A000384, A066524, A076454, A112857, A123164.

Formula

T(n,k) = C(n,k)*A112857(n,k) for 0 <= k <= n.

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

From Petros Hadjicostas, Feb 14 2021: (Start)

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.

T(n,1) = n*(2^n - 1) = A066524(n) for n >= 1.

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

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