A332774 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.

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

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

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

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

Sequence in context: A178752 A225255 A076145 * A256829 A342431 A049617

Adjacent sequences: A332771 A332772 A332773 * A332775 A332776 A332777

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