VOOZH about

URL: https://oeis.org/A102356

⇱ A102356 - OEIS

login
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.
8
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,4
COMMENTS
a(n) is the maximum value in row n of A080575.
LINKS
D. E. Knuth, The Art of Computer Programming, vol. 4. See Section 7.2.1.5, Problem 66, pages 439 and 778.
EXAMPLE
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.
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 *)
CROSSREFS
Sequence in context: A327437 A267552 A241269 * A208662 A102936 A009192
KEYWORD
nonn
AUTHOR
Dan Drake, Feb 21 2005
EXTENSIONS
More terms from Alois P. Heinz, Oct 13 2011.
Typo in definition corrected by Klaus Leeb, Apr 30 2014.
STATUS
approved