{"id":4210,"date":"2025-09-12T11:02:31","date_gmt":"2025-09-12T16:02:31","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=4210"},"modified":"2025-09-12T11:21:32","modified_gmt":"2025-09-12T16:21:32","slug":"letter-boxed","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/letter-boxed\/","title":{"rendered":"Letter Boxed"},"content":{"rendered":"

This week’s Fiddler<\/a> is about the popular NY Times puzzle Letter Boxed<\/a>.<\/p>\n

\nyou must connect letters together around a square to spell out words (they don’t have to be actual English words!). However, from any given letter, the next letter cannot be on the same side of the square. How many distinct valid sequences are there that include each letter exactly once?
\n\"\"\n<\/p><\/blockquote>\n

My solution:
\n[Show Solution]<\/a><\/p>\n

\n

A related problem: Counting Carlitz words<\/h3>\n

This problem is related to a well-known combinatorial problem involving counting special arrangements of symbols.<\/p>\n

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”<\/a> by Jair Taylor.<\/p>\n

The result is as follows:<\/p>\n

\nTheorem<\/strong>
\nThe number of Carlitz words on an alphabet of $m$ symbols with the $i^\\text{th}$ symbol repeated $k_i$ times is given by the formula:
\n\\[
\nN = \\int_0^\\infty e^{-t} \\prod_{i=j}^m l_{k_j}(t)\\,\\mathrm{d}t
\n\\]where the function in the integrand is the polynomial defined as:
\n\\[
\nl_k(t) = \\sum_{i=0}^k (-1)^{k+i}\\binom{k-1}{k-i}\\frac{t^i}{i!}
\n\\]\n<\/div>\n

 
\nThe first several such functions are given by:
\n\\begin{align*}
\nl_1(t)&= t \\\\
\nl_2(t)&= \\frac{t^2}{2}-t \\\\
\nl_3(t)&= \\frac{t^3}{6}-t^2+t \\\\
\nl_4(t)&= \\frac{t^4}{24}-\\frac{t^3}{2}+\\frac{3 t^2}{2}-t \\\\
\nl_5(t)&= \\frac{t^5}{120}-\\frac{t^4}{6}+t^3-2 t^2+t
\n\\end{align*}Therefore, to answer the MISSISSIPPI question, we see that the word is made up of: (M, PP, IIII, SSSS). Applying the formula:
\n\\begin{align*}
\nN &= \\int_0^\\infty e^{-t} l_1(t) l_2(t) l_4(t)^2\\,\\mathrm{d}t \\\\
\n&= \\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 \\\\
\n&= 2016
\n\\end{align*}NOTE:<\/strong> 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!<\/p>\n

Counting Letter Boxed words<\/h3>\n

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.<\/p>\n

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<\/em>; 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$.<\/p>\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:<\/p>\n

$\\displaystyle
\nF(n,m) = (m!)^n \\int_0^\\infty e^{-t}\\, l_m(t)^n\\,\\mathrm{d}t
\n$<\/span><\/p>\n

with $l_m(t)$ defined above.<\/p>\n

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