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,5

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.

Links

Table of n, a(n) for n=0..35.

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.

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)

Example

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.

Crossrefs

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

Sequence in context: A146988 A203954 A060972 * A363849 A296827 A056941

Adjacent sequences: A144063 A144064 A144065 * A144067 A144068 A144069

Keyword

nonn,tabl

Author

Abdullahi Umar, Sep 09 2008

Status

approved