1
$\begingroup$

The partition function $p(n)$ counts the number of ways an integer can be expressed as a sum. For example, $p(4)=5$ as $$4=3+1=2+2=2+1+1=1+1+1+1$$ Hardy and Ramanujan were able to develop a converging series that provides us with an asymptotic expression for the partition function. However, it is quite complicated and therefore do not provide much insight regarding the ways in which this function behaves. Does there exist a simpler upper and lower bound for the partition function? If so, what are these bounds?

$\endgroup$
  • 1
    $\begingroup$ actually that's not quite true, the fact that there's an asymptotic expression, tells you a LOT about how the function behaves, and its boundedness. For more info have a look at math.stackexchange.com/questions/264321/… $\endgroup$ – Ahmed Masud Jun 16 '16 at 21:49
  • 1
    $\begingroup$ "...*provides us with an asymptotic expression for the partition function. However, it is quite complicated*..." I'm sorry, but how is $\frac{e^{\pi\sqrt{2n/3}}}{4n\sqrt{3}}$ overly complicated? $\endgroup$ – JMoravitz Jun 16 '16 at 21:52
  • $\begingroup$ I was referring to the infinite sum developed by Hardy and Ramanujan $\endgroup$ – Romain S Jun 16 '16 at 21:53
0
$\begingroup$

Hint

We know $p_k(n)$( partitions of $n$ into exactly $k$ parts) equals $$x_1+x_2+\cdots +x_k=n\quad ,\quad x_i\in \mathbb{N}$$

  1. let $m=n+\left( \begin{matrix} k \\ 2 \\ \end{matrix} \right)$ and prove the number of distinct partition of $m$ into exactly $k$ distinct parts equals $p_k(n)$
  2. show $$\frac{1}{k!}\left( \begin{matrix} n-1 \\ k-1 \\ \end{matrix} \right)\le {{p}_{k}}(n)\le \frac{1}{k!}\left( \begin{matrix} m-1 \\ k-1 \\ \end{matrix} \right)$$
  3. Apply sigma notation for $k=1,2,\cdots n$
$\endgroup$

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.