A102456 -id:A102456 - 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.

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

Dan Drake, Feb 21 2005

nonn

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

			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.

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.

Cf. A080575, A102456.

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

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

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

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

A255404 Number of different integer partitions of n that produce the maximum number of set partitions for a set of cardinality n.

Original entry on oeis.org

1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 4, 3, 2, 1, 4, 2, 1, 2, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 4, 6, 4, 1, 2, 1, 5, 5, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 5, 2, 2, 1, 1, 4, 1, 1, 2, 3, 1, 8, 2, 1, 1, 3, 1, 1, 1, 3, 1, 1, 3, 1, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 3, 2, 1, 1, 1, 1

Offset: 0

Andrei Cretu, Feb 22 2015

nonn

If n=Sum_i[n_i], the number of set partitions can be written as sp=n!/Prod_i,j(n_i!m_j!) where m_j is the multiplicity of the integer j in the n_i's. For certain integers, this number is maximized by more than one partition.

			For n=9, {1,1,2,2,3} maximizes the number of set partitions, while for n=10, this number is maximized by {1,2,3,4}, {1,1,2,3,3}, {1,2,2,2,3} and {1,1,1,2,2,3}.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A102356, A102456.

Prod[l_] := Apply[Times, Map[#! &, l]]*
    Apply[Times, Map[Count[l, #]! &, Range[Max[Length[l]]]]]
b[n_] := (Min[Map[Prod, IntegerPartitions[n]]])
a[n_] := Count[Map[Prod, IntegerPartitions[n]], b[n]]
Table[a[n], {n, 0, 20}] (* after A102356 *)

More terms from Alois P. Heinz, Feb 25 2015

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions