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$.