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,5

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<=j<i} f(j). - R. J. Mathar, Mar 18 2016

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.

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

Example

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;

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

Crossrefs

Cf. A008277, A000110, A271466.

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

Sequence in context: A063415 A098977 A247311 * A218580 A259697 A330664

Adjacent sequences: A113544 A113545 A113546 * A113548 A113549 A113550

Keyword

nonn,tabl

Author

Franklin T. Adams-Watters, Jan 13 2006

Status

approved