1
$\begingroup$

The questions is: for $A_n$ find all ternary strings of length $n ≥ 0$ that don't include substring $”11”$. Provide answer in form of:

a) recurrence relation
b) combinatorial expression

After that, for $B_n$ take $A_n$ and exclude strings that also have substring $”12”$ and end with $”1”$ (at the same time).

The biggest issue for me comes with combinatorial expression, whatever I try I cannot include all variations and get kind of lost. Might appreciate a bit of help on recurrence relation as well.

$\endgroup$
1
  • $\begingroup$ Alright, I have figured out recurrence relations... Can anyone help with combinatorics? $\endgroup$ – N. Vinogradov Dec 13 '15 at 23:16
0
$\begingroup$

Know this is old, but this is an interesting problem! Let A be a ternary string of length $n$ which does not include the substring $11$. If A does not end in a $1$, then A can be broken up into a unique sequence of the atomic strings $0$, $2$, $10$ and $12$; each $1$ must be followed by a $0$ or $2$, and any remaining characters are either $0$ or $2$. Conversely any string of length $n$ comprised of these atomic strings meets our conditions.

To count the number of such strings of length $n$, let $i$ be the number of length 2 atoms ($10$ and $12$) in the string. The total number of strings of length $n$ using $i$ length 2 atoms from our set is ${{n-i}\choose{i}}2^{n-i}$. To see this, note that we need $i$ length 2 atoms and $n-2i$ length 1 atoms to create a string of length $n$, so a total of $n-i$ atoms. From the $n-i$ available positions in the string, we pick $i$ positions to get length 2 atoms, and once they are picked, there are $2^i$ ways to fill in length 2 atoms. The remaining $n-2i$ positions are filled with length 1 atoms, which can be done in $2^{n-2i}$ ways.

So the total number of length $n$ strings not ending in a $1$ with no $11$ substring is $\sum\limits_{i=0}^{\lfloor\frac{n}{2}\rfloor}{{n-i}\choose{i}}2^{n-i}$.

The number of such strings that do end in a $1$ is calculated similarly, noting that such a string is comprised of a string of length $n-1$ with no $11$ substring that does not end in a $1$, followed by a $1$. Hence there are $\sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}{{n-1-i}\choose{i}}2^{n-1-i}$ such strings.

Thus $A_n = \sum\limits_{i=0}^{\lfloor\frac{n}{2}\rfloor}{{n-i}\choose{i}}2^{n-i} + \sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}{{n-1-i}\choose{i}}2^{n-1-i}$.

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