Braille puzzle

We will solve a general version of this problem, where the Braille characters are $m\times n$. That is, there are $m$ rows and $n$ columns.

When two characters are translations of one another, we will say they are equivalent. The equivalence class of a character is the set of all characters equivalent to that particular one. For example, in the $3\times 2$ case, a single dot has six equivalents, and two vertically stacked dots have 4 equivalents. In the figure below, each row shows equivalent characters.

The size of an equivalence class is determined by the footprint of its characters. That is, the smallest rectangle that contains all the dots. For example, in the $6\times 4$ case below, the character shown has a $4\times 4$ footprint (the red outline):

If we translate this character, we see that it can occupy $3$ different vertical locations and $2$ different horizontal locations, for a total of $3\times 2 = 6$ equivalent characters. In general, if the footprint of a character is $i\times j$, then its equivalence class contains $(m-i+1)(n-j+1)$ elements.
Let us define:

• $f(m,n)$: The size of the largest set of $m\times n$ characters such that no two characters are translations of one another. In other words, the number of different equivalence classes.
• $g(i,j)$: The number of different characters that have a footprint $i\times j$.

The problem is asking us to calculate $f(m,n)$, but based on the discussion above, it is clear that:
\[
f(m,n) = \sum_{i=1}^m\sum_{j=1}^n g(i,j)
\]Computing $g(i,j)$ is fundamentally a (tedious) counting problem: Given a $i\times j$ rectangle, how many dot patterns can we make that fit snugly in that rectangle? The size of the footprint is determined by the dots on the border, so we separate the corners, edges, and middle section of the footprint:

Depending on which corners are filled in, this determines what the edges can look like so that the character fit snugly in the $i\times j$ rectangle. In particular, we have the following five cases:

1. No corners filled in. There must therefore be at least one dot on each edge. The vertical and horizontal edges contain $i-2$ and $j-2$ slots, respectively. Since we want to exclude the “empty” edge, we can fill in the edges in $\bigl(2^{i-2}-1\bigr)^2\bigl(2^{j-2}-1\bigr)^2$ ways.
2. One corner filled in. The adjacent edges can be filled in arbitrarily, while the two opposite edges must each contain a dot. Thus we can fill the edges in $\bigl(2^{i-2}-1\bigr)2^{i-2}\bigl(2^{j-2}-1\bigr)2^{j-2}$ ways. This can happen in 4 different ways (depending on which corner is filled).
3. Two bottom (or top) corners filled in. The three adjacent edges can be filled in arbitrarily, while the opposite vertical edge must contain a dot. Thus we can fill the edges in $\bigl(2^{i-2}\bigr)^2\bigl(2^{j-2}-1\bigr)2^{j-2}$ ways. This can happen in 2 different ways (we can pick the bottom or top corners).
4. Two left (or right) corners filled in. The three adjacent edges can be filled in arbitrarily, while the opposite horizontal edge must contain a dot. Thus we can fill the edges in $\bigl(2^{i-2}-1\bigr)2^{i-2}\bigl(2^{j-2}\bigr)^2$ ways. This can happen in 2 different ways (we can pick the left or right corners).
5. Two opposite corners filled in (or more). In this case, all four edges can be filled in arbitrarily since opposite corners completely determine the footprint. We therefore count $\bigl(2^{i-2}\bigr)^2\bigl(2^{j-2}\bigr)^2$ ways. This can happen in 7 different ways, since we can have only the opposite corners (2 ways), any three corners (4 ways), or all four corners (1 way).

For each of these cases, we can fill in the central $(i-2)\times(j-2)$ portion of the character arbitrarily, which means we should add all the above cases together, and multiply the total by $2^{(i-2)(j-2)}$.

Putting all of this together, we get our final tally:
\begin{multline}
g(i,j) = 2^{(i-2)(j-2)}\biggl(\bigl(2^{i-2}-1\bigr)^2\bigl(2^{j-2}-1\bigr)^2 \\
+ 4 \cdot \bigl(2^{i-2}-1\bigr)2^{i-2}\bigl(2^{j-2}-1\bigr)2^{j-2}
+ 2 \cdot \bigl(2^{i-2}\bigr)^2\bigl(2^{j-2}-1\bigr)2^{j-2} \\
+ 2 \cdot \bigl(2^{i-2}-1\bigr)2^{i-2}\bigl(2^{j-2}\bigr)^2
+ 7 \cdot \bigl(2^{i-2}\bigr)^2\bigl(2^{j-2}\bigr)^2 \biggr)
\end{multline}One final wrinkle: The above formula only makes sense if $i\geq 2$ and $j\geq 2$. Otherwise, our footprint will be a degenerate rectangle (it will not have four corners). Accounting for this, we obtain the complete version of $g(i,j)$:
\[
g(i,j) = \begin{cases}
\text{(formula above)} & i\geq 2\text{ and }j\geq 2 \\
2^{i-2} & i\geq 2\text{ and }j=1\\
2^{j-2} & i=1\text{ and }j\geq 2\\
1 & i=j=1
\end{cases}
\]To verify that the formula is correct, we can count the total number of characters by separating by footprint:
\begin{align}
& \text{(total $m\times n$ characters)} \\
&= \sum_{i=1}^m\sum_{j=1}^n \text{(characters with an $i\times j$ footprint)}\cdot \text{(size of $i\times j$ equiv. class)}\\
&= \sum_{i=1}^m\sum_{j=1}^n g(i,j) \cdot (m-i+1)(n-j+1) \\
&= 2^{mn}-1
\end{align}The last line was evaluated with Mathematica, and it actually worked! The reason for the “$-1$” is that we are excluding the “all-empty” character in our count.

Now that we have verified our formula for $g(i,j)$, we can substitute it in to the formula for $f(m,n)$ we derived earlier:
\[
f(m,n) = \sum_{i=1}^m\sum_{j=1}^n g(i,j)
\]Again, I relied on Mathematica to derive the analytic expression for this sum, and I obtained the following formula:

$\displaystyle
f(m,n) = \bigl(2^{m-1}-1\bigr) \bigl(2^{n-1}-1\bigr) 2^{(m-1) (n-1)}+2^{m n-1}
$

Given the relative simplicity of this final answer, I’m expecting there to be a much more elegant way to solve this problem than the approach I used. Let me know in the comments!

Solutions to special cases

Now that we have a general formula, we need only substitute the appropriate values for $m$ and $n$ to solve the problem. For the first problem, we find:
\[
f(3,2) = 44
\]Here is a picture that shows all $44$ characters. For each equivalence class, I chose the representative in the lower-left corner of the grid. I also indicated in red the number of elements in each equivalence class. As expected, if you sum all the red numbers you obtain $63 = 2^{6}-1$, which is the total number of non-empty characters.

For the extra credit problem, we find:
\[
f(6,4) = 15,\!499,\!264
\]