ternary string using the Inclusion-Exclusion

Question

Use the Inclusion-Exclusion Principle to determine how many ternary strings of length five contain two consecutive $1$s.(explain your answer)

---

My attempt was to get the string that has all ones. Since the length is five and the ternary contains $0,1,2$ only. This is what I did: $3 \cdot 3 \cdot 3 \cdot 3 \cdot 3$ (each location has $3$ possibilities ) - $2 \cdot 2 \cdot 2 \cdot 2 \cdot 2$ (without $1$s) we get $3^5-2^5= 211$. However, this is not the Inclusion-Exclusion method and I don't know how to apply it to this issue!

Answer 1

Let $A_1$ be the set of ternary strings which contain consecutive 1s at positions $i$ and $i+1$, for $i = 1,\ldots,4$. What you seek is $|A_1\cup\ldots\cup A_4|$. It is easy to compute the size of the intersection of any subfamily of $A_i$s: just raise 3 to the power $j$, where $j$ is the number of places not necessarily filled with 1s. To simplify the formula, let us denote $|A_x\cap A_y\cap A_z\cap\ldots|$ by $a_{xyz\ldots}$.

By the I-E principle, we have $$|A_1\cup\ldots\cup A_4| = (a_1+a_2+a_3+a_4)-(a_{12}+a_{23}+a_{34}+a_{13}+a_{24}+a_{14})+(a_{123}+a_{234}+a_{124}+a_{134})-a_{1234} = 4\cdot 3^3-(3\cdot 3^2+3\cdot 3^1)+(2\cdot 3^1+2\cdot 3^0)-3^0 = 79$$

Answer 2

Let $A_1$ be the set of ternary strings of length $5$ that have $1$s in the first and second positions. Let $A_2$ be the set of ternary strings of length $5$ that have $1$s in the second and third positions. Let $A_3$ be the set of ternary strings of length $5$ that have $1$s in the third and fourth positions. Let $A_4$ be the set of ternary strings that have $1$s in the fourth and fifth positions. By the Inclusion-Exclusion Principle, the number of ternary strings of length $5$ that contain two consecutive $1$s is \begin{align*} |A_1 \cup A_2 \cup A_3 \cup A_4| & = |A_1| + |A_2| + |A_3| + |A_4|\\ & \quad - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_1 \cap A_4| - |A_2 \cap A_3| - |A_3 \cap A_4|\\ & \quad + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_1 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_4|\\ & \quad - |A_1 \cap A_2 \cap A_3 \cap A_4| \end{align*}

$|A_1|$: Since the first two positions are filled with $1$s, they can filled in one way. The remaining three positions of the ternary string of length $5$ can be filled with a $0$, $1$, or $2$. Hence, $$|A_1| = 3^3$$ By symmetry, $$|A_1| = |A_2| = |A_3| = |A_4|$$

$|A_1 \cap A_2|$: Observe that sequences in the sets $A_1$ and $A_2$ share a position in which there must be a $1$. Hence, sequences in $A_1 \cap A_2$ have three consecutive ones and two positions that may be filled with $0$, $1$, or $2$. Hence, $$|A_1 \cap A_2| = 3^2$$

The sets $A_1 \cap A_2$, $A_2 \cap A_3$, and $A_3 \cap A_4$ each contain sequences with three consecutive $1$s and two positions that may be filled with a $0$, $1$, or $2$. Hence, $$|A_1 \cap A_2| = |A_2 \cap A_3| = |A_3 \cap A_4|$$

$|A_1 \cap A_3|$: The sets $A_1$ and $A_3$ contain sequences that do not share a position in which there must be a $1$. Hence, four positions of the ternary sequence must be filled with $1$s. The remaining position of the sequence can be filled with a $0$, $1$, or $2$. Hence, $$|A_1 \cap A_3| = 3$$

The sets $A_1 \cap A_3$, $A_1 \cap A_4$, and $A_2 \cap A_4$ each contain sequences in which four positions must be filled with $1$s and the remaining position can be filled with a $0$, $1$, or $2$. Hence, $$|A_1 \cap A_3| = |A_1 \cap A_4| = |A_2 \cap A_4|$$

$|A_1 \cap A_2 \cap A_3|$: Observe that there are four consecutive positions that must be filled with $1$s. The remaining position can be filled with a $0$, $1$, or $2$. Therefore, $$|A_1 \cap A_2 \cap A_3| = 3$$

Observe that $A_1 \cap A_2 \cap A_3$ and $A_2 \cap A_3 \cap A_4$ each contain sequences with four consecutive $1$s and a position that may be filled with a $0$, $1$, or $2$. Hence, $$|A_1 \cap A_2 \cap A_3| = |A_2 \cap A_3 \cap A_4|$$

$|A_1 \cap A_2 \cap A_4|$: Observe that all five positions of the sequence must be filled with $1$s. Hence, $$|A_1 \cap A_2 \cap A_4| = 1$$

Observe that $A_1 \cap A_2 \cap A_4$ and $A_1 \cap A_3 \cap A_4$ contain sequences in which all five positions must be filled with $1$s. Hence, $$|A_1 \cap A_2 \cap A_4| = |A_1 \cap A_3 \cap A_4|$$

$|A_1 \cap A_2 \cap A_3 \cap A_4|$: Observe that all five positions must be filled with $1$s. Hence, $$|A_1 \cap A_2 \cap A_3 \cap A_4| = 1$$