login
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))).
2
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
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
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