Finding the number of solutions of the equation $c_1 + c_2 + c_3 = 20$ in the nonnegative integers if $c_2$ is even and $c_3$ is odd

165 Views Asked by At

Find the number of nonnegative integer solutions to the equation $c_1 + c_2 + c_3 = 20$, where $c_2$ is even and $c_3$ is odd.

I started with finding the total number of solutions, $C(22,20)=231$. Then I tried to apply the inclusion-exclusion principle. Let $P_1$ be the number of solutions that do not satisfy the condition for $c_1$, $P_2$ for $c_2$ and so on.

$N-P_1-P_2-P_3+P_1P_2+P_2P_3+P_1P_3-P_1P_2P_3$ gives us the desired number of solutions. $P_1, P_1P_2, P_1P_3$ and $P_1P_2P_3$ are all zero because there is no condition for $P_1$. To find $P_2$, I assigned odd numbers to the $c_2$ and then calculated the number of solutions which is $110$. $P_3$ is also $110$. If I'm right up to this point, I'm stuck at finding $P_2P_3$.

To find the number of solutions that do not satisfy $c_2$ and $c_3$, I assigned $c_2$ odd numbers and $c_3$ even numbers. Adding an even and an odd number gives us an odd number. From what I previously calculated, I think there is a total of $110$ solutions again.

Thus, $231-110-110+110=121$. Is this true?

3

There are 3 best solutions below

2
On BEST ANSWER

For reasons I will explain below, it is easier to solve this problem directly than to use the Inclusion-Exclusion Principle.

A direct approach:

Since $20$ is an even number, $c_2$ is odd, and $c_3$ is even, $c_1 = 20 - c_2 - c_3$ is also an odd integer. Thus, there exist nonnegative integers $x_1, x_2, x_3$ such that $c_1 = 2x_1 + 1$, $c_2 = 2x_2$, and $c_3 = 2x_3 + 1$.
\begin{align*} c_1 + c_2 + c_3 & = 20 \tag{1}\\ 2x_1 + 1 + 2x_2 + 2x_3 + 1 & = 20\\ 2x_1 + 2x_2 + 2x_3 & = 18\\ x_1 + x_2 + x_3 & = 9 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers which has the same number of solutions as equation 1 subject to the stated constraints. A particular solution of equation 2 corresponds to the placement of two addition signs in a row of nine ones. For instance, $$++ 1 1 1 1 1 1 1 1 1$$ corresponds to the solution $x_1 = x_2 = 0$, $x_3 = 9$ (and $c_1 = 1, c_2 = 0, c_3 = 19$), while $$1 1 1 1 + 1 1 1 + 1 1$$ corresponds to the solution $x_1 = 4$, $x_2 = 3$, $x_3 = 2$ (and $c_1 = 9, c_2 = 6, c_3 = 5$). The number of solutions to Equation 2 is $$\binom{9 + 3 - 1}{3 - 1} = \binom{11}{2}$$ since we must select which two of the eleven positions required for nine ones and two addition signs will be filled by addition signs.

Remarks about your approach:

If you define $P_i$ to be the number of solutions that violate the constraint on $c_i$, then $P_iP_j$ is the product of $P_i$ and $P_j$. Presumably, you meant $P_iP_j$ is the intersection of the sets of solutions that violate the constraint on $c_i$ and the constraint on $c_j$.

If you wish to the Inclusion-Exclusion Principle, you should define $A_i$ to be the set of solutions that violate the constraint on $c_i$, in which case the number of admissible solutions is $$N - |A_1 \cup A_2 \cup A_3|$$ where \begin{align*} |A_1 \cup A_2 \cup A_3| & = |A_1| + |A_2| + |A_3|\\ & \quad - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3|\\ & \qquad + |A_1 \cap A_2 \cap A_3| \end{align*} As stated above, the constraint that $c_2$ is even and $c_3$ is odd imposes the additional constraint that $c_1$ is odd.

Let's examine $|A_1|$. If the condition that $c_1$ is odd is violated, then we need to find the number of solutions of the equation $$c_1 + c_2 + c_3 = 20$$ subject to the constraint that $c_1$ is even. If $c_1$ is even, then either $c_2$ and $c_3$ are both even or they are both odd. If $c_2$ and $c_3$ are both odd, we need to find the number of solutions of the equation $c_1 + c_2 + c_3 = 20$ in which exactly two of the variables are odd, that is, we need to solve the original problem in order to use the Inclusion-Exclusion Principle. Therefore, it makes more sense to solve the problem directly.

2
On

Lets try to use generating functions such that

$c_1=x^0+x^1+...=\frac{1}{1-x}$

$c_2=x^0+x^2+....=\frac{1}{1-x^2}$

$c_3=x^1+x^3+...=\frac{x}{1-x^2}$

Then , $[x^{20}] \frac{1}{1-x} \times \frac{1}{1-x^2} \times \frac{x}{1-x^2} $.

So ,we should find the coefficient of $x^{19}$ in the expression of$C(k+1-1,k)x^k \times C(m+2-1,m)x^{2m} $ where $k+2m=19$

For $k=1 ,m =9 \rightarrow 10$

For $k=3 ,m =8 \rightarrow 9$

For $k=5 ,m =7 \rightarrow 8$

For $k=7 ,m =6 \rightarrow 7$

For $k=9 ,m =5 \rightarrow 6$

For $k=11 ,m =4\rightarrow 5$

For $k=13 ,m =3 \rightarrow 4$

For $k=15 ,m =2 \rightarrow 3$

For $k=17 ,m =1 \rightarrow 2$

For $k=19 ,m =0 \rightarrow 1$

As a result , the sum of coefficients are equal to $55$ . Then the answer is $55$

1
On

Alternative approach:

Any solution to $c_1 + c_2 + c_3 = 20$ where $c_2, c_3$ are of opposite parity (i.e. one odd, the other even) will occur if and only if $c_1$ is odd. Further, for each of these solutions, you know by symmetry, that exactly $(1/2)$ of them will represent $c_2$ even and $c_3$ odd.

So, you may assume that $c_1 \in \{1,3,5,\cdots, 19\}.$

Further, for each such value of $c_1$, the problem will be represented by :

$c_2 + c_3 = (20 - c_1)$, which will have

$\displaystyle \binom{[20 - c_1] + [2-1]}{[2-1]} = (21 - c_1)$ solutions.

Therefore, the desired tally is

$$\left(\frac{1}{2}\right) \times \sum_{k = 1}^{10} (21 - [2k-1]) ~=~ \left(\frac{1}{2}\right) \times \sum_{k = 1}^{10} (22 - [2k]).$$

The right hand factor above is $220 - 2(55) = 110$.

Therefore, the final computation is $(110/2) = 55.$