A135538 Number of triples in all permutations of order n that are collinear modulo n.

0, 0, 0, 6, 32, 400, 2304, 35280, 322560, 3888000, 48384000, 731808000, 9858723840, 161902540800, 2628760780800, 43181994240000, 876764528640000, 16124496740352000, 358721232629760000, 6933770723303424000, 168738115888742400000, 3644128675321085952000, 94201965756599500800000

Offset: 0

Author

R. J. Mathar, Feb 22 2008, corrected Oct 24 2008

Keywords

• nonn

Examples

			For example, in a permutation p=[5,2,4,3,1], a triple of points { (2,p(2)=2), (4,p(4)=3), (5,p(5)=1) } is collinear, since they are located on the line: x + 3*y == 3 (mod 5).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..400
• L. Li, Collinear triples in permutations, arXiv:0802.0572 [math.CO], 2008.

Programs

Mathematica

f[n_] := n*Sum[ Sum[ (n - i - j)*( n*GCD[i, j, n - i - j] - GCD[i, n] - GCD[j, n] - GCD[i + j, n] + 2 ) , {j, 1, n - i}] , {i, 1, n}]; Join[{0, 0, 0}, Table[(n - 3)!*f[n], {n, 3, 25}]] (* G. C. Greubel, Oct 18 2016 *)

PARI

a(n) = if(n<3, 0, (n-3)! * n * sum(i=1,n, sum(j=1,n-i-1, (n-i-j) * (n*gcd([i,j,n-i-j]) - gcd(i,n) - gcd(j,n) - gcd(i+j,n) + 2) )))

Formula

For n>=3, a(n) = (n-3)! * A146557(n).

Extensions

Edited and extended by Max Alekseyev, Oct 31 2008