# 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?

• Split the string according to the even/odd posititions and you'll get two strings with length $n$: the first string over the alphabet $\{0,1,2\}$, the second string over the alphabet $\{1,2\}$. So we have $3^n\cdot 2^n$ chances since the splitting procedure is a bijection, actually. Sep 22, 2016 at 0:28

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.

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

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.