A135452 Number of different multisets of differences between ends of n non-intersecting chords joining 2n labeled points around a circle.

1, 1, 2, 3, 6, 10, 20, 33, 71, 117, 242, 421, 877, 1468

Offset: 1

Author

Arvind Ayyer, Dec 14 2007, definition corrected Jan 04 2007, Jan 07 2007

Keywords

• more
• nonn

Comments

Represent a set of chords as a collection of pairs of integers. For example, if n=3, one possible connectivity is {{1,4},{2,3},{5,6}}.

Define the D-set of a connectivity to be the multiset of differences between connected pairs. In the above example the D-set is {1,1,3}. Since the numbers are on a circle, we can take two possible differences. We take the smaller of the two. Hence the maximal difference can be at most n or n-1 depending on whether n is odd or even. Is another example: the D-set of {{1,6},{2,3},{4,5}} is {1,1,1}.

Then the sequence gives the number of distinct D-sets of all possible connectivities.

While it is true that if two connectivities have different D-sets they are inequivalent, the converse is not true. consider n=6: Both {{4, 5}, {6, 11}, {2, 3}, {8, 9}, {7, 10}, {1, 12}} and {{4, 5}, {1, 6}, {2, 3}, {8, 9}, {7, 10}, {11, 12}} have the same D-set, namely {1,1,1,1,3,5} but they are inequivalent.

Crossrefs

Cf. A001008, A054357.