A145035 T(n,k) is the number of order-decreasing and order-preserving partial transformations (of an n-chain) of waist k (waist(alpha) = max(Im(alpha))).

1, 1, 1, 1, 3, 2, 1, 7, 8, 6, 1, 15, 24, 28, 22, 1, 31, 64, 96, 112, 90, 1, 63, 160, 288, 416, 484, 394, 1, 127, 384, 800, 1344, 1896, 2200, 1806, 1, 255, 896, 2112, 4000, 6448, 8952, 10364, 8558, 1, 511, 2048, 5376, 11264, 20160, 31616, 43392, 50144, 41586, 1, 1023, 4608, 13312, 30464, 59520, 102592, 157760, 214656, 247684, 206098

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) = (n-k+1)*Sum_{j=1..n} binomial(n,j)*binomial(k+j-2,j-1)/n for k > 0.

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

Example

T(3,2) = 8 because there are exactly 8 order-decreasing and order-preserving partial transformations (of a 3-chain) of waist 2, namely: 2->2, 3->2, (1,2)->(1,2), (1,3)->(1,2), (2,3)->(1,2), (2,3)->(2,2), (1,2,3)->(1,1,2), (1,2,3)->(1,2,2).
Table begins
  1;
  1,   1;
  1,   3,   2;
  1,   7,   8,   6;
  1,  15,  24,  28,   22;
  1,  31,  64,  96,  112,   90;
  1,  63, 160, 288,  416,  484,  394;
  1, 127, 384, 800, 1344, 1896, 2200, 1806;

Maple

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

Crossrefs

A006318 gives row sums of T(n, k).

Sequence in context: A111960 A130462 A059380 * A359413 A192020 A367564

Adjacent sequences: A145032 A145033 A145034 * A145036 A145037 A145038

Keyword

nonn,easy,tabl

Author

Abdullahi Umar, Sep 30 2008

Status

approved