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

 

Logo
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 (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.

LINKS

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

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 first permutation for the first 13 positive n:

.

   n  a(n)  lexicographically first 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,  3,  4,  2,  1}

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

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

   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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 05:19 EST 2022. Contains 350481 sequences. (Running on oeis4.)