§ Number of distinct numbers in a partition
- A positive integer is represented as a partition where and . Such a always contains at most distinct numbers.
- Intuition: suppose we want to have the maximum number of distinct numbers. Since we are tied down by the constraint , we must try to choose the as small as possible. But we know that even . Now if , then the sum can only run upto .
- Alternate intuiton: asking to build a number out of distinct numbers is asking to build a "jagged triangle" out of columns whose area is . Area is , which is sorta quadratic (?)