A quick look at the [wikipedia article](http://en.wikipedia.org/wiki/Partition_%28number_theory%29) 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](https://math.stackexchange.com/questions/452180/which-unordered-partition-of-n-gives-rise-to-the-largest-number-of-ordered-par) but did not get much of a response. Any inputs welcome!



Which unordered partition of $n$ gives rise to the largest number of ordered partitions?
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$.


