A145034 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

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

(list; table; graph; refs; listen; history; text; internal format)

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