, 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.