One of these days soon I will get back to writing about primality tests, but for now I am having fun getting sidetracked on orthogons!
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 11 correspondence with sequences of X
’s and V
’s, containing exactly 4 more X
’s than 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 X
’s and V
’s, with exactly four more X
’s than 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.,
XXXXXV
,VXXXXX
, andXXXVXX
are all different sequences). How many sequences are there with fourX
’s and noV
s? How many with fiveX
’s and oneV
? SixX
’s and twoV
’s? In general, how many sequences are there withX
’s andV
’s? 
Try listing 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 , namelyXXXX
. There is also only one,XXXXXV
, for . This is the only one since any sequence with fiveX
’s and oneV
is 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?
Haven’t thought much about the latest questions yet.
Question 1 is clearly the usual starsandbars question (with solution ). As for question 3, a quick backoftheenvelope estimate – assuming that a generic string differs from all its shifts and reflections (which is true for something like strings) – gives that the amount of strings corresponding to a given orthobrace is linear in the length of the orthobrace, thus making the amount of orthobraces grow about as . This, in turn, suggests that the problem you’re alluding to in question 4 is that we we need to canonicize an exponentiallygrowing set by a linearlygrowing relation, which would take exponential time. Hence the need for a canonicalbyconstruction generating function.
One thing that does stand out to me is that the identifications you made (orthobraces are considered identical up to cyclic permutations and reversals (which corresponds to mirroring the orthogon)) correspond to quotienting the set of strings over by the action of the infinite dihedral group.
In more detail, let the set of all strings of length over , and .
Then acts on by sending to a onesymbol shift (in an arbitrary direction) and to reversal.
To extend these actions to an action on , we first view as , which clearly extends to an action by for all by the natural map . This procedure extends to , giving an action of on for all .
Taking the union of these actions, we obtain an action on .
Quotienting by this action, we obtain the braces,
with the orthobraces being just those braces arising from under the action.
This gives a way to improve the estimate of the growth rate from above, by use of Burnside’s theorem. Clearly it suffices to estimate the growth rate at prime lengths (used to keep the strings fixed by manageable$).
Noting that fixes concatenations of palindromes of lengths – of which there are and that fixes strings that are repetitions of strings of length for , we have that the amount of braces – which equals the average amount of points fixed by an action of – is – the same estimate, but with better constants.
P.S. Sorry for the more rambly nature of this comment, I didn’t take the time to properly digest my thoughts here.
Great analysis! I think you are spot on.
Pingback: Listing orthobraces  The Math Less Traveled
Pingback: Efficiently listing orthobraces  The Math Less Traveled