A102356 Problem 66 in Knuth's Art of Computer Programming, vol. 4, section 7.2.1.5 asks which integer partition of n produces the most set partitions. The n-th term of this sequence is the number of set partitions produced by that integer partition.

1, 1, 1, 3, 6, 15, 60, 210, 840, 3780, 12600, 69300, 415800, 2702700, 12612600, 94594500, 756756000, 4288284000, 38594556000, 244432188000, 1833241410000, 17110253160000, 141159588570000, 1298668214844000, 10389345718752000, 108222351237000000, 1125512452864800000

Offset: 0

Author

Dan Drake, Feb 21 2005

Keywords

• nonn

Comments

a(n) is the maximum value in row n of A080575.

Examples

			a(4) = 6 because there are 6 set partitions of type {2,1,1}, namely 12/3/4, 13/2/4, 1/23/4, 14/2/3, 1/24/3, 1/2/34; all other integer partitions of 4 produce fewer set partitions.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..300
• D. E. Knuth, The Art of Computer Programming, vol. 4. See Section 7.2.1.5, Problem 66, pages 439 and 778.

Crossrefs

Cf. A080575, A102456.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
       max(seq(b(n-i*j, i-1) *n!/i!^j/(n-i*j)!/j!, j=0..n/i))))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..40);  # Alois P. Heinz, Apr 13 2012

Mathematica

sp[l_] := (Total[l])!/(Apply[Times, Map[ #! &, l]]*Apply[Times, Map[Count[l, # ]! &, Range[Max[l]]]]) a[n_] := Max[Map[sp, Partitions[n]]]
b[0, ] = 1; b[, ?NonPositive] = 0; b[n, i_] := b[n, i] = Max[Table[ b[n - i*j, i-1]*n!/i!^j/(n - i*j)!/j!, {j, 0, n/i}]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jan 24 2014, after Alois P. Heinz *)

Extensions

More terms from Alois P. Heinz, Oct 13 2011.

Typo in definition corrected by Klaus Leeb, Apr 30 2014.