Combinatorics › Permutations and arrangements › Arrangements of letters

Counting case-switching letter sequences

High school · ●●●●○ 100 pts

Bob writes a sequence of letters of the alphabet, each of which is either uppercase or lowercase, under these rules. If he has just written an uppercase letter, he either writes the same letter in lowercase next, or the next letter of the alphabet in uppercase. If he has just written a lowercase letter, he either writes the same letter in uppercase next, or the preceding letter of the alphabet in lowercase. For example,

a\,A\,a\,A\,B\,C\,D\,d\,c\,b\,B\,C

is such a sequence. How many sequences of 32 letters can he write that start at lowercase

a

and end at lowercase

z

counting with restrictions lattice paths