MathDB

A string of length

n

is a sequence of

n

characters from a specified set. For example,

BCAAB

is a string of length 5 with characters from the set

\{A,B,C\}

. A substring of a given string is a string of characters that occur consecutively and in order in the given string. For example, the string

CA

is a substring of

BCAAB

but

BA

is not a substring of

BCAAB

. [*]List all strings of length 4 with characters from the set

\{A,B,C\}

in which both the strings

AB

and

BA

occur as substrings. (For example, the string

ABAC

should appear in your list.) [*]Determine the number of strings of length 7 with characters from the set

\{A,B,C\}

in which

CC

occures as a substring. [*]Let

f(n)

be the number of strings of length

n

with characters from the set

\{A,B,C\}

such that [*]

CC

occurs as a substring, and[*]if either

AB

BA

occurs as a substring then there is an occurrence of the substring

CC

to its left. (for example, when

n\;=\;6

, the strings

CCAABC

and

ACCBBB

and

CCABCC

satisfy the requirements, but the strings

BACCAB

and

ACBBAB

and

ACBCAC

do not). Prove that

f(2097)

is a multiple of

97

Problem Statement