The Circinate Sectional Song Structure Sequence

I was looking at song structures in terms of sections. Like if you have an A section and a B section, then your song could have the form AABA. That's a great song. Very popular.

I was curious about songs that have two properties. Firstly, I want them to not have immediate repetitions of any length. So we can't have AA or BB as a substring, but also we can't have ABAB or ABCABC or ABCDABCD et cetera. Secondly, I want every section to appear at least twice. The idea is that these songs will be neither too repetitious nor too random, although I've heard enough techno music to know that humans don't really have an aesthetic concept of "too repetitious" when it comes to music they like. Let's call these ... scintillating songs? Sexy songs, synthetic songs, serrpentine, circuitous, ... circinate? Yeah, I like that. Circinate means coiled up like the frond of an immature fern. There are repetitions, bot no exact cycles.

I'm going to normalize the presentation of circinate songs so that the first section is always called A, the next new section is always called B, the next new section is C, and so forth.

There are no circinate sectional song structures in 5 or fewer total non-unique sections. But there are 3 such songs of length 6:

ABACBC
ABCACB
ABCBAC

And there are 8 such songs of length 7:

ABACABC
ABACBCA
ABCABAC
ABCACBA
ABCACBC
ABCBABC
ABCBACA
ABCBACB

And there are 42 such songs of length 8:

ABACABCA, ABACABCB, ABACBABC, ABACBCAB, ABACBCAC, ABACBDCD, ABACDBCD, ABACDBDC, ABACDCBD, ABCABACA, ABCABACB, ABCABDCD, ABCACBAB, ABCACBAC, ABCACBCA, ABCACDBD, ABCADBCD, ABCADBDC, ABCADCBD, ABCADCDB, ABCBABCA, ABCBACAB, ABCBACBC, ABCBADCD, ABCBDACD, ABCBDADC, ABCBDCAD, ABCBDCDA, ABCDABDC, ABCDACBD, ABCDACDB, ABCDADBC, ABCDADCB, ABCDBACD, ABCDBADC, ABCDBCAD, ABCDBDAC, ABCDBDCA, ABCDCABD, ABCDCADB, ABCDCBAD, ABCDCBDA

Now, the sequence {0, 3, 8, 42, ...} looks like A074435 on the OEIS, {0, 3, 8, 42, 214, 1008, 5094, ...}, the "Number of 6-ary Lyndon words of length n with trace 2 and subtrace 1 over Z_6.", so the next number might be 214? Nope! There are only 212. Here are the 212 sectional song structures of length 9 that are circinate: 

