On the Number of Crossing-Free Matchings, Cycles, and Partitions

摘要: We show that a set of $n$ points in the plane has at most $O(10.05^n)$ perfect matchings with crossing-free straight-line embedding. The expected number drawn independently and identically distributed from an arbitrary distribution is $O(9.24^n)$. Several related bounds are derived: (a) all (not necessarily perfect) $O(10.43^n)$. (b) red-blue (where colored red or blue each edge matching must connect point point) $O(7.61^n)$. (c) left-right designated as left right endpoints edges) $O(5.38^n)$. (d) across line edges cross fixed halving set) $4^n$. These employed to infer $O(86.81^n)$ spanning cycles (simple polygonizations) $O(12.24^n)$ partitions (these so convex hulls individual parts pairwise disjoint). also derive lower for some these quantities.