cp's OEIS Frontend

A379299 a(n) is the maximum number k such that every permutation of the integers mod n admits at least k collinear triples.

%I A379299 #30 Jan 09 2025 13:20:03
%S A379299 0,0,1,0,2,0,3,0,5,2,5,0,6,9,6,4,8
%N A379299 a(n) is the maximum number k such that every permutation of the integers mod n admits at least k collinear triples.
%C A379299 Three points (x_i,y_i), i=1,2,3, are collinear if x_1*(y_2-y_3) + x_2*(y_3-y_1) + x_3*(y_1-y_2) == 0 (mod n).
%C A379299 Exhaustive search in SageMath obtained the reported values from Cooper and Solymosi 2004, where the authors show that (n-1)/4 <= a(n) <= (n-1)/2 for every odd prime n. In Li 2008, the author shows that a(n) = (n-1)/2 for every odd prime n.
%H A379299 Joshua Cooper and Jack Hyatt, <a href="https://arxiv.org/abs/2501.02331">Permutations minimizing the number of collinear triples</a>, arXiv:2501.02331 [math.CO], 2025. See p. 7.
%H A379299 Joshua N. Cooper and József Solymosi, <a href="https://doi.org/10.1007/s00026-005-0248-4">Collinear points in permutations</a>, Ann. Comb. 9 (2005), no. 2, 169-175; <a href="https://arxiv.org/abs/math/0408396">preprint</a>, arXiv:math/0408396 [math.CO], 2004.
%H A379299 Liangpan Li, <a href="https://projecteuclid.org/journals/innovations-in-incidence-geometry/volume-8/issue-none/Collinear-triples-in-permutations/10.2140/iig.2008.8.171.full">Collinear triples in permutations</a>, Innov. Incidence Geom. 8 (2008), 171--173; <a href="https://arxiv.org/abs/0805.0410">arXiv preprint</a>, arXiv:0805.0410 [math.CO], 2008.
%F A379299 a(n) = (n-1)/2 for odd primes n.
%e A379299 a(5)=2 because the permutation (in one-line notation) 0,1,3,2,4 admits two collinear triples mod 5: {(0,0),(1,1),(4,4)} is on the line y=x and {(0,0),(3,2),(2,3)} is on the line y=4*x; and all other permutations admit at least 2 collinear triples.
%Y A379299 Cf. A272651, A000769, A000755, A000938.
%K A379299 nonn,more
%O A379299 1,5
%A A379299 _Joshua Cooper_, Dec 20 2024