A101818 -id:A101818 - cp's OEIS frontend

A101817 Triangle read by rows: T(n,h) = number of functions f:{1,2,...,n}->{1,2,...,n} such that |Image(f)|=h; h=1,2,...,n, n=1,2,3,... . Essentially A090657, but without zeros.

1, 2, 2, 3, 18, 6, 4, 84, 144, 24, 5, 300, 1500, 1200, 120, 6, 930, 10800, 23400, 10800, 720, 7, 2646, 63210, 294000, 352800, 105840, 5040, 8, 7112, 324576, 2857680, 7056000, 5362560, 1128960, 40320, 9, 18360, 1524600, 23496480, 105099120

Offset: 1

Clark Kimberling, Dec 17 2004

Row sums = n^n. T(n,1) = n, T(n,n) = n!.

			First rows:
1;
2,   2;
3,  18,   6;
4,  84, 144,  24;

H. Picquet, Note #124, L'Intermédiaire des Mathématiciens, 1 (1894), pp. 125-127. - N. J. A. Sloane, Feb 28 2022

Cf. A090657, A048993, A101818, A101819, A101821, A288312.

Table[Table[StirlingS2[n, k] Binomial[n, k] k!, {k, 1, n}], {n, 1, 8}] // Grid

T(n, h) = C(n, h)*U(n, h), where U(n, h) is the array in A019538. Thus T(n, h) = C(n, h)*h!*S(n, h), where S(n, h) is a Stirling number of the second kind (given by A048993 with zeros removed).

T(2n,n) = A288312(n). - Alois P. Heinz, Jun 07 2017

A181415 Irregular triangle a(n,k) = A049009(n,k)/n, read by rows 1<=k<=A000041(n).

Original entry on oeis.org

1, 1, 1, 1, 6, 2, 1, 12, 9, 36, 6, 1, 20, 40, 120, 180, 240, 24, 1, 30, 75, 50, 300, 1200, 300, 1200, 2700, 1800, 120, 1, 42, 126, 210, 630, 3150, 2100, 3150, 4200, 25200, 12600, 12600, 37800, 15120, 720, 1, 56, 196, 392, 245, 1176, 7056, 11760, 8820, 11760, 11760, 88200

Offset: 1

Alford Arnold, Oct 20 2010

			Row three is calculated as follows:
( 3 18 6) divided by (3 3 3) yielding (1 6 2)
1;
1,1;
1,6,2;
1,12,9,36,6;
1,20,40,120,180,240,24;
1,30,75,50,300,1200,300,1200,2700,1800,120;
1,42,126,210,630,3150,2100,3150,4200,25200,12600,12600,37800,15120,720;

Cf. A000169 (row sums), A000081 (unlabeled rooted trees) A179438 (a similar refinement), A054589, A135278, A019538, A101817, A101818

Sum_{k=1.. A000041(n)} a(n,k) = A000169(n). (Row sums)

a(n,k) = A098546(n,k) *A049019(n,k) /n. - Compare with the formula in A101818.

Edited by R. J. Mathar, May 17 2016

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.

Original entry on oeis.org

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

Geoffrey Critzer, Jun 24 2023

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].

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

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

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

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.

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

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

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

cp's OEIS Frontend

A101817 Triangle read by rows: T(n,h) = number of functions f:{1,2,...,n}->{1,2,...,n} such that |Image(f)|=h; h=1,2,...,n, n=1,2,3,... . Essentially A090657, but without zeros.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

Formula

A181415 Irregular triangle a(n,k) = A049009(n,k)/n, read by rows 1<=k<=A000041(n).

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula