**Answer:** 462.

## Direct counting approach

Perhaps the most intuitive way to approach the problem is to break the problem into cases based on the number of B’s. If there is no B in the word, there is only one word, namely AAAAA. If there is one B, it can be in any of the six positions between the five A’s, so there are 6 possibilities.

If there are two B’s, we wish to count the number of ways of rearranging the letters AAAAABB. This can be viewed as a variant of the “Mississippi problem,” giving us $\frac{7!}{5!2!}=21$ possibilities. Equivalently, we can view a rearrangement as a choice of which five of the seven letters in the word are the A’s (with the other two being the B’s). There are $\binom{7}{5}$ ways to choose $5$ of the $7$ letters to be the A’s, so there are $\binom{7}{5}$ possibilities in this case.

Similarly, there are $\binom{8}{5}$ words having five A’s and three B’s, $\binom{9}{5}$ with four B’s, and $\binom{10}{5}$ with five B’s. The total number of words is therefore $$\binom{5}{5}+\binom{6}{5}+\binom{7}{5}+\binom{8}{5}+\binom{9}{5}+\binom{10}{5}$$ which comes out to $$1+6+21+56+126+252=462.$$

Those readers with a background in problem solving or discrete math may recognize that the sum of binomial coefficients above can be simplified using the Hockey Stick Identity, namely $$\binom{m}{m}+\binom{m+1}{m}+\binom{m+2}{m}+\cdots + \binom{n}{m}=\binom{n+1}{m+1}.$$ The “Hockey Stick” name comes from the shape these binomial coefficients spell out in Pascal’s triangle. Highlighted below are the entries involved for $m=2$ and $n=5$, with the purple highlighted entries adding up to the blue entry, forming a hockey stick shape in the triangle.

$$\begin{array}{ccccccccccccc}

& & & & & & 1 & & & & & & \\

& & & & & 1 & & 1 & & & & & \\

& & & & 1 & & 2 & & \color{purple}{\mathbf{1}} & & & & \\

& & & 1 & & 3 & & \color{purple}{\mathbf{3}} & & 1 & & & \\

& & 1 & & 4 & & \color{purple}{\mathbf{6}} & & 4 & & 1 & & \\

& 1 & & 5 & & \color{purple}{\mathbf{10}} & & 10 & & 5 & & 1 & \\

1 & & 6 & &15 & &\color{blue}{\mathbf{20}} & &15 & & 6 & & 1

\end{array}$$

In our case, the hockey stick identity tells us that our summation is simply $\binom{11}{6}$, which is $462$, avoiding the summation above.

## Interpretation as $\binom{11}{6}$

Since the answer turns out to be the single binomial coefficient $\binom{11}{6}$, we can ask if there is a direct way to see this answer. One possible interpretation of $\binom{11}{6}$ in this context is the number of words in the ABBABA language having exactly six A’s and five B’s. Let $W_{6,5}$ be the set of all such words. It then suffices to find a bijection $f$ from $W_{6,5}$ to the set of all words with exactly five A’s and at most five B’s, which in this notation may be written as $\bigcup_{i\le 5} W_{5,i}$.

We define the bijection as follows: given a word $w$ in $W_{6,5}$, define $f(w)$ to be the word formed by deleting the rightmost A and any B’s to the right of it. For example, $$f(\text{ABAABAAABBB})=\text{ABAABAA}.$$ Then $f(w)$ is in $W_{5,i}$ for some $i\le 5$. Moreover, this function has an inverse, since given a word $v$ in some $W_{5,i}$ where $i\le 5$, we can simply append ABB $\cdots$ B to $v$ where the number of B’s we add makes for a total of five B’s. For instance, the reverse map sends ABAABAA back to ABAABAAABBB.

This bijection shows that the size of our set of words is equal to $|W_{6,5}|=\binom{11}{6}=462$ immediately.

## Proof of Hockey Stick

The above bijection can be generalized to give a very nice proof of the Hockey Stick identity. Indeed, the left hand side of the equation $$\binom{m}{m}+\binom{m+1}{m}+\binom{m+2}{m}+\cdots + \binom{n}{m}=\binom{n+1}{m+1}$$ can be interpreted as $|\bigcup_{i\le n-m} W_{m,i}|$ and the right hand side as $|W_{m+1,n-m}|$. Then we can define a map $$f:W_{m+1,n-m}\to \bigcup_{i\le n-m} W_{m,i}$$ by dropping the last A and any B’s to the right of it, as above. It is invertible, since we can reverse the map by adding an A and an appropriate number of B’s to the shorter word. Thus $f$ is a bijection and the identity follows. QED

*This bijective proof is the nicest I’ve ever seen for the Hockey Stick identity. Thanks to Chris Jeuell for sharing this mathematical gemstone with me.*

hmm in my opinion the nicest is the following:

count subsets of size k of {1, 2, …, n}. One way is the direct binomial coefficient. The other way is to consider the largest element of such a subset, count, and sum over all possible largest elements. Equating gives hockey stick!