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

%I #14 Jul 30 2023 09:04:30

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

%T 2,5,13,34,89,233,610,1,2,5,13,34,89,233,610,1597,1,2,5,13,34,89,233,

%U 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

%N 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))).

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

%H Luigi Santocanale, <a href="https://arxiv.org/abs/1906.05590">On discrete idempotent paths</a>, arXiv:1906.05590 [math.LO], 2019.

%F 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]

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

%e 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).

%e 1;

%e 1, 2;

%e 1, 2, 5;

%e 1, 2, 5, 13;

%e 1, 2, 5, 13, 34;

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

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

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

%e ...

%p 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

%Y Cf. A000045, A001519, A001906.

%K nonn,tabl

%O 1,3

%A _Abdullahi Umar_, Sep 15 2008

%E a(45) and following terms corrected by _Georg Fischer_, Jul 30 2023