How many solutions in positive integers has equation $x_1 + x_2 + … + x_n = n^2?$

Question

Let $n -$ positive integer. How many solutions in positive integers $x_1 <x_2 <... <x_n$ has equation $$x_1 + x_2 + ... + x_n = n^2?$$

I have no idea how to solve this problem.

Answer 1

Let $a_n$ be the number of solutions. Then $a_n$ is the number of partitions of $n^2$ into $n$ distinct parts. Looking at the conjugate partitions, we see that this is also the number of partitions of $n^2$ into parts $1,2,\ldots,n$ such that there is at least one part of each of these sizes; this is the number of solutions to

$$\sum_{k=1}^nkx_k=n^2$$

in positive integers $x_k$. For example, for $n=3$ there are just $3$ partitions of $3^2=9$ into $3$ distinct parts: $6+2+1$, $5+3+1$, and $4+3+2$. The corresponding partitions using only parts $1,2$, and $3$, each of them at least once, are $3+2+1+1+1+1$, $3+2+2+1+1$, and $3+3+2+1$.

This sequence is OEIS A107379; it is noted there that $a_n$ is also the number of partitions of $n^2$ into $n$ odd parts. (E.g., $9$ can be written as $1+1+7$, $1+3+5$, and $3+3+3$.) The entry has no closed form for $a_n$; it does give the generating function

$$g(x)=x^{\binom{n}2}\prod_{k=1}^n\frac1{1-x^k}\;,$$

though it incorrectly calls it a formula for $a_n$.