, 2022

Solution 1

For each Bauman string of length 5 in which the first and last
letters are both $A$, the second and
fourth letters are not $A$.

For such Bauman strings, either the third letter is $A$, or the third letter is not $A$.

Case 1: The third letter is $A$.

In this case, the string is of the form $A\underline{\hspace{5mm}}A\underline{\hspace{5mm}}A$.

There are 4 choices for the second letter ($B,C,D$, or $E$) and 4 choices for the fourth letter,
and so there are $4\times4=16$ such
Bauman strings.

Case 2: The third letter is not $A$.

In this case, the string is of the form $A\underline{\hspace{5mm}}x\underline{\hspace{5mm}}A$, where the
third letter $x$ is $B,C,D$, or $E$, and so there are 4 choices for the
third letter.

The second letter must be different than the third letter and must not
be $A$, and so there are 3 choices
for the second letter.

Similarly, there are 3 choices for the fourth letter, and so there are
$4\times3\times3=36$ such Bauman
strings.

In total, the number of Bauman strings of length 5 in which the first
and last letters are both $A$ is
$16+36=52$.

Solution 2

For each Bauman string of length 5 in which the first and last
letters are both $A$, either the
second and fourth letters are the same, or they are different.

Case 1: The second and fourth letters are the same.

In this case, the string is of the form $Ax\underline{\hspace{5mm}}xA$.

There are 4 choices for the second letter ($B,C,D$, or $E$) and 1 choice for the fourth letter
since it is the same as the second letter.

The third letter must be different than the second and fourth letters
(which are the same) and so there are 4 choices for the third
letter.

Thus, there are $4\times1\times4=16$
such Bauman strings.

Case 2: The second and fourth letters are different.

In this case, the string is of the form $Ax\underline{\hspace{5mm}}\, yA$, where $x$ and $y$ represent different letters.

There are 4 choices for the second letter ($B,C,D$, or $E$) and 3 choices for the fourth letter
(it is different than the second letter and not $A$).

The third letter must be different than the second and fourth letters
(which are different) and so there are 3 choices for the third
letter.

Thus, there are $4\times3\times3=36$
such Bauman strings.

In total, the number of Bauman strings of length 5 in which the first
and last letters are both $A$ is
$16+36=52$.
Solution 1

We may determine the number of Bauman strings of length 6 that
contain more than one $B$
indirectly.

That is, we may subtract the number of Bauman strings that contain 0
$B$’s and the number of Bauman
strings that contain exactly 1 $B$
from the total number of Bauman strings of length 6.

For a Bauman string of length 6 (with no restrictions), there are 5
choices for the first letter and 4 choices for each of the remaining
letters, and so there are a total of $5\times4^5=5120$ such strings.

For a Bauman string of length 6 that contains 0 $B$’s, there are 4 choices for the first
letter and 3 choices for each of the remaining letters, and so there are
a total of $4\times3^5=972$ such
strings.

Next, we count the number of Bauman strings that contain exactly 1
$B$.

If the first letter of the string is a $B$, then there are 4 choices for the
second letter and 3 choices for each of the remaining four
letters.

Similarly, if the last letter is a $B$, then there are 4 choices for the
letter adjacent to the $B$ and 3
choices for each of the remaining four letters.

Thus, there are $1\times4\times3^4=324$ strings that begin
with a $B$ and 324 strings that end
with a $B$.

If the second letter of the string is a $B$, then there are 4 choices for the first
letter, 4 choices for the third letter, and 3 choices for each of the
fourth, fifth and sixth letters.

Thus, there are $4\times1\times4\times3^3=432$ such
strings.

Similarly, if the third, fourth or fifth letter in the string is a $B$, then there are 432 such strings.

In total, there are $5120-972-2\times324-4\times432=1772$
Bauman strings of length 6 that contain more than one $B$.

Solution 2

A Bauman string of length 6 cannot contain more than 3 $B$’s (confirm for yourself why this is
true before proceeding).

We may determine the number of Bauman strings of length 6 that contain
more than one $B$ directly.

