login
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

%I #14 Feb 21 2019 01:12:25

%S 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,

%T 1,7,36,150,400,630,504,132,1,8,49,252,875,1960,2646,1848,429,1,9,64,

%U 392,1680,4900,9408,11088,6864,1430,1,10,81,576,2940,10584,26460,44352,46332,25740,4862

%N 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.

%H Laradji, A. and Umar, A. <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Umar/um.html">Combinatorial Results for Semigroups of Order-Decreasing Partial Transformations</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.8. [From _Abdullahi Umar_, Oct 07 2008]

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

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

%e 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).

%e Table begins

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 1, 3, 4, 2;

%e 1, 4, 9, 12, 5;

%e 1, 5, 16, 36, 40, 14;

%e 1, 6, 25, 80, 150, 140, 42;

%e 1, 7, 36, 150, 400, 630, 504, 132;

%e 1, 8, 49, 252, 875, 1960, 2646, 1848, 429;

%e 1, 9, 64, 392, 1680, 4900, 9408, 11088, 6864, 1430;

%e 1, 10, 81, 576, 2940, 10584, 26460, 44352, 46332, 25740, 4862;

%p 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

%Y Cf. A000108.

%K nonn,tabl

%O 0,5

%A _Abdullahi Umar_, Sep 30 2008