A358251 a(n) is the minimum number of peeling sequences for a set of n points in the plane, no three of which are collinear.

1, 2, 6, 18, 60, 180

Offset

1,2

Comments

Let P be a set of n points in the plane, no three of which are collinear, labeled by 1,2,...,n. A peeling sequence for P is any permutation of [n] that can be obtained by writing the labels of the points removed one by one. a(n) is the minimum number of such permutations that can be obtained, over all point sets of size n.

Links

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

Adrian Dumitrescu, Peeling sequences, Mathematics, 2022, 10, 4287; arXiv preprint, arXiv:2211.05968 [math.CO], 2022.

Example

Let h denote the size of the convex hull of P.
The case n=3 is clear: there are 3!=6 permutations and each of them is a valid peeling sequence, so a(3)=6.
For n=4: If the points are in convex position, there are 4!=24 permutations. If the points are not in convex position, let 4 be the interior point. Then any permutation that starts with 4 is invalid, however, all remaining 4!-3!=18 permutations are valid. Thus a(4)=18.
For n=5: If h >= 4, there are at least 4*a(4) = 72 permutations. The case h=3 yields the smallest number, 24+18+18=60, of permutations; indeed, removing one of the extreme points yields a convex quadrilateral, while the other two removals can result in a triangle with a point inside. Thus a(5)=60.

Crossrefs

Sequence in context: A121320 A148460 A148461 * A002527 A005566 A005631

Adjacent sequences: A358248 A358249 A358250 * A358252 A358253 A358254

Keyword

nonn,more

Author

Adrian Dumitrescu, Nov 04 2022

Status

approved