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

  • $\begingroup$ The values are given in OEIS A102462, but no references or general formula are given for the values. $\endgroup$ – Ross Millikan Jul 25 '13 at 19:21
  • $\begingroup$ Thanks Ross. I'm more interested in the how the partition looks, rather than what values it gives, that too asymptotically as $n \to \infty$. $\endgroup$ – VSJ Jul 25 '13 at 19:27
  • 1
    $\begingroup$ It will clearly have more small parts than large parts. I would guess for large $n$ there will be a rule for the rate of decrease, but whether it is polynomial or exponential or something else I have no idea. $\endgroup$ – Ross Millikan Jul 25 '13 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.