4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Have you done any experiments with small $n$ to get a feel for what goes on here? I suspect it converges to $(1/3,1/3,1/3)$. $\endgroup$ – Gerry Myerson Aug 9 '13 at 0:01
  • $\begingroup$ The maximum value (but not the partition giving rise to the maximum value) is tabulated at oeis.org/A102462 --- there are also links to related matters (but no answer to the current question). $\endgroup$ – Gerry Myerson Aug 9 '13 at 3:51
  • 1
    $\begingroup$ @Gerry Myerson: I actually suspect the answer is $(1/4, 1/8, 1/16,.....)$. With some dubious analysis which involves substituting factorials by their stirling approximations, I get that the number of ordered partitions that this particular unordered partition gives rise to is $\approx c2^n$, where $c$ is a constant. This is pretty big! $\endgroup$ – VSJ Aug 9 '13 at 4:08
  • $\begingroup$ You could well be right. Anyway, I retract my $(1/3,1/3,1/3)$ suggestion, which was based partly on misunderstanding the question, and partly on misinterpreting some calculations I did. $\endgroup$ – Gerry Myerson Aug 9 '13 at 5:44
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Let me go through this carefully, looks promising! $\endgroup$ – VSJ Aug 11 '13 at 23:48
  • $\begingroup$ Very nice proof :) $\endgroup$ – VSJ Aug 12 '13 at 18:40
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is how I arrived at guessing the answer too, but couldn't get past those roadblocks to get a solid proof. $\endgroup$ – VSJ Aug 11 '13 at 23:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.