6
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ May I ask what methods have you tried? $\endgroup$ – the4seasons Jun 25 '16 at 7:47
  • $\begingroup$ @the4seasons: No methods. I do not know how to solve. Tried $n=2$ and $n = 3$ $\endgroup$ – Roman83 Jun 25 '16 at 7:59
  • $\begingroup$ This is OEIS sequence A107379. $\endgroup$ – joriki Jun 25 '16 at 8:21
  • 2
    $\begingroup$ 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$. $\endgroup$ – Jack D'Aurizio Jun 25 '16 at 9:04
  • $\begingroup$ where is from this problem? $\endgroup$ – function sug Jun 26 '16 at 9:28
4
$\begingroup$

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.

No time for the lower bound now.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I took the liberty to fix a possible typo. I hope you wouldn't mind. $\endgroup$ – Batominovski Jun 28 '16 at 11:41
2
$\begingroup$

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}\,.$$

|cite|improve this answer
$\endgroup$

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.