A213222 Minimum number of distinct slopes formed by n noncollinear points in the plane.

3, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 14, 14, 16, 16, 18, 18, 20, 20, 22, 22, 24, 24, 26, 26, 28, 28, 30, 30, 32, 32, 34, 34, 36, 36, 38, 38, 40, 40, 42, 42, 44, 44, 46, 46, 48, 48, 50, 50, 52, 52, 54, 54, 56, 56, 58, 58, 60, 60, 62, 62, 64, 64, 66, 66, 68, 68, 70, 70, 72, 72, 74, 74, 76, 76, 78, 78, 80, 80, 82, 82, 84

Offset: 3

Author

Charles R Greathouse IV, Mar 02 2013

Keywords

• nonn
• easy

Comments

Scott formulated the problem (on the basis of a similar problem of Erdős), gave bounds, and conjectured the formula which Unger later proved.

Also the edge chromatic number of the n-polygon diagonal intersection graph. - Eric W. Weisstein, Mar 23 2018

References

• Martin Aigner and Gunter M. Ziegler, Proofs from THE BOOK, Second Edition, Springer-Verlag, Berlin, 2000. Chapter 10.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 3..1000
• J. E. Goodman and R. Pollack, On the combinatorial classification of nondegenerate configurations in the plane, J. Combin. Theory Ser. A, 29 (1980), pp. 220-235.
• Giovanni Resta, Illustration of terms a(3)-a(7)
• P. R. Scott, On the sets of directions determined by n points, The American Mathematical Monthly 77:5 (1970), pp. 502-505.
• Peter Ungar, 2N noncollinear points determine at least 2N directions, Journal of Combinatorial Theory, Series A, 33:3 (1982), pp. 343-347.
• Eric Weisstein's World of Mathematics, Edge Chromatic Number
• Eric Weisstein's World of Mathematics, Polygon Diagonal Intersection Graph
• Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Crossrefs

Cf. A000769, A000755, A219760.

Cf. A000217 (maximum number of slopes, with offset 1).

Programs

Magma

[2*Floor(n/2): n in [3..100]]; // Vincenzo Librandi, Mar 29 2014

Maple

A213222:=n->`if`(n = 3, 3, 2*floor(n/2)); seq(A213222(n), n=3..100); # Wesley Ivan Hurt, Mar 28 2014

Mathematica

CoefficientList[Series[(3 + x - 3 x^2 + x^3)/((1 + x) (1 - x)^2), {x, 0, 100}], x] (* Vincenzo Librandi, Mar 29 2014 *)
LinearRecurrence[{1,1,-1},{3,4,4,6},100] (* Harvey P. Dale, Dec 29 2024 *)

PARI

a(n)=if(n>3,n\2*2,3)

Formula

a(n) = 2*floor(n/2) for n > 3.

G.f.: x^3*(3+x-3*x^2+x^3)/((1+x)*(1-x)^2). [Bruno Berselli, Mar 04 2013]