A102356 - OEIS

%I #27 Oct 03 2014 18:23:34

%S 1,1,1,3,6,15,60,210,840,3780,12600,69300,415800,2702700,12612600,

%T 94594500,756756000,4288284000,38594556000,244432188000,1833241410000,

%U 17110253160000,141159588570000,1298668214844000,10389345718752000,108222351237000000,1125512452864800000

%N 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 a(n) is the maximum value in row n of A080575.

%H Alois P. Heinz, <a href="/A102356/b102356.txt">Table of n, a(n) for n = 0..300</a>

%H 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 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 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p        max(seq(b(n-i*j, i-1) *n!/i!^j/(n-i*j)!/j!, j=0..n/i))))

%p     end:

%p a:= n-> b(n, n):

%p seq(a(n), n=0..40);  # _Alois P. Heinz_, Apr 13 2012

%t sp[l_] := (Total[l])!/(Apply[Times, Map[ #! &, l]]*Apply[Times, Map[Count[l, # ]! &, Range[Max[l]]]]) a[n_] := Max[Map[sp, Partitions[n]]]

%t 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 Cf. A080575, A102456.

%K nonn

%O 0,4

%A _Dan Drake_, Feb 21 2005

%E More terms from _Alois P. Heinz_, Oct 13 2011.

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