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?
Best Answer
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.