2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Sep 22, 2016 at 0:28

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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