Which unordered partition of $n$ gives rise to the largest number of ordered partitions?

Question

A quick look at the wikipedia article on partitions of $n \in \mathbb{N}$ shows that the number of ordered partitions is $2^{n-1}$, and the number of unordered partitions is asymptotically $ \sim \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}}$.

We can write an unordered partition of $n$ as an $n$ length vector $[a_1, a_2, ..., a_n]$ where $a_i$ is the number of parts of size $i$. For this to be a valid partition of $n$, we must have $$\sum_{i=1}^n ia_i = n.$$ Each such unordered partition gives rise to $\frac{(\sum a_i) !}{\Pi a_i!}$ ordered partitions of $n$. For a given $n$, let $\mbox{argmax}_a \frac{(\sum a_i) !}{\Pi a_i!} = a^*(n)$, where the maximum is taken over all valid unordered partitions of $a$ of $n$.

My question is, as $n \to \infty$ does the vector $\frac{1}{n}[a^*_1, a^*_2, ..., a^*_n]$ converge in some sense?

If so, this would mean that the unordered partitions that lead to the largest number of ordered partitions tend to have a fixed fraction of size $i$ blocks for each $i$.

I'd asked this earlier here but did not get much of a response. Any inputs welcome!

Answer 1

We will prove that $\lim_{n\to\infty} a_i^*/n = 1/2^{i+1}$.

Also let $s_*=\sum a_i^*$

To do this, note that if $a^*$ is optimal, adding $1$ to $a_i$ and $a_j$ and subtracting one from $a_{i+j}$ must reduce the number of unordered partitions, so

$$ \frac{ (s^*+1) (a_{i+j} ^*)} { (a_i^*+1)(a_j^*+1) } \leq 1$$

or if $j=i$,

$$ \frac{ (s^*+1) (a_{2i}^* )} { (a_i^*+1)(a_i^*+2) } \leq 1$$

Similarly, subtracting one from $a_i$ and $a_j$ and adding one to $a_{i+j}$ must also reduce the number of unordered partitions, so

$$ \frac{ a_i^* a_j^*} { s^* (a_{i+j}^*+1)} \leq 1$$

or if $j=i$,

$$ \frac{ a_i^* (a_i^*-1)} { s^* (a_{2i}^*+1)} \leq 1$$

Using these inequalities, one could probably give explicit bounds for the $a_i^*$ and use that to determine the convergence rate, but that sounds messy, so we can prove convergence using soft methods instead.

If $\lim_{n\to\infty} a_1^*/s_*=1/2$, we can conclude that $\lim_{n\to\infty} a_i^*/s_*=1/2^i$ $n_*/s_*= \sum_i i a_i^*/s_i^*$, so if we can interchange the sum and the limit we get $n_*/s_*=2$ and the desired result.

Conversely, if $\lim_{n\to\infty} a_1^*/s_*$ does not exist or exists and isn't $1/2$, a subsequence exists with limit $x\neq 1/2$, so by these inequalities the limit of $a_i^*/s_*= x^i$ Since $1 = \sum_i a_i^*/s_i^*$, if we can interchange the limits we get $1=x/(1-x)$ and $x=1/2$ and a contradiction.

So the key step is to interchange the sum and the limit. We will do this using the Dominated Convergence theorem and the estimate $a_i^*/s_* = O(1/i^3)$, which makes both sums converge.

We obtain the estimate as follows: Setting $j=1$ in the first inequality, we see that $a_{i+1}^*< a_i^*+1$, so $a_{i+1}^* \leq a_i^*$, so the function is nonincreasining Thus $a_i^* \leq s^*/i$. So

$$a_{2i}^* \leq \frac{(s^*/i+1) (s^*/i+2)}{(s^*+1)}$$

and

$$a_{3i}^* \leq \frac{ (s^*/i+1) (s^*/i+2)(s^*/i+3)}{ (s^*+1) (s^*+2) }$$

Also $a_{3i}^*=0$ unless $s^* \geq 3i$. So $a_{3i}^*/s^*= O(1/i^3)+O(1/i^2s^*)+O(1/is^{*2})+O(1/s^{*3})=O(1/i^3)$.

Then the same holds for every $a_i$ and we have the desired result.

---

To work on this problem, it is helpful to have a method to generate a random ordered partition. This is very easy - flip $n$ coins, and divide them into streaks. So if the flips are HTTHHHTHTTTTH, the corresponding ordered partition is $1+2+3+1+4+1$, and the corresponding unordered partition is $1+1+1+2+3+4$. Since each ordered partition is equally likely to occur (it comes from exactly two sequences of coin flips), this question is equivalent to the question: Which unordered partition is most likely to occur, and what is its probability of occurrence?

The Central Limit Theorem shows that the probability of getting a given $a_1,a_2,\dots, a_k$ is $O(1/n^{k/2})$, so the probability of getting a given unordered partition must be $O(1/n^{k/2})$ for all $k$, so the number of ordered partitions corresponding to a given unordered partition must be $O(2^n/n^{k/2})$ for all $k$.

Answer 2

Some heuristic way to the answer, related to well-known properties of the entropy of probability distributions, is loosely as follows.

Set $m=\sum_i a_i$ and $p_i=a_i/m$, so that $p=(p_i)_{i\ge1}$ is a probability distribution with expectation $\langle p\rangle=n/m\ge 1$.

Then $$\ln\frac{(\sum a_i) !}{\Pi a_i!}\simeq n\frac{\mathcal H(p)}{\langle p\rangle},$$ in which $\mathcal H(p)=-\sum_i p_i\ln(p_i)$ is the entropy of $p$. For a given expectation $\langle p\rangle=1/\lambda\ge 1$, the maximal entropy is that of the geometric distribution $\Lambda_i=(1-\lambda)^{i-1}\lambda$, namely $$\mathcal H(\Lambda)=-\ln\lambda+(1-\tfrac1\lambda)\ln(1-\lambda),$$ leading to $$\frac{\mathcal H(\Lambda)}{\langle \Lambda\rangle}=-(\lambda\ln\lambda+(1-\lambda)\ln(1-\lambda))\le\ln 2$$ with equality when $\lambda=1/2$, and when $a_i/n=p_i m/n=(1-\lambda)^{i-1}\lambda^{2}=2^{-i-1}$.

Roadblocks are:

1. the accuracy of the approximation by $n\,\tfrac{\mathcal H(p)}{\langle p\rangle}$,

2. the fact that one can achieve $\forall i\ge 1, a_i/n\simeq 2^{-i-1}$ only approximately,

3. ...