cp's OEIS Frontend

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.

%I A102356 #27 Oct 03 2014 18:23:34
%S A102356 1,1,1,3,6,15,60,210,840,3780,12600,69300,415800,2702700,12612600,
%T A102356 94594500,756756000,4288284000,38594556000,244432188000,1833241410000,
%U A102356 17110253160000,141159588570000,1298668214844000,10389345718752000,108222351237000000,1125512452864800000
%N 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.
%C A102356 a(n) is the maximum value in row n of A080575.
%H A102356 Alois P. Heinz, <a href="/A102356/b102356.txt">Table of n, a(n) for n = 0..300</a>
%H A102356 D. E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/taocp.html#vol4">The Art of Computer Programming, vol. 4</a>. See Section 7.2.1.5, Problem 66, pages 439 and 778.
%e A102356 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.
%p A102356 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A102356        max(seq(b(n-i*j, i-1) *n!/i!^j/(n-i*j)!/j!, j=0..n/i))))
%p A102356     end:
%p A102356 a:= n-> b(n, n):
%p A102356 seq(a(n), n=0..40);  # _Alois P. Heinz_, Apr 13 2012
%t A102356 sp[l_] := (Total[l])!/(Apply[Times, Map[ #! &, l]]*Apply[Times, Map[Count[l, # ]! &, Range[Max[l]]]]) a[n_] := Max[Map[sp, Partitions[n]]]
%t A102356 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_ *)
%Y A102356 Cf. A080575, A102456.
%K A102356 nonn
%O A102356 0,4
%A A102356 _Dan Drake_, Feb 21 2005
%E A102356 More terms from _Alois P. Heinz_, Oct 13 2011.
%E A102356 Typo in definition corrected by Klaus Leeb, Apr 30 2014.