# Help understanding solution to growth of partition function

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}$?)

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.