That is, we may count the number of strings that contain exactly 3 $B$’s and the number of strings that
contain exactly 2 $B$’s.

Thus, there are two cases to consider.

Case 1: The Bauman string has exactly 3 $B$’s

In this case, the string must take one of four possible forms: $$B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}},~~ B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B ,~~ B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B ,~~ \underline{\hspace{5mm}}\,B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B.$$ We begin by counting the number of strings of the form
$B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}$.

There are 4 choices for the second letter ($A,C,D$, or $E$), 4 choices for the fourth letter, and
4 choices for the sixth letter, and so there are $4^3=64$ such strings.

Similarly, there are $4^3=64$ strings
of the form $\underline{\hspace{5mm}}\,B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B$.

It is worth noting that $B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}$ and $\$\underline{\hspace{5mm}}\,B\underline{\hspace{5mm}}B\underline{}$
}B$ have identical forms when one is read left to right and the
other right to left.

We may call such pairs of forms symmetric, and recognize that
under the same restrictions, symmetric forms have an equal number of
Bauman strings.

For strings of the form $B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B$, there are 4 choices for the
second letter, 4 choices for the fourth letter, and 3 choices for the
fifth letter (since the fifth letter must be different than $B$ and different than the fourth letter,
which is not $B$), and so $4^2\times3=48$ such strings.

Since $B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B$ is symmetric to $B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B$, there are similarly $4^2\times3=48$ strings of this form.

Thus, there are $2\times64+2\times48=224$ Bauman strings
with exactly 3 $B$’s.

Case 2: The Bauman string has exactly 2 $B$’s

In this case, the string must take one of ten possible forms.

Eight of these occur in one of the following four symmetric pairs $$B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}} \textrm{ \ and \ } \underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B \textrm{,\ \ \ \ \ \ \ } B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}} \textrm{ \ and \ } \underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B,$$
$$B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{ }B\underline{\hspace{5mm}} \textrm{ \ and \ } \underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B \textrm{,\ \ \ \ \ \ \ } \underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}} \textrm{ \ and \ } \underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}$$ and
the final two forms (which are not a symmetric pair) are $$B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B \textrm{ \ and \ }$$ $$\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}.$$ We begin by counting the number of strings of
the form $B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}$.

There are 4 choices for the second letter ($A,C,D$, or $E$), 4 choices for the fourth letter,
3 choices for each of the fifth and sixth letters, and so there are
$4^2\times3^2=144$ such
strings.

Similarly, there are $4^2\times3^2=144$ strings for each of the
next five forms listed above, $\$\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B,\, B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,, \,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B,$ \, $B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,, \textrm{}$ and }
$\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\$.$

For strings of the form $\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}$, there are 4
choices for the first letter, 4 choices for the third letter, 4 choices
for the fifth letter, and 3 choices for the sixth letter, and so there
are $4^3\times3=192$ such
strings.

Since $\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}$ is symmetric to $\underline{\hspace{5mm}}B\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}$, there are similarly $4^3\times3=192$ strings of this form.

Finally, there are $4\times3^3=108$ strings of the form $B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B$, and $4^3\times3=192$ strings of the form $\underline{\hspace{5mm}}B\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}B\underline{\hspace{5mm}}$.

Thus, there are $\$6\times144+2\times192+$
108+192 =1548 Bauman strings with exactly 2 B$’s.

In total, there are $224+1548=1772$ Bauman strings of length 6
that contain more than one $B$.
Solution 1

Consider all Bauman strings of length $n$ that begin with $C$.

There are 4 choices for each of the remaining $n-1$ letters, and so there are $4^{n-1}$ such Bauman strings.

Each of these strings either ends with $D$, or it does not end with $D$.

We call those that end with $D$,
$d_n$, and we define $|d_n|$ to be the number of such
strings.

Similarly, we call those that do not end in $D$, $x_n$, and we define $|x_n|$ to be the number of such
strings.

For example, $d_1$ represents the
Bauman strings of length $1$ that
begin with $C$ and end with $D$, and since no such string exists, then
$|d_1|=0$.

