A063549 Smallest number of crossing-free matchings on n points in the plane.

1, 1, 3, 2, 10, 5, 35, 14, 126, 42, 462, 132, 1716, 429, 6435, 1430, 24310, 4862, 92378, 16796, 352716, 58786, 1352078, 208012, 5200300, 742900, 20058300, 2674440, 77558760, 9694845, 300540195, 35357670, 1166803110, 129644790, 4537567650

Offset: 1

Author

N. J. A. Sloane, Aug 14 2001

Keywords

• nonn
• nice
• easy

Comments

a(n) = Catalan(n/2) if n is even else n*Catalan((n-1)/2) (see Garcia reference). The same as A057977. - Vladeta Jovovic, Mar 20 2010

Links

• 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.
• A. Garcia, M. Noy, and J. Tejel, Lower bounds on the number of crossing-free subgraphs of K_N, Comput. Geom., 16 (2000), pp. 211-221.

Crossrefs

Cf. A057977, A063550.

Programs

Maple

# See A057977 for an implementation based on ballot numbers. Peter Luschny, Feb 23 2019

Mathematica

a[n_?EvenQ] := CatalanNumber[n/2]; a[n_?OddQ] := n*CatalanNumber[(n-1)/2]; Table[a[n], {n, 3, 35}] (* Jean-François Alcover, Feb 03 2012, after Vladeta Jovovic *)

Formula

(n+2)*a(n) -n*a(n-1) +4*(-2*n+1)*a(n-2) +4*(n-1)*a(n-3) +16*(n-3)*a(n-4)=0. - R. J. Mathar, Jun 13 2013

Sum_{n>=1} 1/a(n) = 5/3 + 8*Pi/(9*sqrt(3)). - Amiram Eldar, Aug 20 2022

Extensions

More terms from Jean-François Alcover, Feb 03 2012

a(1) = a(2) = 1 inserted and added Garcia reference from Nathaniel Johnston, Nov 17 2014