Ternary Strings of Length $2n$

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.