Find number of solutions of this equation using generating function

632 Views Asked by At

I'm given an equation $x_1 + x_2 + x_3 + x_4 + x_5 = 24$, with a restriction that all of $x_i > 1$ and 2 of them are odd, the rest are even natural numbers.

I can solve this using the following reasoning: I must allocate $2 \cdot 3$ for the odd summands and $3 \cdot 2$ for even summands. Then I have to find the number of ways I can distribute the remaining 12 to the 5 unknowns. Since these 12 must be distributed in pairs, it follows that the number of ways it can be done is ${5 + 6 - 1 \choose 5} = 210$, and the number of ways the unknowns can be arranged is $\frac{5!}{2!3!} = 10$, hence the final answer is $2100$. I know this to be correct because I also wrote some code to compute it.

However, I'm required to recast this problem as a generating function, and I'm lost as to how to do that. I would probably be able to solve it, once it is given as a generating function (which is my final goal).

1

There are 1 best solutions below

2
On BEST ANSWER

I'm not sure how to bring the ${5\choose2}=10$ into the generating function, but apart from that, you are looking for the coefficient of $x^{24}$ in $$10(x^3+x^5+x^7...)^2(x^2+x^4+x^6+...)^3$$ By the way, ${10\choose4}=210$
The exponent of $x$ is the sum of the exponents of the five terms chosen from the five factors.
The first two factors, the exponent is odd - that is the two odd numbers. The other three factors, the exponent is even.
Each time you select terms whose exponents add to $24$, you add $1$ to the coefficient of $x^{24}$. So the coefficient of $x^{24}$ equals the number of ways to do it.
I multiply by $10$ because I can't think of a way to put it into the generating function otherwise.
Yes, you can stop at $x^{23}$ and $x^{24}$ because larger terms will not contribute to $x^{24}$ in the final product. On the other hand, the infinite sum has a simpler formula than a finite sum.