A145034 T(n,k) is the number of order-decreasing and order-preserving partial transformations (of an n-chain) of width (width(alpha) = |Dom(alpha)|) and waist (waist(alpha) = max(Im(alpha))) both equal to k.

1, 1, 1, 1, 2, 1, 1, 3, 4, 2, 1, 4, 9, 12, 5, 1, 5, 16, 36, 40, 14, 1, 6, 25, 80, 150, 140, 42, 1, 7, 36, 150, 400, 630, 504, 132, 1, 8, 49, 252, 875, 1960, 2646, 1848, 429, 1, 9, 64, 392, 1680, 4900, 9408, 11088, 6864, 1430, 1, 10, 81, 576, 2940, 10584, 26460, 44352, 46332, 25740, 4862

Offset

0,5

Links

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

Laradji, A. and Umar, A. Combinatorial Results for Semigroups of Order-Decreasing Partial Transformations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.8. [From Abdullahi Umar, Oct 07 2008]

Formula

T(n,k) = binomial(n,k)*binomial(2k-2,k-1)*(n-k+1)/n for n >= k >= 1; T(n,0) = 1.

T(n,n) = A000108(n-1) for n > 0.

Example

T(3,2) = 4 because there are exactly 4 order-decreasing and order-preserving partial transformations (of a 3-chain) of width and waist both equal to 2, namely: (1,2)->(1,2), (1,3)->(1,2), (2,3)->(1,2), (2,3)->(2,2).
Table begins
  1;
  1,  1;
  1,  2,  1;
  1,  3,  4,   2;
  1,  4,  9,  12,    5;
  1,  5, 16,  36,   40,    14;
  1,  6, 25,  80,  150,   140,    42;
  1,  7, 36, 150,  400,   630,   504,   132;
  1,  8, 49, 252,  875,  1960,  2646,  1848,   429;
  1,  9, 64, 392, 1680,  4900,  9408, 11088,  6864,  1430;
  1, 10, 81, 576, 2940, 10584, 26460, 44352, 46332, 25740, 4862;

Maple

A145034 := proc(n, k) if k = 0 then 1; else binomial(n, k)*binomial(2*k-2, k-1)*(n-k+1)/n ; end if; end proc: # R. J. Mathar, Jun 11 2011

Crossrefs

Cf. A000108.

Sequence in context: A292975 A056863 A120019 * A286510 A336842 A159933

Adjacent sequences: A145031 A145032 A145033 * A145035 A145036 A145037

Keyword

nonn,tabl

Author

Abdullahi Umar, Sep 30 2008

Status

approved