A363849 Triangular array read by rows. T(n,k) is the number of Green's H-classes of rank k in the semigroup of partial transformations, n >= 0, 0 <= k <= n.

1, 1, 1, 1, 6, 1, 1, 21, 18, 1, 1, 60, 150, 40, 1, 1, 155, 900, 650, 75, 1, 1, 378, 4515, 7000, 2100, 126, 1, 1, 889, 20286, 59535, 36750, 5586, 196, 1, 1, 2040, 84700, 435120, 486570, 148176, 12936, 288, 1, 1, 4599, 335880, 2864820, 5358150, 2876202, 493920, 27000, 405, 1

Offset: 0

Author

Geoffrey Critzer, Jun 24 2023

Keywords

• nonn
• tabl

Comments

Let H_f denote the H-class in the semigroup of partial transformations containing f. Then H_f contains an idempotent iff the image of f is a transversal for the kernel of f.

Let H_f ~ H_g iff the image of f is contained in the image of g and the kernel of f is more coarse than the kernel of g. Then ~ is a partial order on the H-classes, hence a preorder (quasi-order) on the semigroup. The poset is isomorphic to the Segre product of the Boolean lattice of rank n and the partition lattice of [n+1].

Examples

			Triangle begins:
 1;
 1,   1;
 1,   6,   1;
 1,  21,  18,   1;
 1,  60, 150,  40,  1;
 1, 155, 900, 650, 75, 1;
 ...
		

References

• O. Ganyushkin and V. Mazorchuk, Classical Finite Transformation Semigroups, 2009, Chapter 4.4 - 4.6.

Links

• Wikipedia, Green's relations
• Wikipedia, Transversal (combinatorics)

Crossrefs

Columns k=0-1 give: A000012, A066524.

Row sums give A134055(n+1).

T(n,n-1) gives A002411.

Cf. A000169, A007318, A008277, A090683, A101818.

Programs

Maple

T:= (n, k)-> binomial(n, k)*Stirling2(n+1, k+1):
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Jun 24 2023

Mathematica

Table[Table[Binomial[n, k] StirlingS2[n + 1, k + 1], {k, 0, n}], {n,0, 5}] // Grid

Formula

T(n,k) = A007318(n,k)*A008277(n+1,k+1).

Sum_{k=0..n} T(n,k)*k! = (n+1)^n = A000169(n+1).

T(n,1) = A101818(n,1) = A066524(n) = n*(2^n - 1). (Every partial function of rank 1 is idempotent.)