Similarly, $x_1$ represents the
Bauman strings of length $1$ that
begin with $C$ and do not end with
$D$, and so $|x_1|=1$ (the string is $C$).

We may confirm that $4^{n-1}=|d_n|+|x_n|$ when $n=1$, since $4^{1-1}=|d_1|+|x_1|=0+1$.

Further, we know that $|d_2|=1$ (the
string is $CD$), and $|x_2|=3$ (the strings are $CA$, $CB$, $CE$), and again confirm that $4^{2-1}=1+3$.

Next, consider the Bauman strings of length $n$ that begin with $C$ and do not end with $D$, that is, $x_n$.

Each of these strings could have a $D$ added to its end to form a Bauman
string of length $n+1$ that begins
with $C$ and ends with $D$, or $d_{n+1}$.

Since adding a $D$ to the end of
every string $x_n$ gives all possible
strings $d_{n+1}$, then $|d_{n+1}| = |x_n|$.

From our earlier work, we may confirm that $|d_2|=|x_1|=1$.

Further, $|x_{n+1}| = 4|d_n| +
3|x_n|$. Why is this true?

Every Bauman string of length $n+1$
that begins with $C$ and does not end
with $D$, that is $x_{n+1}$, is either a string $d_n$ with an $A$, $B$, $C$, or $E$ added to its end, or it is a string
$x_n$ that has a choice of 3 letters
added to its end (the letter added can not be $D$ and it can not be the last letter of
$x_n$, leaving 3
possibilities).

The number of strings $d_n$ that have
$A$, $B$, $C$, or $E$ added to its end is $4|d_n|$.

The number of strings $x_n$ that have
a choice of 3 letters added to its end is $3|x_n|$.

Therefore, we conclude that $|x_{n+1}| =
4|d_n| + 3|x_n|$.

From our earlier work, we may confirm that $|x_2|=4|d_1|+3|x_1|=4(0)+3(1)=3$.

We use these two formulas $|d_{n+1}| =
|x_n|$and$|x_{n+1}| = 4|d_n| +
3|x_n|$, which are equivalent to$|d_{n}| = |x_{n-1}|$and$|x_{n}| = 4|d_{n-1}| + 3|x_{n-1}|$, to
build the table below.

$n$
$|d_n|=|x_{n-1}|$
$|x_n|=4|d_{n-1}| + 3|x_{n-1}|$

1
$|d_1|=0$
$|x_1|=1$

2
$|d_2|=1$
$|x_2|=3$

3
$|d_3|=|x_{2}|=3$
$|x_3|=4|d_{2}| +
3|x_{2}|=4(1)+3(3)=13$

4
$|d_4|=|x_{3}|=13$
$|x_4|=4|d_{3}| +
3|x_{3}|=4(3)+3(13)=51$

5
$|d_5|=51$
$|x_5|=4(13)+3(51)=205$

6
$|d_6|=205$
$|x_6|=4(51)+3(205)=819$

7
$|d_7|=819$
$|x_7|=4(205)+3(819)=3277$

8
$|d_8|=3277$
$|x_8|=4(819)+3(3277)=13\,107$

9
$|d_9|=13\,107$
$|x_9|=4(3277)+3(13\,107)=52\,429$

10
$|d_{10}|=52\,429$
not needed

Therefore, the number of Bauman strings of length $10$ in which the first letter is $C$ and the last letter is $D$ is 52 429.

Solution 2

Let $S_{n}$ be the set of Bauman
strings of length $n$ in which the
first letter is $C$ and the last
letter is $D$.

Further, we define $|S_{n}|$ to be
the number of such strings.

For example, $S_2=\{CD\}$ and so
$|S_{2}|=1$, and $S_3=\{CAD, CBD, CED\}$ and so $|S_{3}|=3$.

Each string in $S_{10}$ is of the
form $C\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,\underline{\hspace{5mm}}\,D$ or $CT_8D$ where $T_8$ is a Bauman string of length 8 that
does not begin with $C$ and does not
end with $D$.

