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,3

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.

Prog

(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=', ')

Crossrefs

Cf. A175383, A189345, A189413, A189414.

Sequence in context: A367330 A184274 A093456 * A246192 A246612 A289635

Adjacent sequences: A189409 A189410 A189411 * A189413 A189414 A189415

Keyword

nonn

Author

Martin Renner, Apr 21 2011

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

Status

approved