2
$\begingroup$

Let $p(n)$ represent the number of partitions of a natural number n. Show that $p(n) ≥2^{\left \lfloor \sqrt n \right \rfloor}$ for $n \ge 2$ where $[x]$ represents the floor function, which takes any real number $x$ to the greatest integer equal to or less than $x$.

This is a problem from a practice exam and it gives a hint to construct a surjection from the set of partitions of n to the power set $\{1, 2, \ldots, \sqrt n \}$, but I'm really quite unsure about how to go about doing this. Any help would be greatly appreciated and I apologize for the poor formatting.

$\endgroup$
2
$\begingroup$

Note that

$$n-(1+2+\cdots+\lfloor\sqrt n\rfloor)=n-{\lfloor\sqrt n\rfloor(\lfloor\sqrt n\rfloor+1)\over2}\ge n-{\sqrt n(\sqrt n+1)\over2}={n-\sqrt n\over2}\gt\sqrt n\ge\lfloor\sqrt n\rfloor$$

if $n\gt9$. If $A$ is any subset of $S=\{1,2,\ldots,\sqrt n\}$ (for $n\gt9$), then $m=n-\sum_{k\in S}k\not\in S$ and $n=m+\sum_{k\in S}k$ is a partition of $n$. So the number of partitions of $n$ (for $n\gt9$) is at least the number of subsets of $S$, i.e., $p(n)\ge2^{\lfloor\sqrt n\rfloor}$. For $2\le n\le9$, the inequality can be verified case by case.

$\endgroup$
1
$\begingroup$

Hint: Each set $A$ in the power set of $S$ represents for at least one partition of $n$ that contains all elements in $A$ (each appears at least once in the partition) but no element in $S \setminus A$ appears in the partition.

$\endgroup$
  • $\begingroup$ What is the set $S$? $\endgroup$ – TheNotMe Dec 25 '17 at 20:12

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.