login
Given n line segments, the k-th of which is drawn from (k,0) to (x_k,1) where {x_1,x_2,...,x_n} is a permutation of {1,2,...,n}, a(n) is the maximum number of distinct points at which line segments intersect.
1

%I #39 Feb 02 2025 15:04:57

%S 0,1,2,5,8,13,17,23,30,39,47,57,67,79,90,103

%N Given n line segments, the k-th of which is drawn from (k,0) to (x_k,1) where {x_1,x_2,...,x_n} is a permutation of {1,2,...,n}, a(n) is the maximum number of distinct points at which line segments intersect.

%C There is a bijection between points with y=0 and y=1.

%C a(n) <= n(n-1)/2.

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

%H Arvin Ding, <a href="/A332774/a332774.txt">Java program</a>

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

%e This case corresponds to the permutation where {x_1,x_2,x_3} is {2,3,1}.

%e For the other 5 permutations, there are at most 2 distinct intersections. Because of this a(3)=2.

%e This table displays n, a(n), and the lexicographically earliest permutation for the first 13 positive n:

%e .

%e n a(n) lexicographically earliest permutation

%e -- ---- ---------------------------------------

%e 1 0 { 1}

%e 2 1 { 2, 1}

%e 3 2 { 2, 3, 1}

%e 4 5 { 3, 4, 2, 1}

%e 5 8 { 3, 5, 4, 2, 1}

%e 6 13 { 5, 6, 4, 3, 1, 2}

%e 7 17 { 4, 7, 6, 3, 5, 2, 1}

%e 8 23 { 6, 7, 8, 5, 3, 4, 1, 2}

%e 9 30 { 7, 9, 4, 8, 6, 3, 5, 2, 1}

%e 10 39 { 9, 10, 7, 8, 4, 3, 6, 5, 2, 1}

%e 11 47 { 9, 8, 11, 10, 7, 6, 5, 3, 4, 1, 2}

%e 12 57 { 9, 12, 11, 8, 7, 10, 4, 3, 6, 5, 2, 1}

%e 13 67 {10, 13, 12, 9, 8, 11, 5, 4, 7, 6, 3, 2, 1}

%o (Java) See Ding link

%K nonn,more,hard

%O 1,3

%A _Arvin Ding_, Feb 23 2020

%E a(13) from _Giovanni Resta_, Feb 23 2020

%E Lexicographic earliest permutation corrected by _Alexander Yan_, Apr 06 2022

%E a(14)-a(16) from _Mikhail Lavrov_, Sep 07 2022