1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Mar 6 '18 at 21:37
1
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ that makes |A1∪A2∪A3∪A4| a negative number. Is that ok? it is gonna be -11 $\endgroup$ – W.M Mar 7 '18 at 18:20
  • $\begingroup$ @W.M I get \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_2 \cap A_4| - |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|\\ & = 3^3 + 3^3 + 3^3 + 3^3 - 3^2 - 3 - 3 - 3^2 - 3 - 3^2 + 3 + 1 + 1 + 3 - 1\\ & = 27 + 27 + 27 + 27 - 9 - 3 - 3 - 9 - 3 - 9 + 3 + 1 + 1 + 3 - 1\\ & = 79 \end{align*} $\endgroup$ – N. F. Taussig Mar 7 '18 at 18:33
0
$\begingroup$

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$$

$\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.