A063550 Largest number of crossing-free matchings on a set S of n points in the plane, that is, a set of floor(n/2) pairwise non-intersecting segments with endpoints in S having no endpoint in common.

1, 1, 3, 3, 14, 12, 79, 56, 497, 311

Offset

1,3

Links

Table of n, a(n) for n=1..10.

O. Aichholzer and H. Krasser, The point set order type data base: a collection of applications and results, pp. 17-20 in Abstracts 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 13-15, 2001.

M. Sharir and E. Welzl. On the Number of Crossing-Free Matchings, (Cycles, and Partitions)

Example

The Sharir link contains an image (Figure 1) of a placement of 6 points in the plane such that 12 of their perfect matchings are crossing-free, demonstrating that a(6) >= 12. - Nathaniel Johnston, Nov 17 2014

Crossrefs

Cf. A063549.

Sequence in context: A287501 A287537 A186373 * A367672 A298960 A356117

Adjacent sequences: A063547 A063548 A063549 * A063551 A063552 A063553

Keyword

nonn,nice,hard,more

Author

N. J. A. Sloane, Aug 14 2001

Extensions

a(1) = a(2) = 1 inserted by Nathaniel Johnston, Nov 17 2014

Name clarified by Manfred Scheucher, Mar 12 2018

Status

approved