0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ There are so few possibilities you can just list them. $\endgroup$ – saulspatz Jan 12 '19 at 17:53
  • $\begingroup$ @saulspatz I have counted at least 20, it seems like a lot of work $\endgroup$ – Robo Yonuomaro Jan 12 '19 at 17:58
  • $\begingroup$ Can $x_2,x_3$ be real or just integers are alowed? $\endgroup$ – Patricio Jan 12 '19 at 18:09
  • $\begingroup$ Integers, I forgot to mention it $\endgroup$ – Robo Yonuomaro Jan 12 '19 at 18:10
1
$\begingroup$

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.

$\endgroup$

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.