1

For each integer n>= 1, let $t_n$ be the number of strings of n letters that can be produced by concatenating (running together) copies of the strings "a", "bc", and "cb"

For example, $t_1$ = 1("a" is the only possible string) and $t_2$ = 3 ("aa", "bc" and "cb" are the possible strings).

a) Find $t_3$ and $t_4$

b) Find the recurrence for $t_n$ that holds for all n>=3. Explain why your recurrence gives $t_n$.

I am not sure if I understand the question. How do we get $t_2$ = "aa"? How would i get $t_3$ adn $t_4$ and the recurrence for $t_n$? Any guidance would be appreciated.

SAR
  • 297
  • a) can be done by careful listing and counting. For example, for $t_3$, the possibilities are aaa, abc, acb, bca, cba. – André Nicolas May 26 '16 at 17:32
  • So would $t_4$ have 4 characters for each string? – SAR May 26 '16 at 19:18
  • $t_4$ is the number of strings of length $4$ and of the specified shape. So $4$ characters. You are asked in a) to list them all, and then count them. Here are a few to get you started: aaaa, aabc, aacb. Then in b) we find a simple way of counting without listing. Work on it a little more. If you do not succeed and no one has answered, please send me a message and I will write an answer. – André Nicolas May 26 '16 at 19:23

1 Answers1

1

a) Let $S_n$ be the collection of $n$ character strings that can be made using the character strings a, and/or bc and/or cb. Then $t_n$ is the number of strings in $S_n$.

For example, $S_2$ consists of the character strings aa, bc, and cb. Thus $t_2=3$.

In part a), we are asked to find $t_3$ and $t_4$. There are more streamlined ways of doing it, but we will simply list all the strings in $S_3$ and count. Similarly, we will list all the strings in $S_4$ and count.

For $S_3$, here are all of them: aaa, abc, acb, bca, cba. Thus $t_3=5$.

For $S_4$, here are all of them: aaaa, aabc, aacb,abca, acba, bcaa, cbaa, bcbc, bccb, cbbc, cbcb. Thus $t_4=11$.

b) Listing and counting can be tedious, and also error-prone. So we find a more efficient way of calculating $t_n$, by finding a recurrence.

Let us count the number of strings in $S_{n+1}$ efficiently. Such a string can be of one of two types:

A Type (i) string is one that ends with an a;

A Type (ii) string is one that ends with bc or cb.

Any Type (i) string with $n+1$ characters is obtained by appending an a to any string in $S_n$, and different strings in $S_n$ yield different Type (i) strings of length $n+1$. Thus there are $t_n$ Type (i) strings with $n+1$ characters.

Any Type (ii) string with $n+1$ characters can be obtained by appending bc or cb to any string in $S_{n-1}$. Thus there are $2t_{n-1}$ Type (ii) strings of length $n+1$. It follows that $$t_{n+1}=t_n+2t_{n-1}.\tag{1}$$ The above recurrence is easy to compute with. For example, we saw that $t_3=5$ and $t_4=11$. It follows that $t_5=21$, and therefore $t_6=43$.

Remark: One can even use recurrence (1) to find a simple closed form formula for $t_n$, but since the problem did not ask for that we shall not do so.

André Nicolas
  • 507,029