Find the generating function for the number of integer solutions to $x_1 + x_2 + x_3 + x_4 = r$ with $1 \le x_1 \le x_2 \le x_3 \le x_4$

Question

Find the generating function for the number of integer solutions to $x_1 + x_2 + x_3 + x_4 = r$ with $1 \le x_1 \le x_2 \le x_3 \le x_4$.

The textbook has showed me the solution, so I do know how to do this (If someone need it, I will update)

But before I saw the solution, I constructed my own way which 'seemed' to be wrong, but I couldn't see where the mistake was, which step led to the incorrect generating function usage, so please point out the mistake I made :) :

First, let

$y_1 = x_1\\y_2 = x_2 - x_1\\ y_3 = x_3 - x_2\\ y_4 = x_4 - x_3\\ y_5 = r - x_4$

thus $y_1 + y_2 + y_3 + y_4 + y_5 = r$
where $y_1 \ge 1,\ y_2, y_3, y_4 \ge 0,\ y_5 \ge 3$

So, the generating function can be constructed:

$A(x) = (x + x^2 + x^3 + ...)(1 + x + x^2 + ...)^3(x^3 + x^4 + x^5 + ...)\\ = x(1 + x + x^2 + ...)(1 + x + x^2 + ...)^3x^3(1 + x + x^2 + ...)\\= x^4(1 + x + x^2 + ...)^5\\ = x^4(\frac{1}{1-x})^5 = x^4(\sum_{n=0}^\infty\ {{4 + n}\choose{4}}x^n)$

The coefficient of $x^r$ is ${{4 + r-4}\choose{4}} = {{r}\choose{4}}$

If $r = 6$, from my generating function, there are ${{6}\choose{4}} = 15$ solutions, which seemed wrong, because the solution can only be $1 + 1 + 1 + 3 = 6$ or $1 + 1 + 2 + 2 = 6$

Thanks!

Answer 1

Your $y_1$ through $y_4$ are fine for the problem; we have $x_1+x_2+x_3+x_4=4y_1+3y_2+2y_3+y_4$, and that lets us build a generating function $$f(x)=(x^4+x^8+x^{12}+\cdots)(1+x^3+x^6+\cdots)(1+x^2+x^4+\cdots)(1+x+x^2+\cdots)$$ The coefficient of $x^r$ in that will be our answer.

Then you introduce $y_5=r-x_4=x_1+x_2+x_3=3y_1+2y_2+y_3$. It's not an independent variable; it's completely determined by the $y_i$ we already know. As such, it introduces no new information; if we take the $x^2$, $x$, and $1$ terms respectively in the first three factors of your expression, we have to take the $x^8$ term in the fifth factor. That's not the free choice implied by multiplication, and your generating function is invalid.

In short, when we build up a generating function as a product, each factor in that product must represent an independent choice, which can be anywhere in the full range allowed regardless of the values of the others. The only restrictions come from the overall sum we're looking to match, and the generating function's variable powers of $x$ imply that we allow that sum to vary.

Answer 2

I can’t post my ask on new thread.

Problem 1. Let be $a$ is positive integer $(a\le 5)$. Define $\|1,1,1,a;n\|$ are Number of non-negative integer solutions of equation $\quad x_1+x_2+x_3+ax_4=n$

Proof

$\|1,1,1,a;n\|=\left\lfloor\dfrac{(n+2)(n+a+2)(2n+a+1)}{12a}\right\rfloor$

Problem2. Applies result on problem 1, Count number of triangles with edges are positive integers less than or equal $n$

---

My solution for problem 2. Let $x_1,x_2,x_3$ are three edges of triangle sort order $1\le x_1\le x_2\le x_3\le n$

Get $\begin{cases}x_1=y_1+1;(y_1\ge 0) \\ x_2=x_1+y_2=y_1+y_2+1;(y_2\ge 0)\\ x_3=x_2+y_3=y_1+y_2+y_3+1;(y_3\ge 0)\end{cases}$ Because $x_1+x_2>x_3$ therefore $2y_1+y_2+2>y_1+y_2+y_3+1\Rightarrow y_1\ge y_3\Leftrightarrow y_1=y_3+y_4;(y_4\ge 0)$ And $x_3=y_1+y_2+y_3+1=y_2+2y_3+y_4+1\le n$ Therefore $y_2+y_4+y_5+2y_3=n-1$ where $y_5\ge 0$ Ref problem 1. Number of triangles are $\|1,1,1,2;n-1\|=\left\lfloor\dfrac{(n+1)(n+3)(2n+1)}{24}\right\rfloor$

Return problem 1. I trying uses generating funtion $G(x)=\dfrac{1}{(1-x)^3(1-x^a)}$ but not result. Could you help me solve it?