number of solutions for this equation

68 Views Asked by At

What is the number of solutions for this equation: $$x_1 + x_2 + x_3 = 15$$ when $x_1 \in \mathbb{N}_{even} \cup \{0\}$, $0\leq x_2\leq 5$, $x_3 \geq 0$?

Can it be solved without generating functions? If not, how can I use generating functions to solve it?

EDIT: $x_1, x_2, x_3$ can be only integers

1

There are 1 best solutions below

0
On BEST ANSWER

Start by putting $x_1=2k$ (where $k$ varies from $0$ to $7$). This gives us the following

$$x_2 + x_3 = 15-2k = n$$

Now, using the stars and bars rule we know that the above equation has following number of integral solutions for any particular $k$

$$N_1 = \binom{n+2-1}{2-1} = \binom{n+1}{1} = \binom{16+2k}{1}$$

Now from this we subtract all the cases in which $x_2\ge6$. So put $x_2=y_2+6$ which gives us $y_2\ge0$

$$y_2 + x_3 = 15-2k-6 = 9-2k$$

Number of integral solutions to this are

$$N_2 = \binom{9-2k+2-1}{2-1} = \binom{10-2k}{1}$$

Summing up $N_1$ from $k=0$ to $k=7$

$$\sum_{k=0}^7\binom{16+2k}{1} =\sum_{k=0}^716+2k=184$$

Now summing up $N_2$ from $k=0$ to $k=4$ as after that the terms will simply be $0$ in the binomial coefficient

$$\sum_{k=0}^4\binom{10-2k}{1} =\sum_{k=0}^410-2k = 30$$

Subtracting $N_2$ from $N_1$, we'd get

$$N=N_1-N_2 = 184-30 =154$$ which is the total number of possibilities.