The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 1
 0, 1, 2, 5, 8, 13, 17, 23, 30, 39, 47, 57, 67, 79, 90, 103 (list; graph; refs; listen; history; text; internal format)
 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified February 2 09:15 EST 2023. Contains 360004 sequences. (Running on oeis4.)