The proof for the leftside inequality: Handle $ n = 2,3,4$ separately. Let now $ n\ge5$. Let $ m = [\sqrt n]$ and $ V = \{1,2,\ldots,m\}$. For a finite $ X\subset Z$ let $ \displaystyle f(X) = \sum_{x\in X}x$. We prove that for $ n\ge 5$ we have $ e = f(V) + m\le n$. For $ n = 5,6,7,8$ $ m = 2$ and the inequality is trivial. Assume $ n\ge9$. Then $ e = \dfrac{m^2 + m}2 + m\le\dfrac{n + 3\sqrt n}2\le n$. Moreover equality takes place iff $ n = 5$ or $ n = 9$. Thus for any subset $ A\subset V$, $ A = \{a_1,a_2,\ldots,a_k\}$ we can associate the partition of $ n$: $ (a_1,\ldots,a_k,n - f(A))$ with $ n - f(A) > a_i$, for any $ i$ if $ A\neq V$ or maybe $ n - f(A) = m$ if $ A = V$. It is clear that this is an injective map. Since there are $ 2^m$ different subsets of $ V$, we get $ 2^{[\sqrt n]}\le p(n)$. I'll think for a normal proof of the rightside inequality. For now, here's a strange proof for it: Handle $ n = 2$ separately. We use the following strong bound for $ p(n)$ for $ n > 2$: $ \boxed{p(n) < \dfrac{\pi}{\sqrt {6(n - 1)}}e^{\pi\sqrt {\frac {2n}3}}}$. Now for $ n\ge3$ we easily have $ \dfrac{\pi}{\sqrt {6(n - 1)}} < 1$, so it is sufficient to prove $ e^{\pi\sqrt {\frac {2n}3}} < n^3{[\sqrt n]}$, or $ e^{\pi\sqrt {\frac23}} < n^3$. Direct calculations show that ${ \pi\sqrt {\dfrac23}} < 3$, and since $ e < 3\le n$, the desired inequality holds. I'll post tomorrow the proof for the stated bound for $ p(n)$. If anyone does that before me, I'd be glad . I gotta go now.

As I promised, here's the proof of the following fact: If $ p(n)$ is the number of partitions of $ n$ as a sum of several positive integers then $ \boxed{p(n) < \dfrac{\pi}{\sqrt {6(n - 1)}}e^{\pi\sqrt {\frac {2n}3}}}$ Proof: We'll use the following $ 3$ facts: $ F1.$ $ \displaystyle\sum_{n = 1}^{\infty}p(n)x^n = \dfrac1{(1 - x)(1 - x^2)(1 - x^3)\ldots}$, where $ p(0) = 1$. $ F2.$ $ \displaystyle\sum_{i = 1}^{\infty}\dfrac1{i^2} = \dfrac{\pi^2}6$. $ F3.$ $ \ln(1 - x)^{ - 1} = - \ln(1 - x) = \displaystyle\sum_{j = 1}^{\infty}\dfrac{x^j}j$. Denote $ P(x) = \displaystyle\sum_{n = 1}^{\infty}p(n)x^n = \dfrac1{(1 - x)(1 - x^2)(1 - x^3)\ldots}$ (by $ F1$) the generating function for the sequence $ p(n)$. Let $ f(t) = \ln P(t)$. Then $ f(t) = \displaystyle\sum_{i = 1}^{\infty}\ln(1 - t^i)^{ - 1} = \sum_{k = 1}^{\infty}\left(\sum_{j = 1}^{\infty}\dfrac{t^{kj}}j\right) = \sum_{j = 1}^{\infty}\dfrac1j\left(\sum_{k = 1}^{\infty}(t^j)^k\right) = \sum_{j = 1}^{\infty}\dfrac1j\cdot \dfrac{t^j}{1 - t^j}$. Now take $ 0 < t < 1$. From $ \dfrac{1 - t^j}{1 - t} = 1 + t + t^2 + \ldots + t^{j - 1} > jt^{j - 1}$, we have $ 1 - t^j > j(1 - t)t^{j - 1}$, or $ \dfrac{t^j}{1 - t^j} < \dfrac1j\cdot\dfrac t{1 - t}$. Then $ f(t) = \displaystyle\sum_{j = 1}^{\infty}\dfrac1j\cdot \dfrac{t^j}{1 - t^j} < \dfrac t{1 - t}\sum_{j = 1}^{\infty}\dfrac1{j^2} = \dfrac{\pi^2}6\cdot\dfrac t{1 - t}$. We obtained the following important inequality $ \boxed{f(t) < \dfrac{\pi^2}6\cdot\dfrac t{1 - t}}$. Also, using the fact that $ p(n)$ is an increasing sequence $ P(t) = \displaystyle\sum_{j = 1}^{\infty}p(j)t^j > \sum_{j = n}^{\infty}p(j)t^j > \sum_{j = n}^{\infty}p(n)t^j = \dfrac{p(n)t^n}{1 - t}$. Taking logarithm of both sides we get $ f(t) > \ln p(n) + n\ln t - \ln(1 - t)$, or $ \ln p(n) < f(t) - n\ln t + \ln(1 - t) < \dfrac{\pi^2}6\cdot\dfrac t{1 - t} - n\ln t + \ln(1 - t)$. Further setting $ t = (1 + u)^{ - 1}$ for some $ u > 0$ (remember that $ 0 < t < 1$) we get $ \ln p(n) < \dfrac{\pi^2}6\cdot\dfrac1u + n\ln(1 + u) + \ln\dfrac u{1 + u}$. It follows that $ \boxed{\ln p(n) < \dfrac16\pi^2u^{ - 1} + (n - 1)u + \ln u}$. Here we have used the well-known inequality $ \ln(1 + x) < x$ for $ x > 0$. Setting $ u = \dfrac{\pi}{\sqrt {6(n - 1)}}$, we get the desired inequality, as $ \dfrac16\pi^2u^{ - 1} + (n - 1)u = \pi\sqrt {\dfrac{n - 1}3} < \pi\sqrt {\dfrac{2n}3}$. Note that setting different values for $ u$ or using slightly different inequalities along the proof will yield different bounds for $ p(n)$. ________________________ Proofs of the facts $ F1$: $ \dfrac1{(1 - x)(1 - x^2)(1 - x^3)\ldots} = (1 + x + x^2 + \ldots + )(1 + x^2 + x^4 +$ $ \ldots + )(1 + x^3 + x^6 + \ldots)$ and the conclusion is immediate. $ F2$: This is well-known. $ F3$: Consider the relation $ \dfrac1{1 - x} = 1 + x + x^2 + x^2 + \ldots$. Taking integrals of both sides, we have $ - \ln(1 - x) = \dfrac x1 + \dfrac{x^2}2 + \dfrac{x^3}3 + \ldots$, which is $ F3$. ________________________ Hope there are no typos or mistakes... For references see the following good article on partitions (it's in Bulgarian): "Разбивания"(Partitions) by Иван Ланджев in the book "Олимпийски теми 2006" (Olympiad Topics 2006). The above proof can be found there but with some small mistakes and with quite few explanations.