login
Number of concave quadrilaterals on an n X n grid (or geoboard).
7

%I #32 Feb 13 2024 07:56:00

%S 0,0,24,720,6300,34812,135552,436944,1198968,2929656,6516984,13502448,

%T 26208516,48407988,85481280,145200888,238502808,380729160,591761304,

%U 899049096,1336994100,1950873276,2798226336,3952174032,5500597632,7555866072,10253438688

%N Number of concave quadrilaterals on an n X n grid (or geoboard).

%H Michal ForiĊĦek, <a href="/A189412/b189412.txt">Table of n, a(n) for n = 1..50</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConcavePolygon.html">Concave Polygon</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Quadrilateral.html">Quadrilateral</a>.

%o (Python)

%o def gcd(x, y):

%o x, y = abs(x), abs(y)

%o while y: x, y = y, x%y

%o return x

%o def concave(N):

%o V = [ (r, c) for r in range(-N+1, N) for c in range(N) if (c>0 or r>0) ]

%o answer = 0

%o for i in range(len(V)):

%o for j in range(i):

%o r1, c1, r2, c2 = V[i]+V[j]

%o rr, cr, ta = N-max(r1, r2, 0)+min(r1, r2, 0), N-max(c1, c2), abs(r1*c2-r2*c1)

%o if rr>0 and cr>0 and ta>0:

%o answer += 3*rr*cr*(ta+2-gcd(r1, c1)-gcd(r2, c2)-gcd(r1-r2, c1-c2))/2

%o return answer

%o for N in range(1, 28):

%o print(int(concave(N)), end=', ')

%Y Cf. A175383, A189345, A189413, A189414.

%K nonn

%O 1,3

%A _Martin Renner_, Apr 21 2011

%E a(6)-a(22) from _Nathaniel Johnston_, Apr 25 2011

%E Terms a(7)-a(22) corrected by _Michal Forisek_, Sep 06 2011

%E Terms a(23)-a(50) added by _Michal Forisek_, Sep 06 2011