ABACABCAC, ABACABCBA, ABACABDCD, ABACADBCD, ABACADBDC, ABACADCBD, ABACADCDB, ABACBABCA, ABACBABCB, ABACBADCD, ABACBCABA, ABACBCABC, ABACBCACB, ABACBCDAD, ABACBCDBD, ABACBDACD, ABACBDADC, ABACBDBCD, ABACBDCAD, ABACBDCDA, ABACBDCDB, ABACDABCD, ABACDABDC, ABACDACBD, ABACDADBC, ABACDADCB, ABACDBADC, ABACDBCAD, ABACDBCBD, ABACDBCDA, ABACDBCDC, ABACDBDAC, ABACDBDCA, ABACDBDCB, ABACDBDCD, ABACDCABD, ABACDCADB, ABACDCBAD, ABACDCBCD, ABACDCBDA, ABACDCBDB, ABACDCBDC, ABCABACAB, ABCABACBA, ABCABACBC, ABCABADCD, ABCABDACD, ABCABDADC, ABCABDBCD, ABCABDCAD, ABCABDCBD, ABCABDCDA, ABCABDCDB, ABCACBABC, ABCACBACA, ABCACBCAB, ABCACBDAD, ABCACBDCD, ABCACDABD, ABCACDADB, ABCACDBAD, ABCACDBCD, ABCACDBDA, ABCACDBDC, ABCACDCBD, ABCADABCD, ABCADABDC, ABCADACBD, ABCADACDB, ABCADBACD, ABCADBADC, ABCADBCBD, ABCADBCDA, ABCADBCDB, ABCADBCDC, ABCADBDAC, ABCADBDCA, ABCADBDCB, ABCADBDCD, ABCADCABD, ABCADCBAD, ABCADCBCD, ABCADCBDA, ABCADCBDB, ABCADCBDC, ABCADCDAB, ABCADCDBA, ABCADCDBC, ABCADCDBD, ABCBABCAB, ABCBABCAC, ABCBABDCD, ABCBACABA, ABCBACABC, ABCBACBCA, ABCBACDAD, ABCBACDBD, ABCBADACD, ABCBADBCD, ABCBADBDC, ABCBADCAD, ABCBADCBD, ABCBADCDA, ABCBADCDB, ABCBDABCD, ABCBDABDC, ABCBDACAD, ABCBDACBD, ABCBDACDA, ABCBDACDB, ABCBDACDC, ABCBDADBC, ABCBDADCA, ABCBDADCB, ABCBDADCD, ABCBDBACD, ABCBDBADC, ABCBDBCAD, ABCBDBCDA, ABCBDCABD, ABCBDCACD, ABCBDCADA, ABCBDCADB, ABCBDCADC, ABCBDCBAD, ABCBDCDAB, ABCBDCDAC, ABCBDCDAD, ABCBDCDBA, ABCDABACD, ABCDABADC, ABCDABCAD, ABCDABCBD, ABCDABDAC, ABCDABDBC, ABCDABDCA, ABCDABDCB, ABCDABDCD, ABCDACABD, ABCDACADB, ABCDACBAD, ABCDACBCD, ABCDACBDA, ABCDACBDB, ABCDACBDC, ABCDACDBA, ABCDACDBC, ABCDACDBD, ABCDACDCB, ABCDADBAC, ABCDADBCA, ABCDADBCB, ABCDADBCD, ABCDADBDC, ABCDADCAB, ABCDADCBA, ABCDADCBC, ABCDADCBD, ABCDADCDB, ABCDBABCD, ABCDBABDC, ABCDBACAD, ABCDBACBD, ABCDBACDA, ABCDBACDB, ABCDBACDC, ABCDBADAC, ABCDBADBC, ABCDBADCA, ABCDBADCB, ABCDBADCD, ABCDBCABD, ABCDBCACD, ABCDBCADA, ABCDBCADB, ABCDBCADC, ABCDBCBAD, ABCDBCBDA, ABCDBDABC, ABCDBDACA, ABCDBDACB, ABCDBDACD, ABCDBDADC, ABCDBDCAB, ABCDBDCAC, ABCDBDCAD, ABCDBDCBA, ABCDBDCDA, ABCDCABAD, ABCDCABCD, ABCDCABDA, ABCDCABDB, ABCDCABDC, ABCDCACBD, ABCDCACDB, ABCDCADAB, ABCDCADBA, ABCDCADBC, ABCDCADBD, ABCDCADCB, ABCDCBABD, ABCDCBACD, ABCDCBADA, ABCDCBADB, ABCDCBADC, ABCDCBCAD, ABCDCBCDA, ABCDCBDAB, ABCDCBDAC, ABCDCBDAD, ABCDCBDBA, ABCDCBDCA

These happen to include four palindromes: ABACBCABA, ABCABACBA, ABCDADCBA, ABCDBDCBA.

Next up would be 1008 on the OEIS Lyndon sequence, but there are 1110 circinate songs structures of length 10. I won't post them, because that would be spammy, but I will remark that "E" sections show up, i.e. in some songs, we have 5 distinct sections, all occurring exactly twice, e.g. "ABACBDCEDE".

The sequence continues: [0, 0, 0, 0, 0, 3, 8, 42, 212, 1110, 6166, 36279, 225384, 1473866, 10118595, ...]. And now you know the start of the Circinate Sectional Song Structure Sequence. I'm gonna use 'em for algorithmic music composition. Unless I come up with a clever optimization, the next number would take more time to find than I have the patience for, but it should be about 72,700,000.

At first I was just doing random searches over string-space to find these, and gradually new ones would stop coming in, and eventually I'd feel pretty confident that I'd gotten the full count of circinate songs for a certain song length. Then I redid my program properly and wrote a recursive function to build up strings one character at a time, and that function was based on one I'd written years ago to build up polyphonic contrapuntal vocal arrangements one note at a time. I love it when I can adapt an old bit of complicated code to do a new thing. It feels like my powers are growing. Not only have I wielded recursion successfully, I have made it my plaything. Anyway, the first program checked up to 6166 in the sequence so I'm doubly confident in those values.

I wondered if a simpler version of the sequence would be in the OEIS, so I tried limiting songs to just three distinct sections {A, B, C}.Then the ternary Circinate sequence is [0, 0, 0, 0, 0, 3, 8, 13, 18, 24, 34, 47, 57, 76, 103, ...], which also isn't exactly in the OEIS, but it agrees from 13 onward with A060688, the "Number of dissimilar ternary squarefree words of length n+1.". So maybe I can read up on that and figure out a different name for the original Circinates. Maybe the full Circinate sequence takes its members from different points in dissimilar n-ary square-free sequences of increasing {n}. Like maybe the numbers of songs of length 2n and 2n+1 come from a{dissimilar n-ary square-free-word sequence}, except that that doesn't work even for n=3.