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

%I #22 Dec 21 2022 22:16:07

%S 1,2,6,18,60,180

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

%C 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.

%H Adrian Dumitrescu, <a href="https://doi.org/10.3390/math10224287">Peeling sequences</a>, Mathematics, 2022, 10, 4287; <a href="https://arxiv.org/abs/2211.05968">arXiv preprint</a>, arXiv:2211.05968 [math.CO], 2022.

%e Let h denote the size of the convex hull of P.

%e The case n=3 is clear: there are 3!=6 permutations and each of them is a valid peeling sequence, so a(3)=6.

%e 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.

%e 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.

%K nonn,more

%O 1,2

%A _Adrian Dumitrescu_, Nov 04 2022