# The number of positive integer solutions to the equation $x_1+2x_2+…+nx_n=n^2.$

Let $n \ge 2, n \in \mathbb N$. $A_n$ denotes the number of positive integer solutions to the equation $$x_1+2x_2+...+nx_n=n^2.$$ Prove inequality $$\frac{n^n(n-1)^{n-1}}{2^{n-1}\left(n!\right)^2}<A_n<\frac{n^{2n-1}}{\left(n!\right)^2}$$

I have no idea how to solve this problem.

• May I ask what methods have you tried? – the4seasons Jun 25 '16 at 7:47
• @the4seasons: No methods. I do not know how to solve. Tried $n=2$ and $n = 3$ – Roman83 Jun 25 '16 at 7:59
• This is OEIS sequence A107379. – joriki Jun 25 '16 at 8:21
• We have: $$A_n = [x^{n^2}]\frac{x}{1-x}\cdot\frac{x^2}{1-x^2}\cdot\ldots\cdot\frac{x^n}{1-x^n} \tag{1}$$ hence: $$A_n = [x^{\frac{n(n-1)}{2}}]\frac{1}{1-x}\cdot\frac{1}{1-x^2}\cdot\ldots\cdot\frac{1}{1-x^n}\tag{2}$$ and the main contribute comes from the pole at $x=1$. – Jack D'Aurizio Jun 25 '16 at 9:04
• where is from this problem? – function sug Jun 26 '16 at 9:28

Note that $A_n$ is also equal to the number of tuples $(y_1,y_2,\ldots,y_n)\in\mathbb{Z}^n$ such that $0<y_1<y_2< \ldots y_n$ and $y_1+\ldots +y_n=n^2$.
[Consider the bijection $y_1=x_n,y_2=x_n+x_{n-1}$,$\ldots$,$y_n=x_n+\ldots +x_1$.]
The number of such tuples is less than $\dfrac{1}{n!}$ times the number of positive integer solutions to $z_1+\ldots +z_n=n^2$, which is ${n^2-1 \choose n-1}$, which is at most $\dfrac{n^{2(n-1)}}{(n-1)!}=\dfrac{n^{2n-1}}{n!}$—this gives the upper bound.
From the OP's question The number of positive integer solutions to the equation $x_1+x_2+...+x_n=n^2.$, we have $$A_n>\frac{1}{2^{n-1}n!}\,\binom{n^2-1}{n-1}\geq\frac{\big(n(n-1)\big)^{n-1}}{2^{n-1}n!(n-1)!}=\frac{n^n(n-1)^{n-1}}{2^{n-1}(n!)^2}\,.$$