Letter Boxed

A related problem: Counting Carlitz words

This problem is related to a well-known combinatorial problem involving counting special arrangements of symbols.

Given an ordered list of letters (a word) such as “MISSISSIPPI”, one can ask: How many distinct rearrangements of these letters have no adjacent letters the same? This is known as a Carlitz word, named after the American mathematician Leonard Carlitz. There is a stunning formula for calculating this, which is explained in detail in the paper “Counting words with Laguerre polynomials” by Jair Taylor.

The result is as follows:

 
The first several such functions are given by:
\begin{align*}
l_1(t)&= t \\
l_2(t)&= \frac{t^2}{2}-t \\
l_3(t)&= \frac{t^3}{6}-t^2+t \\
l_4(t)&= \frac{t^4}{24}-\frac{t^3}{2}+\frac{3 t^2}{2}-t \\
l_5(t)&= \frac{t^5}{120}-\frac{t^4}{6}+t^3-2 t^2+t
\end{align*}Therefore, to answer the MISSISSIPPI question, we see that the word is made up of: (M, PP, IIII, SSSS). Applying the formula:
\begin{align*}
N &= \int_0^\infty e^{-t} l_1(t) l_2(t) l_4(t)^2\,\mathrm{d}t \\
&= \int_0^\infty e^{-t} \, t \left( \frac{t^2}{2}-t\right) \left(\frac{t^4}{24}-\frac{t^3}{2}+\frac{3 t^2}{2}-t\right)^2\,\mathrm{d}t \\
&= 2016
\end{align*}NOTE: An easy way to evaluate the integral above is to expand the polynomial part and use the fact that $\int_0^\infty e^{-t}t^n\,\mathrm{d}t=n!$ This can also convince you that the integrals always evaluate to integers!

Counting Letter Boxed words

Back to Letter Boxed, we have a shape with $n=4$ sides, and each side has $m$ distinct symbols. We want to find the total number of words where a symbol from the same side is never used twice in a row.

This is related to the problem of counting Carlitz words; we start by counting the number of Carlitz words where the symbols on a given side are treated as identical. For example, if there are 3 letters per side as in the picture at the top of the page, we count Carlitz words for “111222333444”. Each different Carlitz word provides a template; we then need to assign the letters from each side to the corresponding number in the template. e.g., the 1’s encode ABC, and there are 3! ways of ordering those. Then the 2’s encode DEF, and there are 3! ways of ordering those, and so on. Ultimately, we multiply our number of Carlitz words by $(m!)^n$.

Therefore, a formula for the total number of legal Letter Boxed words played on a shape with $n$ sides and $m$ letters per side is:

$\displaystyle
F(n,m) = (m!)^n \int_0^\infty e^{-t}\, l_m(t)^n\,\mathrm{d}t
$

with $l_m(t)$ defined above.

Here are some values for $F(n,m)$ for $n$ sides and $m$ symbols per side.
\[
\begin{array}{c|ccccc}
n\backslash m & 1 & 2 & 3 & 4 & 5 \\ \hline
1& 1 & 0 & 0 & 0 & 0 \\
2& 2 & 8 & 72 & 1152 & 28800 \\
3& 6 & 240 & 37584 & 15095808 & 12420864000 \\
4& 24 & 13824 & 53529984 & 751480602624 & 27917203599360000 \\
5& 120 & 1263360 & 152458744320 & 93995798935633920 & 197726965332480000000000 \\
\end{array}
\]Some observations:

• In the first row, we only have one side. So if that side contains more than one letter, it’s impossible to make any words since we would be forced to use the same side for consecutive letters. This is why $F(1,m)=1$ if $m=1$ and $0$ otherwise.
• In the first column, we only have one symbol per side. Therefore, we don’t need to worry about letters from consecutive sides, and we see that $F(n,m)=n!$.

For standard Letter Boxed ($n=4$), we can read off the fourth row:

• Two letters per side: $F(4,2) = 13824$.
• Three letters per side: $F(4,3) = 53529984$.