Therefore, $|S_{10}|=|T_8|$. The
number of such strings, $|T_8|$, is
equal to $$\begin{array}{cl} & \text{the total number of Bauman strings of length 8}\\ - & \text{the number of Bauman strings of length 8 that begin with } C\\ - & \text{the number of Bauman strings of length 8 that end with } D\\ + & \text{the number of Bauman strings of length 8 that begin with } C \text{ and end with } D \end{array}$$ In the above, we note that strings beginning with
$C$ include those that end with $D$, as well as others.

Similarly, strings that end with $D$
include those that begin with $C$, as
well as others.

Since we have subtracted the number of strings that begin with $C$ and end with $D$ twice from the total, we conclude by
adding the number of such strings.

For a Bauman string of length 8, there are 5 choices for the first
letter and 4 choices for each of the remaining 7 letters.

Thus, the total number of Bauman strings of length 8 is equal to $5\times4^7$.

For a Bauman string of length 8 that begins with $C$, there is 1 choice for the first letter
and 4 choices for each of the remaining 7 letters.

Thus, the total number of Bauman strings of length 8 that begin with
$C$ is equal to $1\times4^7$.

Also, the total number of Bauman strings of length 8 that end with $D$ is equal to $1\times4^7$.

The number of Bauman strings of length 8 that begin with $C$ and end with $D$ is equal to $|S_8|$.

Therefore, we get $$|S_{10}|=|T_8|=5\times4^7-1\times4^7-1\times4^7+|S_8|=3\times4^7+|S_8|$$
and so the number of Bauman strings of length 10 that begin with $C$ and end with $D$ is dependent on the number of Bauman
strings of length 8 that begin with $C$ and end with $D$.

At this point, we could repeat the process above to determine $|S_8|$, however it may be more efficient
to generalize the work above to determine a formula for $|S_n|$.

For integers $n\geq3$, each string
in $S_{n}$ is of the form $CT_{n-2}D$ where $T_{n-2}$ is a Bauman string of length
$n-2$ that does not begin with $C$ and does not end with $D$.

The number of such strings, $|T_{n-2}|$, is equal to $$\begin{array}{cl} & \text{the total number of Bauman strings of length } n-2\\ - & \text{the number of Bauman strings of length } n-2 \text{ that begin with } C\\ - & \text{the number of Bauman strings of length } n-2 \text{ that end with } D\\ + & \text{the number of Bauman strings of length } n-2 \text{ that begin with } C \text{ and end with } D \end{array}$$ For a Bauman string of length $n-2$, there are 5 choices for the first
letter and 4 choices for each of the remaining $n-3$ letters.

Thus, the total number of Bauman strings of length $n-2$ is equal to $5\times4^{n-3}$.

For a Bauman string of length $n-2$
that begins with $C$, there is 1
choice for the first letter and 4 choices for each of the remaining
$n-3$ letters.

Thus, the total number of Bauman strings of length $n-2$ that begin with $C$ is equal to $1\times4^{n-3}$.

Also, the total number of Bauman strings of length $n-2$ that end with $D$ is equal to $1\times4^{n-3}$.

The number of Bauman strings of length $n-2$ that begin with $C$ and end with $D$ is equal to $|S_{n-2}|$.

Therefore, we get $$|S_{n}|=|T_{n-2}|=5\times4^{n-3}-1\times4^{n-3}-1\times4^{n-3}+|S_{n-2}|=3\times4^{n-3}+|S_{n-2}|, \textrm{ for integers } n\geq3.$$ Using this recursive formula
and the fact that $|S_2|=1$, we get
$$\begin{array}{lllllll} |S_4|&=&3\times4^{4-3}+|S_{4-2}|&=&3\times4+|S_2|&=&13\\ |S_6|&=&3\times4^{6-3}+|S_{6-2}|&=&3\times4^3+|S_4|&=&205\\ |S_8|&=&3\times4^{8-3}+|S_{8-2}|&=&3\times4^5+|S_6|&=&3277\\ |S_{10}|&=&3\times4^{10-3}+|S_{10-2}|&=&3\times4^7+|S_8|&=&52\,429 \end{array}$$ The number of Bauman strings of length $10$ in which the first letter is $C$ and the last letter is $D$ is 52 429.