2
$\begingroup$

The prompt asks us to find the number of n-long sequences of letters 'a', 'b', 'c', where letter 'a' cannot appear on odd numbered positions, positions start from number 1.

The way I tried solving it was, Since there are $\lceil \frac{n}{2} \rceil$ odd positions and $n - \lceil \frac{n}{2} \rceil$ or $\lfloor \frac{n}{2} \rfloor$ even positions.

Even positions can be occupied in $3^{\lfloor \frac{n}{2} \rfloor}$ ways and odd positions can be occupied in $2^{\lceil \frac{n}{2} \rceil}$ ways, putting both together we have $$3^{\lfloor \frac{n}{2} \rfloor} \cdot 2^{\lceil \frac{n}{2} \rceil} \text{ ways of choosing n sequences}$$

Is this the right way to solve this problem? Can this be solved using inclusion-exclusion principle? should it?

$\endgroup$

2 Answers 2

2
$\begingroup$

I don't see any flaw in your solution and this is a clean way of solving this kind of problem.

For your second question, Inclusion-Exclusion Principle is generally used when we have some cases that are counted more than once. When this is the case, we exclude them from the result first, then include some of them again in order not to completely exclude them from the result.

Now, in your case, you already eliminated the cases where the letter 'a' appears on odd numbered indexes. For the rest of the cases, even if there is a different letter in only one index, two sequences are different (For example take "babacbc" and "babacbb"). So your answer already counts each sequence exactly once with given condition and there is no sequence that is counted more than once.

$\endgroup$
2
$\begingroup$

A general method to solve this kind of problem is to write an unambiguous regular expression representing the language. In your case, if $A$ is the alphabet, the language is $((b+c)A)^*(b+c+1)$. Now, you replace every occurrence of $a, b, c$ by $t$ to get $$ ((2t)(3t))^*(2t+1) = (6t^2)^*(2t+1) = {2t + 1 \over (1-6t^2)} $$ You just have now to find the $n$-th term of the Taylor expansion of this fraction. You will of course recover your solution. Using Sagemaths, one gets for instance

var('t'); 
taylor (((2*t + 1) /(1-6*t^2)), t, 0, 10);

$7776t^{10} + 2592t^9 + 1296t^8 + 432t^7 + 216t^6 + 72t^5 + 36t^4 + 12t^3 + 6t^2 + 2t + 1$

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