Braille characters are formed by raised dots arranged in a braille cell, a three-by-two array. With six locations for dots, each of which is raised or unraised, there are 26, or 64, potential braille characters.
Each of the 26 letters of the basic Latin alphabet (shown below) has its own distinct arrangement of dots in the braille cell. What’s more, while some arrangements of raised dots are rotations or reflections of each other (e.g., E and I, R and W, etc.), no two letters are translations of each other. For example, only one letter (A) consists of a single dot – if there were a second such letter, A and this letter would be translations of each other.
Of the 64 total potential braille characters, how many are in the largest set such that no two characters consist of raised dot patterns that are translations of each other?
Extra Credit In addition to six-dot braille, there’s also an eight-dot version. But what if there were even more dots? Let’s quadruple the challenge by doubling the size of the cell in each dimension. Consider a six-by-four array, where a raised dot could appear at each location in the array. Of the 224 total potential characters, how many are in the largest set such that no two characters are translations of each other?
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:
- 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.
- 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).
- 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).
- 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).
- 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
\]
Thanks for the solution. By the way, I think there’s a typo in your general formula for f(m,n). I believe the second factor of (2^(m-1) -1) should be (2^(n-1) – 1). With that change, I can show that my answer it equivalent to yours. Mine is
f(m,n) = 2^(mn) – (2^(m(n-1)) + (2^(n(m -1 ))) + 2^((n-1)(m-1))
although I counted no dots, so my submitted answer is 1 larger.
There is fairly easy way to get my answer that uses a sort of inclusion-exclusion argument. We start of with 2^(mn) possible characters. Then we consider what happens if the last row is all 0 (0 = no dot). There are 2^(n(m -1 )) such patterns, and each of these is a valid translation. Then we consider what happens if the last columns all 0. There are 2^(m(n -1 )) such patterns, and each of these is a valid translation. So, we subtract both of these from the 2^(mn) total. However, when we do this we have subtracted some translations twice: namely those with the last row and the last column all 0. There are 2^((m-1)(n-1)) of these, so we add these back in. Voila! We have my expression.
Thanks! Looks like my Mathematica notebook was correct; I just made a typo transcribing the formula. Should be fixed now.
I suspected there was an inclusion-exclusion argument lurking given how simple the final formula turned out to be… Good job finding it!
Just a note: when I said “is a valid translation” what I should have said was “yields a valid translation when shifted” (down in the first case, right in the second). Sorry for any confusion.
This is some tedious calculation. As Mike pointed out there is a simpler inclusion-exclusion solution and I would like to add some little amount of formulation to that comment.
For any of the translation equivalence classes, one may always select a “representation” from it. We may define our representation to be the one having some dot( not necessarily distinct) on the first column and first row.
For any layout, its dots’ column coordinate is some nonempty positive integer sequence and by WO principle it has a minimum- suppose the minimum is not one yet, we may translate the layout down by 1 unit until it meets one( cannot be moved anymore), and the same setting for left.
Furthermore, if f(a)=f(b), that means the two configurations can be mapped to the same config with translation, then they are in the same equivalence class with the representation, so they are in the same equivalence class.
Thus counting representations is the same as counting equivalence classes.
For representations, it is good to consider the dot in first column/row as hinges. And (1,1) is special because it can hinge both row and column. If (1,1) is not occupied, we need two separate hinges; otherwise we may simply let (1,1) hinge the figure. So we go into two cases:
A. the (1,1) position is occupied. Then it is automatically a representation regardless of the rest mn-1 positions, we know that there are 2^(mn-1) choices.
B. the (1,1) position is not occupied. Then some position at the top row is occupied, the same for leftmost column , and the other positions again does not matter. For the first clause there are [2^(m-1)-1] possibilities, for the second clause there are [2^(n-1)-1], and the last contribute 2^(m-1)(n-1).
We multiply the whole thing out and add it to case A to find 2^(mn-1)+2^(mn-1)-2^(mn-m)-2^(mn-n)+2^(mn-m-n+1),while the first two terms may be combined so the final result is 2^(mn)-2^(mn-m)-2^(mn-n)+2^(mn-m-n+1)
[Note: There is a slight differentation on steps, yet on a larger level this is just counting (a-p)(b-q) vs ab-ap-bq+pq]