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

Question

I'm working on this problem. To solve it I need this lemma:

Let $n\ge2, n\in \mathbb N$. Let $X$ be the number of solutions in positive integers to the equation $x_1+x_2+...+x_n=n^2$. Let $Y$ be the number of solutions in positive integers to the equation $y_1+y_2+...+y_n=n^2$, such that $y_1 < y_2 < ... < y_n$. Prove that $$X < Y\cdot n!\cdot 2^{n-1}.$$

I have no idea how to solve this problem.

Answer 1

Note that $Y$ is also the number of integral solutions $\left(z_1,z_2,\ldots,z_n\right)$ satisfying the condition $0\leq z_1\leq z_2\leq \ldots\leq z_n$ to the equation $$z_1+z_2+\ldots+z_n=\frac{n(n-1)}{2}$$ (i.e., by setting $z_k:=y_k-k$ for every $k=1,2,\ldots,n$). Hence, $n!\cdot Y$ is at least the number of integral solutions $\left(w_1,w_2,\ldots,w_n\right)$ with $w_1,w_2,\ldots,w_n\geq 0$ to $$w_1+w_2+\ldots+w_n=\frac{n(n-1)}{2}\,.$$ Consequently, $$n!\cdot Y\geq \binom{\frac{n(n-1)}{2}+(n-1)}{n-1}=\binom{\frac{n(n+1)}{2}-1}{n-1}=\frac{1}{2^{n-1}(n-1)!}\,\prod_{i=1}^{n-1}\,\big(n(n+1)-2i\big)\,.$$ For each $i=1,2,\ldots,n-1$, it is trivial that $n(n+1)-2i> n^2-i$. That is, $$n!\cdot Y> \frac{\prod_{i=1}^{n-1}\,\left(n^2-i\right)}{2^{n-1}(n-1)!}=\frac{1}{2^{n-1}}\,\binom{n^2-1}{n-1}=\frac{X}{2^{n-1}}\,.$$

Answer 2

Number of positive integer solutions to $x_1+\cdots+x_n=n^2=$Number of ways of distributing $n^2$ similar sticks among $n$ boys such that each gets at least $1={n^2-1\choose n-1}$.

As for the second equation there is a good answer here.

You can also try this approach : with the constraints $0<y_1<y_2<\cdots<y_n$ the minimum case i.e the minimum number of articles each will get is $y_1=1;y_2=2;\cdots;y_n=n; $

Then the total number of sticks left to be distributed is $=n^2-{n(n+1)\over 2}={n(n-1)\over 2}$. You can try to continue from here.