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

0, 0, 24, 720, 6300, 34812, 135552, 436944, 1198968, 2929656, 6516984, 13502448, 26208516, 48407988, 85481280, 145200888, 238502808, 380729160, 591761304, 899049096, 1336994100, 1950873276, 2798226336, 3952174032, 5500597632, 7555866072, 10253438688

Offset: 1

Author

Martin Renner, Apr 21 2011

Keywords

• nonn

Links

• Michal Forišek, Table of n, a(n) for n = 1..50
• Eric Weisstein's World of Mathematics, Concave Polygon.
• Eric Weisstein's World of Mathematics, Quadrilateral.

Crossrefs

Cf. A175383, A189345, A189413, A189414.

Programs

Python

def gcd(x, y):
  x, y = abs(x), abs(y)
  while y: x, y = y, x%y
  return x
def concave(N):
  V = [ (r, c) for r in range(-N+1, N) for c in range(N) if (c>0 or r>0) ]
  answer = 0
  for i in range(len(V)):
    for j in range(i):
      r1, c1, r2, c2 = V[i]+V[j]
      rr, cr, ta = N-max(r1, r2, 0)+min(r1, r2, 0), N-max(c1, c2), abs(r1*c2-r2*c1)
      if rr>0 and cr>0 and ta>0:
        answer += 3*rr*cr*(ta+2-gcd(r1, c1)-gcd(r2, c2)-gcd(r1-r2, c1-c2))/2
  return answer
for N in range(1, 28):
    print(int(concave(N)), end=', ')

Extensions

a(6)-a(22) from Nathaniel Johnston, Apr 25 2011

Terms a(7)-a(22) corrected by Michal Forisek, Sep 06 2011

Terms a(23)-a(50) added by Michal Forisek, Sep 06 2011