Finding the generating function.

Question

Find the generating function for the number of solutions for the equation $x_1+x_2+x_3+x_4 = n$, where $x_1,x_2,x_3,x_4\geq1$, and $x_1 < x_2$.

My attempt so far: I have tried putting a $y$ value in my equation, where $y$ represents the difference between $x_2$ and $x_1$, $ y $ must be greater than $0$ and less than or equal to $n-4$,because we have to take something for $x_1,x_2,x_3,x_4$. Then, after solving it, I get that the number is ${n-1\choose n-5}$, which works for $n = 5$, but for nothing else.

Any help would be appreciated, thanks!

Answer 1

Your approach directly yields the GF $$(z^2 + z^4 + \ldots)( z+z^2 +\ldots)(z+z^2 + \ldots)(z+z^2 + \ldots) = \frac{ z^5}{(1-z^2)(1-z)^3}.$$

Do you see why?

We have $ 2x_ 1 + (x_2 - x_1) + x_3 + x_4 = n$, with no restriction other than each term being $\geq 1$.

Answer 2

The number of solutions with $x_1<x_2$ is the same as the number of solutions with $x_1>x_2$. So take the generating function without restrictions, $(z+z^2+\cdots)^4$, subtract the generating function for the solutions with $x_1=x_2$, and divide by $2$, yielding \begin{align} \frac{\left(\sum_{k=1}^\infty z^k\right)^4-\left(\sum_{k=1}^\infty z^{2k}\right)\left(\sum_{k=1}^\infty z^k\right)^2}{2} &= \frac{1}{2}\left(\frac{z^4}{(1-z)^4} - \frac{z^4}{(1-z^2)(1-z)^2}\right) \\ &= \frac{z^5}{(1-z)^4 (1+z)} \end{align}