Which integer partitions correspond to the most set partitions?

Question

Which integer partitions of n correspond to the most distinct set partitions?

For small n where it is feasible to calculate these values for every integer partition and compare, this is a straightforward exercise with the multinomial function...but beyond that range, what constraints can be put on the form of the integer partitions realizing that maximum?

For example, the five integer partitions of n=4 correspond to the block sizes of the fifteen set partitions like so:

4    [1234]
31   [123,4],[124,3],[134,2],[234,1]
22   [12,34],]13,24],[14,23]
211  [12,3,4],[13,2,4],[14,2,3],[23,1,4],[24,1,3],[34,1,2]
1111 [1,2,3,4]

Thus 211 is the integer partition yielding the most set partitions for n=4.

The optimal partition is not always unique, and its maximum part size doesn't even increase monotonically, so rather than relying on empirical guesswork I was wondering if the underlying patterns had been identified previously, perhaps under a different name.

    n   max set partitions           int partition
    1   1                            (1,)
    3   3                            (2, 1)
    4   6                            (2, 1, 1)
    5   15                           (2, 2, 1)
    6   60                           (3, 2, 1)
    7   210                          (3, 2, 1, 1)
    8   840                          (3, 2, 2, 1)
    9   3780                         (3, 2, 2, 1, 1)
    13  2702700                      (4, 3, 2, 2, 1, 1)
    16  756756000                    (4, 3, 3, 2, 2, 1, 1)
    18  38594556000                  (4, 3, 3, 2, 2, 2, 1, 1)
    21  17110253160000               (4, 3, 3, 3, 2, 2, 2, 1, 1)
    22  141159588570000              (4, 4, 3, 3, 2, 2, 2, 1, 1)
    23  1298668214844000             (5, 4, 3, 3, 2, 2, 2, 1, 1)
    25  108222351237000000           (4, 4, 3, 3, 3, 2, 2, 2, 1, 1)
    26  1125512452864800000          (5, 4, 3, 3, 3, 2, 2, 2, 1, 1)
    27  11395813585256100000         (5, 4, 4, 3, 3, 2, 2, 2, 1, 1)
    29  1156675078903494150000       (5, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1)
    30  15422334385379922000000      (5, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1)
    31  159364121982259194000000     (5, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1)

Equivalently, which monomial/s of the exponential Bell polynomials for a given n have the largest coefficient, as n increases?

Answer 1

Since you're talking in the comments about hill-climbing, I interpret that what you're interested is in calculating the partitions.

If we define $f(n, k)$ to be the maximum of the set partition counts over partitions of $n$ into parts of at most $k$ then we can compute it recursively: $$f(n, k) = \begin{cases} \max_{0 \le j \le n/k} \frac{n!}{k!^j j! (n-jk)!} f(n-jk, k-1) & \textrm{if }n > 0 \\ 1 & \textrm{if } k = n = 0 \\ 0 & \textrm{otherwise} \end{cases}$$

This can easily be made constructive. E.g. Python code:

from functools import lru_cache


@lru_cache(maxsize=None)
def binom(n, k):
    if k < 0 or k > n: return 0
    if k == 0 or k == n: return 1
    rv = 1
    for i in range(k):
        rv *= n - i
        rv //= 1 + i
    return rv


@lru_cache(maxsize=None)
def biggest_partitions(n, k):
    """Each partition of n into parts of at most k corresponds to a number of set partitions. This gives the largest of those numbers."""
    if k < 0: return 0, set()
    if k == 0: return int(n == 0), set([()])

    # If we have j parts of size k, we choose jk of n to be those parts; then we have n!/(k!^j j! (n-jk!)) times most_partitions(n - jk, k - 1)
    best_score = 0
    best = set()
    lhs = 1
    for j in range(n // k + 1):
        score, examples = biggest_partitions(n - j * k, k - 1)
        score *= lhs
        if score >= best_score:
            if score > best_score:
                best = set()
            for example in examples:
                best.add(tuple([k] * j + list(example)))
            best_score = score
        lhs = lhs * binom(n - j * k, k) // (j + 1)
    return best_score, best


def A102356_explicit(n):
    if n == 0: return [()]

    best_score = 0
    best = set()
    for k in range(1, n+1):
        score, examples = biggest_partitions(n, k)
        if score >= best_score:
            if score > best_score:
                best = set()
            for example in examples:
                best.add(example)
    return sorted(best)


if __name__ == "__main__":
    print(A102356_explicit(300))

Try it online.