I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated.

Question Let the number of partitions be given by the function $p(n)$, i.e. the number of ways of writing the integer $n$ as a sum of positive integers. Prove that that if $g$ is any polynomial function in $n$, then there exists an integer $N$ such that $g(n)<p(n)$ for all $n>N$. Do not use the asymptotic Hardy-Ramanujan formula.

Provided Proof.

  1. Enough to show $n^a<p(n)$ for fixed positive integer $a$. (This is just saying that we want to show $p(n)$ grows faster than any degree polynomial of $n$, right?)

  2. We have that $(i_1,i_2,\ldots,i_{a+1},1^{n-i_1-\cdots -i_{a+1}})$ is a partition of $n$ as long as $i_{a+1}\leq i_a\leq \cdots i_1 \leq \lfloor\frac{n}{a+1}\rfloor$. (I really don't understand this step. What is this partition? Of the coefficients or terms of polynomial $p(n)$? And how do we know this is $\leq \lfloor\frac{n}{a+1}\rfloor$?)

  3. The number of partitions $n$ of this form is multiset binomial coefficient $$\left(\dbinom{\lfloor \frac{n}{a+1}\rfloor}{a+1}\right)=\frac{\lfloor\frac{n}{a+1}\rfloor(\lfloor\frac{n}{a+1}\rfloor+1)\cdots(\lfloor\frac{n}{a+1}\rfloor+a-1)}{(a+1)!}$$ (I'm assuming that if I can understand (2.) then I can understand this line)

  4. This means $p(n)>\left(\binom{\lfloor \frac{n}{a+1}\rfloor}{a+1}\right)$ for all $n>0$.

  5. Since $a$ is constant, the given fraction grows with order $n^{a+1}$, which means $p(n)>n^a$ for $n$ sufficiently large. (Why does it grow with order $n^{a+1}$?)

Thanks all again in advance!

  1. A polynomial of degree $a$ is $O(n^a)$. If $p(n)$ is eventually greater than $n^{a+1}$, then $p(n)$ is not $O(n^a)$ and therefore is not bounded by any polynomial of degree $a$. Since this holds for all $a$, $p(n)$ is not bounded by any polynomial.

  2. Let $\langle i_1,\ldots,i_{a+1}\rangle$ be any non-increasing sequence of positive integers such that $a_1\le\left\lfloor\frac{n}{a+1}\right\rfloor$. Since $i_k\le i_1\le\left\lfloor\frac{n}{a+1}\right\rfloor\le\frac{n}{a+1}$ for $k=1,\ldots,a+1$, $$\sum_{k=1}^{a+1}i_k\le(a+1)\cdot\frac{n}{a+1}=n\;.$$ Let $s=\sum_{k=1}^{a+1}i_k$; then $n-s\ge 0$. If $s=0$, then $\langle i_1,\ldots,i_{a+1}\rangle$ is a partition of $n$ into $a+1$ parts. If $s>0$, we’ll fill that out with $n-s$ parts of size $1$ to make the partition $$\langle i_1,\ldots,i_{a+1},\underbrace{1,\ldots,1}_{n-s}\rangle\;,$$ abbreviated in your proof as $\langle i_1,\ldots,i_{a+1},1^{n-s}\rangle$. We’re going to count the partitions of $n$ that have this form for some such sequence $\langle i_1,\ldots,i_{a+1}\rangle$. We know that $s\le\left\lfloor\frac{n}{a+1}\right\rfloor$ because we only consider sequences $\langle i_1,\ldots,i_{a+1}\rangle$ for which that’s the case.

  3. Think of the sequence $\langle i_1,\ldots,i_{a+1}\rangle$ as a multiset of $a+1$ elements $i_1,\ldots,i_{a+1}$, each of which is a positive integer no larger than $\left\lfloor\frac{n}{a+1}\right\rfloor$. The set of all such sequences can in this way be identified with the set of all multisets of cardinality $a+1$ chosen from the set $\left\{1,\ldots,\left\lfloor\frac{n}{a+1}\right\rfloor\right\}$, and there are $$\left(\!\!\binom{\left\lfloor\frac{n}{a+1}\right\rfloor}{a+1}\!\!\right)=\frac{\left\lfloor\frac{n}{a+1}\right\rfloor^{\overline{a+1}}}{(a+1)!}=\binom{\left\lfloor\frac{n}{a+1}\right\rfloor+a}{a+1}\tag{1}$$ of those. (There’s an error in your proof at this point: that ugly numerator should have $a+1$ factors, not $a$, so the last one should be $\left\lfloor\frac{n}{a+1}\right\rfloor+a$.)

  4. Parts (2) and (3) showed how to construct $\left(\!\!\binom{\left\lfloor\frac{n}{a+1}\right\rfloor}{a+1}\!\!\right)$ partitions of $n$, so $$p(n)\ge\left(\!\!\binom{\left\lfloor\frac{n}{a+1}\right\rfloor}{a+1}\!\!\right)\;.$$ To justify the strict inequality in your proof, we may simply note that we counted only partitions with at least $a+1$ parts.

  5. Each factor in the numerator of $(1)$ is at least $\left\lfloor\frac{n}{a+1}\right\rfloor$, so $$p(n)>\frac1{(a+1)!}\left(\left\lfloor\frac{n}{a+1}\right\rfloor\right)^{a+1}\ge\frac1{(a+1)!}\left(\frac{n}{a+1}-1\right)^{a+1}\tag{2}\;.$$ The righthand side of $(2)$ is a polynomial in $n$ of degree $a+1$, so it’s $\Theta(n^{a+1})$, i.e., grows with order $a+1$.


Well, binomial coefficient ${n}\choose{k}$ grows as polynomial of degree $k$ when $k$ is a fixed number so that completes the proof.

Alternatively -- a very simple argument proves that $p(n) > 2^{\lfloor\sqrt{n}\rfloor-1}$ (take any subset $\{a_1,a_2,...a_k\}$ in $S=\{1,2,3,...,m\}$ where $m=\lfloor\sqrt{n}\rfloor-1$ and construct partition $[a_1,a_2,...,a_k,n-\sum a_i]$ -- this gives you an injection of the set of all subsets of $S$ into set of all partitions of $n$). Since function $f(n) = 2^{\lfloor\sqrt{n}\rfloor-1}$ grows "faster" than any polynomial (use logarithm to prove that) you get your second proof.


Your Answer

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

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