A111516 Triangle G(n,k) read by rows: number of order-preserving partial transformations (of an n-element totally ordered set) of waist k (waist(alpha) = max(Im(alpha))).

1, 1, 1, 1, 3, 4, 1, 7, 12, 18, 1, 15, 32, 56, 88, 1, 31, 80, 160, 280, 450, 1, 63, 192, 432, 832, 1452, 2364, 1, 127, 448, 1120, 2352, 4424, 7700, 12642, 1, 255, 1024, 2816, 6400, 12896, 23872, 41456, 68464, 1, 511, 2304, 6912, 16896, 36288, 71136, 130176, 225648, 374274

Offset

0,5

Links

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

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

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

Formula

G(n,k) = Sum_{j=1..n} C(n,j)*C(k+j-2,j-1) for 1 <= k <= n. [Corrected by Petros Hadjicostas, Feb 13 2021]

G(n,k) = 2*G(n-1,k) - G(n-1,k-1) + G(n,k-1) for n >= 2 and 1 <= k <= n-1 with initial conditions G(n,0) = 1 for n >= 0, G(n,1) = 2^n - 1 for n >= 1, and G(n,n) = A050146(n) for n >= 2.

Sum_{k=0..n} G(n,k) = A123164(n).

From Petros Hadjicostas, Feb 13 2021: (Start)

G(n,k) = A055807(n+k,k) for 0 <= k <= n.

Bivariate o.g.f.: Sum_{n,k>=0} G(n,k)*x^n*y^k = ((2 - 2*y - 2*x*y + x*y^2) + 2*x*(y - 1)/(1 - x) + x*y*(2 - 3*y - 2*x*y + x*y^2)/sqrt(1 - 6*x*y + x^2*y^2))/(2*(1 - 2*x - y + x*y)). (End)

Example

Triangle G(n,k) (with rows n >= 0 and columns k = 0..n) begins:
  1;
  1,  1;
  1,  3,   4;
  1,  7,  12,  18;
  1, 15,  32,  56,  88;
  1, 31,  80, 160, 280,  450;
  1, 63, 192, 432, 832, 1452, 2364;
  ...
G(2,2) = 4 because there are exactly 4 order-preserving partial transformations (on a 2-element chain) of waist 2, namely: (1)->(2), (2)->(2), (1,2)->(1,2), and (1,2)->(2,2) - the mappings are coordinate-wise.

Crossrefs

Cf. A050146 (main diagonal), A055807, A123164 (row sums).

Sequence in context: A076412 A053707 A075052 * A210636 A116392 A324559

Adjacent sequences: A111513 A111514 A111515 * A111517 A111518 A111519

Keyword

nonn,tabl

Author

Abdullahi Umar, Aug 25 2008

Extensions

G(7,5) corrected by and more terms from Petros Hadjicostas, Feb 13 2021

Status

approved