§ Number of distinct numbers in a partition

• A positive integer $n$ is represented as a partition $\lambda \equiv (k_1, k_2, \dots)$ where $\sum_i k_i = n$ and $k_1 \leq k_2, \dots$. Such a $\lambda$ always contains at most $O(\sqrt n)$ distinct numbers.
• Intuition: suppose we want to have the maximum number of distinct numbers. Since we are tied down by the constraint $\sum k_i = n$, we must try to choose the $k_i$ as small as possible. But we know that even $\sum_{i=1}^p i = p(p+1)/2 \sim O(p^2)$. Now if $O(p^2) = n$, then the sum can only run upto $\sqrt p$.
• Alternate intuiton: asking to build a number $n$ out of distinct numbers $k_1, k_2, \dots$is asking to build a "jagged triangle" out of columns $(i, k_i)$ whose area is $n$. Area is $1/2 b h$, which is sorta quadratic (?)