In a previous post I gave rules for when two orthogons will be considered the same:
- Two orthogons are the same if one is the mirror image of the other.
- Two orthogons are the same if one can be turned into the other just by changing the length of some of the edges.
I just realized that I forgot a rule!
- Two orthogons are the same if one is a rotation of the other.
You might not have even noticed this omission, because it would be strange not to have this rule: usually we think of two polygons as being the same if one is just a rotation of the other. And if rotating an orthogon were to result in a distinct orthogon, then there would be way too many distinct orthogons (uncountably infinitely many, in fact).
So, for example, these four orthogons are all the same:
Of course this notion of sameness should also be reflexive (any orthogon is the same as itself) and transitive (if A is the same as B and B is the same as C, then A is the same as C), so that it is an equivalence relation.
Now, in my previous post I finished the proof showing that orthogons are in 1-1 correspondence with sequences of
V’s, containing exactly 4 more
V’s, when the sequences are also considered the same up to rotation and reversal. Sequences considered the same up to rotation and reversal are sometimes called bracelets. They are very similar to the necklaces we saw in a recent proof of Fermat’s Little Theorem; the only difference is that two sequences which are the reverse of each other are considered distinct as necklaces, but the same as bracelets. Let’s call bracelets of
V’s, with exactly four more
V’s, orthobraces. (Not to be confused with orthodontics, which are also called braces, but are definitely not the same when rotated.)
So we have reduced the problem of listing all the orthogons with a given number of vertices to two subproblems:
- List all orthobraces of a given length.
- Turn each orthobrace into a drawing of an orthogon.
I want to start by talking about the first subproblem. To get a sense for why listing bracelets is an interesting problem, here are some questions you can ponder:
Start by considering normal sequences (so, e.g.,
XXXVXXare all different sequences). How many sequences are there with four
X’s and no
Vs? How many with five
X’s and one
X’s and two
V’s? In general, how many sequences are there with
Try 1listing small orthobraces. How many do you get for each number of
V’s? You can try to come up with a formula if you really want, but this actually turns out to be quite difficult; I suggest just trying to systematically list orthobraces and see how many you get. For example, there is only one orthobrace when , namely
XXXX. There is also only one,
XXXXXV, for . This is the only one since any sequence with five
X’s and one
Vis just a rotation of this one. (The particular sequence we pick to represent the orthobrace doesn’t matter.)
Compare how many bracelets there are of each size with how many sequences there are. What seems to be the general trend?
An obvious algorithm for listing all bracelets of a given size is to list all the sequences (this is very easy), and throw away any sequences which are equivalent to one we’ve already generated when considered as bracelets (i.e. up to rotation and reversal). Based on your observations above, how feasible is this method?