OFFSET
1,3
COMMENTS
There is a bijection between points with y=0 and y=1.
a(n) <= n(n-1)/2.
a(n) >= floor(n^2/4), by considering the n-permutation sending i to (floor(n/2)+i) mod n. - Boon Suan Ho, Sep 07 2022
LINKS
Arvin Ding, Java program
EXAMPLE
For n=3, draw a line segment from (0,0) to (1,1), from (1,0) to (2,1), and from (2,0) to (0,1). This would correspond to 2 distinct intersections; namely, these are at (5/3,2/3) and (7/3,1/3).
This case corresponds to the permutation where {x_1,x_2,x_3} is {2,3,1}.
For the other 5 permutations, there are at most 2 distinct intersections. Because of this a(3)=2.
This table displays n, a(n), and the lexicographically earliest permutation for the first 13 positive n:
.
n a(n) lexicographically earliest permutation
-- ---- ---------------------------------------
1 0 { 1}
2 1 { 2, 1}
3 2 { 2, 3, 1}
4 5 { 3, 4, 2, 1}
5 8 { 3, 5, 4, 2, 1}
6 13 { 5, 6, 4, 3, 1, 2}
7 17 { 4, 7, 6, 3, 5, 2, 1}
8 23 { 6, 7, 8, 5, 3, 4, 1, 2}
9 30 { 7, 9, 4, 8, 6, 3, 5, 2, 1}
10 39 { 9, 10, 7, 8, 4, 3, 6, 5, 2, 1}
11 47 { 9, 8, 11, 10, 7, 6, 5, 3, 4, 1, 2}
12 57 { 9, 12, 11, 8, 7, 10, 4, 3, 6, 5, 2, 1}
13 67 {10, 13, 12, 9, 8, 11, 5, 4, 7, 6, 3, 2, 1}
PROG
(Java) See Ding link
CROSSREFS
KEYWORD
nonn,more,hard
AUTHOR
Arvin Ding, Feb 23 2020
EXTENSIONS
a(13) from Giovanni Resta, Feb 23 2020
Lexicographic earliest permutation corrected by Alexander Yan, Apr 06 2022
a(14)-a(16) from Misha Lavrov, Sep 07 2022
STATUS
approved