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$


  • $\begingroup$ @vadim123 sor what do you mean 'appear'? $\endgroup$ – OOD Waterball Feb 5 at 6:00
  • $\begingroup$ @vadim123 I don't understand where I replace it? It's a problem given as a practice, The problem's description is as short as the post title. Any hint is appreciated $\endgroup$ – OOD Waterball Feb 5 at 6:10

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.

  • $\begingroup$ Wow, thank you! That's the point ! $y_5$ is not independent! $\endgroup$ – OOD Waterball Feb 5 at 7:58

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.