Ternary Strings of Length $2n$ I am trying to count the number of ways I can generate a ternary string of
length $2n$ such that there are no $0$s present on the even positions
the string. To me, this seemed like a prime case of the inclusion exclusion
problem.
I can see that the number of ternary string of length $2n$ is $3^{2n} = 9^n.$
I can also see that the number of ternary strings such that $k$ of the
even positions are occupied by zeros is $\binom{n}{k}2^{n-k}3^n.$ This leaves
me with an inclusion exclusion expression that is essentially
$$9^n - n2^{n-1}3^n + \binom{n}{2}2^{n-2}3^n - \binom{n}{3}2^{n-3}3^n
+ ... + (-1)^n 3^n.$$
However, I am having some difficulties figuring out how to simplify this,
given that we see a product of a power of $2$ and a power of $3$ in many of
the terms. Is there a reasonable procedure for simplifying this expression?
 A: In this case, it is probably simpler to chop the string up into chunks of 2 characters. Then, for each pair of characters there are 3 options for the first character, and 2 for the second character, so 6 options total. There are $n$ of these pairs in a row, so there are $6^n$ such strings.
A: Although Mees De Vries has suggested a brilliant solution, here is another approach to solve this problem. Out of $n$ odd positions, choose any $k$ positions for $0$s which can be done in ${n \choose k}$ ways. The remaining $2n-k$ positions can be filled with $1$s and $2$s in $2^{2n-k}$ ways. As such, the total number of ternary strings with $0$s only allowed in odd indices is:
$$
\sum_{k=0}^{n}{n \choose k}2^{2n-k} = 2^n\sum_{k=0}^{n}{n \choose k}2^{n-k} =  2^n(1+2)^n = 2^n3^n = 6^n
$$
A: You are doing inclusion-exclusion wrong. There's nothing to exclude-include here.
From $9^n$ you need to substract the prohibited configurations, which are those that have $1,2 \cdots n$ zeros in even positions.But this is given straighforwardly by the sum (no inclusion-exclusion!)
$$ n2^{n-1}3^n  +\binom{n}{2}2^{n-2}3^n + \binom{n}{3}2^{n-3}3^n +\cdots$$
(the first term counts the number of strings having exactly one prohibited zero; the second those containing exactly two, and so on)
The above can be expressed as a binomial sum; it equals
$$ 3^n \left ( (2+1)^n - 2^n\right ) = 9^n - 6^n $$
Then the desired total count is 
$$ 9^n -(9^n - 6^n)=6^n  $$
See Mees de Vries's answer for a much more natural and simple way.
