Hockey sticks on planet ABBABA
Question: On the planet ABBABA, the inhabitants have a binary language where the only two letters in their alphabet are A and B. The language is incredibly efficient and complex in that every finite sequence of A’s and B’s is a valid word. How many of the words in this language have exactly five A’s and at most five B’s?
For instance, ABAAABA, AAAAA, and BBBBBAAAAA are all valid such words, since they all have five A’s and no more than five B’s.
Answer: 462.
We’ll start with a straightforward counting method, and then go on to find a much faster method that will also lead us to an elegant combinatorial proof of a well-known binomial coefficient identity.
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 ${7}\choose {5}$ ways to choose $5$ of the $7$ letters to be the A’s, so there are ${7}\choose {5}$ possibilities in this case.
Similarly, there are ${8}\choose {5}$ words having five A’s and three B’s, ${9}\choose {5}$ with four B’s, and ${10}\choose {5}$ with five B’s. The total number of words is therefore \[{5\choose 5}+{6\choose 5}+{7\choose 5}+{8\choose 5}+{9\choose 5}+{10\choose 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 \[{m\choose m} + { {m+2}\choose {m}}+\cdots + {n\choose m}={ {n+1}\choose {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 ${11}{6}$, which is $462$, avoiding the summation above.
Interpretation as ${11}\choose {6}$
Since the answer turns out to be the single binomial coefficient ${11}\choose {6}$, we can ask if there is a direct way to see this answer. One possible interpretation of ${11}\choose {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} |={11 \choose 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 \[{m\choose m}+{ {m+1}\choose m}+{ {m+2}\choose m}+\cdots + {n \choose m}={ {n+1}\choose {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.