How many solutions are there to the equation $x_1+x_2+x_3+x_4+x_5=30$ with restrictions using generating functions?

123 Views Asked by At

How many solutions are there to the equation $x_1+x_2+x_3+x_4+x_5=30$ where

$a) 2 \leq x_1 \leq 4$, and $3 \leq x_i \leq 8$, for all $2 \leq i \leq 5$.

$b) 0 \leq x_i$ for all $1 \leq i \leq 5$, with $x_2$ even and $x_3$ odd.

Attempt 1:

So far with part $a$ I have this:

$\frac{(x^2+x^3+x^4)(x^3+x^4+x^5+x^6+x^7+x^8)^4}{(1-x)}$

I'm struggling with how to go further from where I am at by using generating functions. I don't know how I would deal with the case where $x_2$ is even and $x_3$ is odd.

Attempt 2:

I've followed the videos posted before and here's where I'm at now:

Part a:

$[x^{30}](x^2+x^3+x^4)(x^3+x^4+x^5+x^6+x^7+x^8)^4=[x^{30}]x^2 \frac{1-x^3}{1-x} x^{12} (\frac{1-x^6}{1-x})^4 = [x^{16}] \frac{1-x^3}{1-x} (\frac{1-x^6}{1-x})^4 = [x^{16}] (1-x^3)(1-x)^{-2}(1-x^6)^4(1-x)^{-4}$

Part b:

$[x^{30}](1+x^2+x^4+...)(x+x^3+x^5+...)(1+x+x^2+...)^3 = [x^{30}] \frac{1}{1-x^2}x \frac{1}{1-x^2}(\frac{1}{1-x})^3 = [x^{29}](1-x)^{-2}(1-x)^{-3}$

I believe I need to do something like at this mark, but I'm not sure how to apply it to my problem.

2

There are 2 best solutions below

2
On

Both your problems have finite number of solutions and are easily solved by brute force, e.g. in Mathematica:

enter image description here

3
On

The theory is rather ... computationaly extensive. Check out these 2 videos, they should give a full explanation

https://youtu.be/-drdeNMoe8w

https://youtu.be/ZyUb5UxBA9Q

being even means, that the generating function's part related to this x will be something like $(x^0 + x^2 + x^4 + x^6 +...)$

For odd - similar scenario: $x^1 + x^3 + x^5 + x^7 + ... $

the generating function for (a) would be correct if you removed the denominator.

the generating function for (b) should look like this I believe:

$(1+x+x^2+x^3+...)^3(x+x^3+x^5+x^7+...)(1+x^2+x^4+x^6+...) = x(1-x)^{-3}(1-x^2)^{-2}$