$x_1 + x_2 + x_3 + ... + x_6 =20$ while $0\le x_i\le8$

Question

So there this problem. In my lectures notes : is solved as such. We can compute the number of ways that violate the constraint. We note $c_i$ as the fact that $x_i$ has a value $>8$ and $N(c_i)$ the number of ways this can happen. We actually want to compute : $N((c_i \lor c_j)^\prime) =N - \sum_{i}N(c_i) + \sum_{i}N(ci \land c_j) =N - N(c_i) + N(ci \land c_j)$ I get that this formula comes from $N((c_i \lor c_j)^\prime) = N - N(c_i \lor c_j) $ and the inclusion - exlusion principle - I think -. I'm generally confused about the formula of inclusion - exclusion. To my mind, I thought about it like the are two ways to violate the constraint : 1)there is one $x_i$ receives value $>8$ (fact A) or either 2 (fact B)( there can't be more since $9 + 9 =18$ and we sum them to $20$). So I need to compute : $ (A \lor B)^\prime = Everything - (|A| + |B| - |A\land B|)$ and here I get confused because if |B| is number of ways two $x_i$s are $>8$ then what does $|A \land B|$ stands for? (how do I estimate its value?)

Answer 1

We can define $A_i$ to be the set of outcomes in which $x_i > 8$, where $1 \leq i \leq 6$. Then the set of excluded outcomes is $A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \cup A_6$. By the Inclusion-Exclusion Principle, \begin{align*} |A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \cup A_6| & = \sum_{i = 1}^{6} |A_i| - \sum_{1 \leq i < j \leq 6} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq 6} |A_i \cap A_j \cap A_k|\\ & \quad - \sum_{1 \leq i < j < k < l \leq 6} |A_i \cap A_j \cap A_k \cap A_l|\\ & \qquad + \sum_{1 \leq i < j < k < l < m \leq 6} |A_i \cap A_j \cap A_k \cap A_l \cap A_m|\\ & \quad\qquad - |A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5 \cap A_6| \end{align*} As you observed, at most two of the variables can exceed $8$ since $3 \cdot 9 = 27 > 20$. Therefore, \begin{align*} |A_i \cap A_j \cap A_k| & = 0~\text{for each}~i, j, k~\text{such that} 1 \leq i < j < k \leq 6\\ |A_i \cap A_j \cap A_k \cap A_l| & = 0~\text{for each}~i, j, k, l~\text{such that} 1 \leq i < j < k < l \leq 6\\ |A_i \cap A_j \cap A_k \cap A_l \cap A_m| & = 0~\text{for each}~i, j, k, l, m~\text{such that} 1 \leq i < j < k < l < m\leq 6\\ |A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5 \cap A_6| & = 0 \end{align*} Furthermore, by symmetry, $$|A_1| = |A_2| = |A_3| = |A_4| = |A_5| = |A_6|$$ and $$|A_1 \cap A_2| = |A_1 \cap A_3| = |A_1 \cap A_4| = |A_1 \cap A_5| = |A_1 \cap A_6| = |A_2 \cap A_3| = |A_2 \cap A_4| = |A_2 \cap A_5| = |A_2 \cap A_6| = |A_3 \cap A_4| = |A_3 \cap A_5| = |A_3 \cap A_6| = |A_4 \cap A_5| = |A_4 \cap A_6| = |A_5 \cap A_6|$$ Hence, $$|A_1 \cup A_2 \cup A_3 \cup A_4 \cup A_5 \cup A_6| = \binom{6}{1}|A_1| - \binom{6}{2}|A_1 \cap A_2|$$

If $N$ represents the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20 \tag{1}$$ in the nonnegative integers, then the number of solutions which do not violate the constraints is $$N - \binom{6}{1}|A_1| + \binom{6}{2}|A_1 \cap A_2|$$

$N$: A particular solution of equation 1 in the nonnegative integers corresponds to the placement of $6 - 1 = 5$ addition signs in a row of $20$ ones. For instance, $$1 1 1 1 + 1 1 1 + + 1 1 1 1 1 1 1 1 + 1 1 + 1 1 1$$ corresponds to the solution $x_1 = 4$, $x_2 = 3$, $x_3 = 0$, $x_4 = 8$, $x_5 = 2$, $x_6 = 3$. The number of such solutions is $$\binom{20 + 6 - 1}{6 - 1} = \binom{25}{5}$$ since we must choose which $6 - 1 = 5$ of the $20 + 6 - 1 = 25$ positions required for $20$ ones and $6 - 1 = 5$ addition signs will be filled with addition signs.

$|A_1|$: If $x_1 > 8$, then $x_1' = x_1 - 9$ is a nonnegative integer. Substitute $x_1' + 9$ for $x_1$ in equation 1 and simplify to obtain $$x_1' + x_2 + x_3 + x_4 + x_5 + x_6 = 11 \tag{2}$$ Equation 2 is an equation in the nonnegative integers with

$$\binom{11 + 6 - 1}{6 - 1} = \binom{16}{5}$$

solutions.

$|A_1 \cap A_2|$: If $x_1 > 8$ and $x_2 > 8$, then $x_1' = x_1 - 9$ and $x_2' = x_2 - 9$ are nonnegative integers. Substitute $x_1' + 9$ for $x_1$ and $x_2' + 9$ for $x_2$ in equation 1 and simplify to obtain $$x_1' + x_2' + x_3 + x_4 + x_5 + x_6 = 2 \tag{3}$$ Equation 3 is an equation in the nonnegative integers with

$$\binom{2 + 6 - 1}{6 - 1} = \binom{7}{5}$$

solutions.

Hence, the number of admissible solutions is

$$\binom{25}{5} - \binom{6}{1}\binom{16}{5} + \binom{6}{2}\binom{7}{5}$$

Answer 2

Take simply all the solutions minus the ones with at least one $x_i>8$.

You then use PIE to get the result:

First, you consider a $x_i$ and and give $9$ units to it. This can be done in $\binom{6}{1}$ ways. Then you are left with the equivalent problem $x_1+...+x_6=11$ (because you already gave $9$ units) and proceed as normally, thus $6\times\binom{11+6-1}{6-1}=6\times\binom{16}{5}.$ Then you realize you counted too many, since for instance you counted twice equal pairs of $x_i, x_j$ such that $x_i=x_j=9$ and therefore you need to subtract these pairs. You then give 9 to each elements of such pairs ($9+9=18$). There are $\binom{6}{2}$ pairs and thus $\binom{6}{2}\times\binom{7}{5}$. You if you had started with more units than $20$ you could go now ahead and sum up the ones you would have over-subtracted of order $3$ and so forth.

You are left with:

$$\binom{25}{5}-\big[\binom{6}{1}\binom{16}{5}-\binom{6}{2}\binom{7}{5}\big].$$

This is equivalent to counting the cardinalities of the sets you mentioned, plus the fact that the cardinalities of the the sets (and the ones of the intersections) are equal.