Introduction ============ In the following, m(n)=A001006(n) is the number of non intersecting chord configurations on n points, mc(n)=A175954(n) is the number of such configurations with cylic rotations considered equivalent, and md(n)=A185100(n) is the number of such configurations with rotations and reflections considered equivalent. To avoid repetition, in this document, chord configurations are always assummed to contain only non intersecting chords. In the following we will mostly be applying Burnsides lemma. This allows us to derive the number of non isomorphic configurations by counting instead the number of configurations that remain fixed under a line of symmetry or rotation. Non intersecting chord diagrams are isomorphic with Motzkin words which are sequences of U(up), D(down) and H(horizontal) which if assigned the values 1, -1, and 0 respectively total 0 in any word and no left prefix of the word has a negative total. The correspondance with chord diagrams is fairly natural with U being interpretted as begin a chord, D being interpretted as finish a chord and H as skip a node. Mostly we will use chord diagrams as it is easier to visualize the symmetries, but occasionally we use the HUD Motzkin word notation to save space. Dihedral Symmetry ================= We deal with dihedral symmetry first since it is slightly simpler. Case n odd: There are n lines of symmetry, each passing through one vertex on one side and between two vertices on the opposite side. Considering any one of these, there may be chords that span the line of symmetry and between these, chord configurations that do not. The vertex that the line of symmetry runs through cannot be associated with a chord. Illustration of a symmetrical configuration on 17 vertices: (vertical line of symmetry) .___. ._______. . . ._ _. . \ / . ._ / \_. .___________. . . . In the above there are 3 chords that span the line of symmetry and these divide the configuration into 4 segments. (The segments from top to bottom have 0, 0, 4 and 1 available vertices). The bottom unpaired vertex is ignored. To count the number of symmetrical chord configurations we essentially need to count collections of chord configurations on (n-1)/2 nodes where each separator between the chord configurations also occupies one node. This is best dealt with in the language of combinatorial objects. (see "Analytic Cominatorics" by P. Flajolet and R. Sedgewick, chapter I). In particular we want M x SEQ( Z x M ) where M is the combinatorial class of Motzkin words. In GF terms this gives: M(x) ------------ 1 - x * M(x) The first few terms are (n>=0): 1, 2, 5, 13, 35.... It turns out this sequence is already in OEIS and is A005773(n+1). The GF of A005773 is then 1/(1 - x * M(x)) and counts sequences of Motzkin words where each word is prefixed with a marker which also contributes to the length of the word. Example: ( where / is the marker, U - up, D - down, H - horizontal ) A005773(3) = 5, counts ///, //H, /H/, /UD, /HH. A005773(4) = 13, counts ////, ///H, //H/, /H//, //HH, //UD, /H/H, /HH/, /UD/, /HHH, /HUD, /UHD, /UDH. Applying Burnside's lemma: mc(2n+1) + A007573(n+1) md(2n+1) = ----------------------- 2 Case n even: There are n/2 lines of symmetry passing between vertices on opposite sides. As when n is odd, there may be chords that span the line of symmetry and between these there are chord configurations that do not. There are also n/2 lines of symmetry passing through vertices on opposite sides. Here there is an option to either connect the two opposing vertices or not. If the two vertices are connected there can be no chords that cross the line of symmetry in which case each side is just a single chord configuration on n/2 - 1 points. Otherwise crossing are allowed. The three cases give: A007573( n/2 + 1 ) A007573( n/2 ) m( n/2 - 1 ) Illustrations of the three cases (8 points, vertical line of symmetry) . . . . .__| |__. . . . | . . . .__| |__. .__| | |__. .___. ._____. . | . . . Putting it all together with Burnside's lemma: mc(2n) A007573( n/2 + 1 ) + A007573( n/2 ) + m( n/2 - 1 ) md(2n) = ------- + ------------------------------------------------------- 2 4 The reason for the division by 4 instead of 2 is that there are only n/2 symmetries of each kind. (Technically, there should be a multiplier of n for mc(2n), a multiplier of n/2 for everything else and then the whole lot is divided by 2n which is the total number of symmetries including both rotations and reflections.) ------------------------ Cyclic Symmetry =============== It is necessary to count the number of chord configurations that remain fixed under a given rotation. In the following we will take d as the number of points that the chord configuration is rotated by. It is only necessary to consider rotations of d points where d is a factor of n. (since if a chord configuration is fixed by a rotation of say 7/12 then it is also fixed by a rotation of 1/12) The principal difficulty is that it is insufficient to simply count chord configurations over d points, otherwise we exclude those configurations that have chords crossing into the chosen segment from the previous one. Similarly we cannot simply multiply by d without getting duplicates. In order to count everything and not overcount it is necessary to count only those configurations that begin at the start of a chord and multiply by the distance up to the start of the second chord (or d if there is only one). We also need to add in an extra item for the case that there are no chords at all. (the empty segment). To count configurations that start on a chord just use m(n) - m(n-1), where m(-1) is defined to be 0. (this works because every Motzkin word of length n that starts with an H can be represented by an H followed by a Motzkin word of length n-1 and vice versa). This leads to the following formula: ___ ___ \ \ 1 + > ( m(d-k)-m(d-k-1) ) * > m(j-2) /___ /___ k=2..d j=2..k In the above, k is the number of vertices occupied by the first chord including all of its contents and any empty vertices up to the start of the second chord, j is the number of vertices occupied by the first chord, m(j-2) is the number of ways of filling the first chord with a valid chord configuration and m(d-k)-m(d-k-1) is the number of ways of filling the remaining d-k vertices with other chord configurations. This somewhat complex formula leads to the sequence (d>=1) 1, 3, 7, 19, 51, 141, 393, 1107, 3139, 8953.... It turns out this sequence is already in OEIS and is A002426. (Central trinomial coefficients) There are a couple of special cases we need to consider. Firstly, the above is only valid for 1 HHHHHH (no chord) UDH => UDHUDH, HUDHUD, UHUDHD (k=3) UHD => UHDUHD, UUHDDH, HUUHDD (k=3) The 6 that are covered by the d = n/2 rule HH => UHHDHH, HUHHDH, HHUHHD UD => UUDDUD, UUUDDD, UDUUDD If we define { 0 when n is odd r(n) = { { (n/2) * m(n/2-1) when n is even Then applying Burnside's lemma: ___ 1 \ mc(n) = --- ( m(n) + r(n) + > phi(n/d) * A002426(d) ) n /___ d|n, d 2 * 1 = 2 d: 2 => 1 * 7 = 7 d: 3 => 2 * 6 = 12 m(6) => 1 * 51 = 51 r(6) => 6 + ---- 72 Therefore, mc(6) = 72 / 6 = 12