A144224 - OEIS

A144224

T(n,k) is the number of idempotent order-preserving full transformations (of an n-element chain) of waist k (waist(alpha) = max(Im(alpha))).

1, 1, 2, 1, 2, 5, 1, 2, 5, 13, 1, 2, 5, 13, 34, 1, 2, 5, 13, 34, 89, 1, 2, 5, 13, 34, 89, 233, 1, 2, 5, 13, 34, 89, 233, 610, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 28657

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

OFFSET

1,3

REFERENCES

Laradji, A. and Umar, A. Combinatorial results for semigroups of order-preserving full transformations. Semigroup Forum 72, (2006), 51-62.

LINKS

Table of n, a(n) for n=1..78.

Luigi Santocanale, On discrete idempotent paths, arXiv:1906.05590 [math.LO], 2019.

FORMULA

T(n,k) = Sum_{j=0..k} C(k+j-1, k-1-j) for all n >= k. [Corrected by Georg Fischer, Jul 30 2023]

Sum of rows of T(n,k) is A001906(n+1) and T(n,k) = A001519(k+1) for all n>=k.

EXAMPLE

T(4,3) = 5 because there are exactly 5 idempotent order-preserving full transformations (on a 4-element chain) of waist 3, namely: the five possible ordered images (1,1,3,3), (1,2,3,3), (1,3,3,3), (2,2,3,3), (3,3,3,3) of (1,2,3,4).

1, 2;

1, 2, 5;

1, 2, 5, 13;

1, 2, 5, 13, 34;

1, 2, 5, 13, 34, 89;

1, 2, 5, 13, 34, 89, 233;

1, 2, 5, 13, 34, 89, 233, 610;

...

MAPLE

seq(print(seq(add(binomial(k+j-1, k-1-j), j=0..k), k=1..n)), n=1..12); # Georg Fischer, Jul 30 2023

CROSSREFS

Cf. A000045, A001519, A001906.