I took a bit of a break to finish writing a paper for submission to the International Conference on Functional Programming—which I should write about here! All in good time. (I tend to accumulate things to write about faster than I can write them… a blessing and a curse!) For now, back to your irregularly scheduled orthogons.

Recall from my previous post that a bracelet is a string considered unique only up to rotation and reflection. We also gave the name orthobrace to a bracelet consisting of X’s and V’s, with exactly four more X’s than V’s, and we saw that they are in one-to-one correspondence with orthogons. If we can find a way to list all orthobraces of a certain size (and if we can find a reasonable way to turn them into drawings!) we can make a list of all the orthogons of a certain size.

In my previous post I left you with a few questions.

1. How many sequences are there with X’s and V’s?

   (Here I really do mean just sequence, not bracelet, so e.g. XXXV and XXVX are the same bracelet but different sequences.)

   If we have four X’s and no V’s then there is of course only one. With five X’s and one V, we have a choice of five different places where we could put the V: before the first X, after the first X, after the second X, … and so on. With six X’s and two V’s, we get to choose any two out of six possible places to put the V’s.

   In general, the number of sequences with X’s and V’s is the number of ways to choose places out of the total to put the V’s. We can make a table:

   

   As you can see, the number of sequences grows quite quickly; in fact (though I won’t prove this) it grows exponentially relative to .

2. What about orthobraces, where we consider sequences equivalent up to rotation and reversal, and just want one representative from each equivalence class? If you try listing them and counting how many there are of each size, you get a sequence of numbers like

   

   which does not grow quite so quickly (though it turns out it still grows exponentially).

3. Gesh made a nice argument in a comment on my previous post which gives us an idea of how quickly we should expect this to grow relative to how many sequences there are. In particular, we expect that every sequence of length will have roughly different sequences which it is equivalent to— rotations plus all their reversals. This is only a rough estimate, since if the sequence has any sort of symmetry, some of the rotations and reflections may be identical. But symmetry is special—an average random string will not be symmetric, and hence most of the time all the rotations and reflections will be distinct. So we would expect there to be about times as many sequences as bracelets—a little less to account for some of the rotations and reflections not always being distinct. And if we take ratios, here’s what we get:

   

   On the left hand side of the table is the ratio of the number of sequences of size to the number of orthobraces; on the right hand side is . As you can see, the ratios do indeed seem to be approaching from below.

4. So, what about generating all orthobraces of a given size by listing all sequences and throwing away any sequences which are equivalent to one we’ve already generated? This can be done, but as we can see from the above analysis, we would spend most of our time throwing out sequences which are equivalent to ones we’ve already generated.

So generating orthobraces this way isn’t actually such a great idea, although it does have the benefit of being quite simple conceptually. In another post I’ll show some simple code to carry out this “naive” algorithm, and then talk about an alternative!