A113547 Triangle read by rows: number of labeled partitions of n with maximin m.

1, 1, 1, 1, 2, 2, 1, 4, 5, 5, 1, 8, 13, 15, 15, 1, 16, 35, 47, 52, 52, 1, 32, 97, 153, 188, 203, 203, 1, 64, 275, 515, 706, 825, 877, 877, 1, 128, 793, 1785, 2744, 3479, 3937, 4140, 4140, 1, 256, 2315, 6347, 11002, 15177, 18313, 20270, 21147, 21147, 1, 512, 6817, 23073, 45368, 68303, 88033, 102678, 111835, 115975, 115975

Offset: 1

Author

Franklin T. Adams-Watters, Jan 13 2006

Keywords

• nonn
• tabl

Comments

The maximin of a partition is the maximum over all parts of the minimum label in each part. If the rows are reversed, the result is the number of partitions of n with minimax m.

The number of restricted growth functions of length n where the maximum appears first at position m. The RGF's are defined here as f(1)=1 and f(i) <=1+max_{1<=jR. J. Mathar, Mar 18 2016

Examples

			Maximin [123]=max(1)=1, maximin [12|3]=max(1,3)=3, maximin [13|2]=max(1,2)=2, maximin [1|23]=max(1,2)=2 and maximin [1|2|3]=max(1,2,3)=3, so for n=3 the multiset of maximins is {1,2,2,3,3}, making the 3rd line 1,2,2.
1;
1,  1;
1,  2,   2;
1,  4,   5,   5;
1,  8,  13,  15,  15;
1, 16,  35,  47,  52,  52;
1, 32,  97, 153, 188, 203, 203;
1, 64, 275, 515, 706, 825, 877, 877;
		

Links

• G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
• Todd Tichenor, A note on graph compositions and their connection to minimax of set partitions, arXiv:1709.00393 [math.CO], 2017.

Crossrefs

Cf. A008277, A000110, A271466.

A362924 and A362925 are other versions of this triangle. - N. J. A. Sloane, Aug 10 2023

Programs

Maple

A113547 := proc(n,m)
    add(combinat[stirling2](m-1,k-1)*k^(n-m),k=1..m) ;
end proc:
seq(seq( A113547(n,m),m=1..n),n=1..10) ; # R. J. Mathar, Mar 13 2016

Mathematica

T[n_, n_] := BellB[n - 1]; T[n_, n_ - 1] := BellB[n - 1]; T[n_, n_ - 2] := BellB[n - 1] - BellB[n - 3]; T[n_, m_] := Sum[StirlingS2[m - 1, k - 1]*k^(n - m), {k, 1, m}]; Table[T[n, m], {n, 1, 5}, {m, 1, n}] (* G. C. Greubel, May 06 2017 *)

Formula

T(n, m) = Sum_{k=1..m} S2(m-1, k-1)*k^(n-m), where S2 is the Stirling numbers of the second kind (A008277). T(n, n)=T(n, n-1)=B(n-1), where B is the Bell numbers (A000110). T(n, n-2)=B(n-1)-B(n-3).

Conjectures: T(n,3) = A007689(n-3). T(n,4) = 2^(n-4)+3^(n-3)+4^(n-4).- R. J. Mathar, Mar 13 2016