A110858 Triangle read by rows: number of order-preserving partial transformations (of an n-element chain) of width and waist both equal to r (width(alpha) = |Dom(alpha)| and waist(alpha) = max(Im(alpha))).

1, 1, 1, 1, 2, 2, 1, 3, 6, 6, 1, 4, 12, 24, 20, 1, 5, 20, 60, 100, 70, 1, 6, 30, 120, 300, 420, 252, 1, 7, 42, 210, 700, 1470, 1764, 924, 1, 8, 56, 336, 1400, 3920, 7056, 7392, 3432, 1, 9, 72, 504, 2520, 8820, 21168, 33264, 30888, 12870, 1, 10, 90, 720, 4200, 17640, 52920, 110880, 154440, 128700, 48620

Offset

0,5

Comments

Whenever the formula generates a zero, it is changed to a one in the sequence. - Harvey P. Dale, Sep 06 2013

Links

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

Laradji, A. and Umar, A. Combinatorial results for semigroups of order-preserving partial transformations, Journal of Algebra 278, (2004), 342-359.

Laradji, A. and Umar, A. Combinatorial results for semigroups of order-decreasing partial transformations, J. Integer Seq. 7 (2004), 04.3.8

Formula

G(n,k) = binomial(n,k)*binomial(2*k-2,k-1), n >= k > 0.

Example

G(3,2)=6 because there are exactly 6 order-preserving partial transformations (on a 3-element chain) of both width and waist equal to 2, namely: (1,2)->(1,2),(1,2)->(2,2),(1,3)->(1,2),(1,3)->(2,2),(2,3)->(1,2),(2,3)->(2,2)
1;
1,1;
1,2,2;
1,3,6,6;
1,4,12,24,20;
1,5,20,60,100,70;
1,6,30,120,300,420,252;
1,7,42,210,700,1470,1764,924;
1,8,56,336,1400,3920,7056,7392,3432;

Maple

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

Mathematica

Flatten[Table[Binomial[n, k]Binomial[2k-2, k-1], {n, 0, 10}, {k, 0, n}]/.{0->1}] (* Harvey P. Dale, Sep 04 2013 *)

Crossrefs

Sequence in context: A107111 A082037 A163649 * A008279 A239572 A056043

Adjacent sequences: A110855 A110856 A110857 * A110859 A110860 A110861

Keyword

nonn,tabl

Author

Abdullahi Umar, Aug 25 2008

Status

approved