From: "Ignacio Larrosa Cañestro" <ilarrosa@linuxfan.com>
Subject: RE: Checkerboard.
Date: Sun, 22 Oct 2000 18:48:25 +0200
Newsgroups: sci.math
Summary: [missing]

For a 4*4 grid, the calculations are easy:

Comb(16, 9)=560 triads of points

There are 10 straight lines with four points on then: 4 verticals, 4
horizontals an 2 main diagonals. There ara 4 triads (i.e., Comb(4, 3)) of
points in each one of them --> 40

Aditionally, the four diagonals (2 of then indicated below) close the main
diagonals also contain 3 points.

Then, there are 44 triads of points collinears, and the number of triangles
is 560 - 44=516

*  *  *  *
      /
*  *  *  *
  /      /
*  *  *  *
      /
*  *  *  *

In general, let B(m,n) the number of triangles in a grid of m*n points.

Let C(j,k) the number of triangles in a grid of j*k points that cannot be
put on a grid of j'*k' points if j'<j or k'<k.

Then,

B(m,n)=Sum(Sum((m-j+1)(n-k+1)C(j,k), j, 2, m), k, 2, n)

because in a grid of m*n points we can put a grid of j*k points of
(m-j+1)(n-k+1) forms; without gires, a j*k grid gired 90º is a k*j grid.

Well, C(j,k) have three components:

i) Triangles with two vertices in the extremes of one diagonal. The third
vertix can be anyone not in the diagonal. There ara then 2(j*k - gcd(j-1,
k-1) -1), because there are two diagonals and there ara gcd(k-1,j-1) + 1
points in each one of then.

ii) Triangles with two vertices in extremos of one side. The third vertix
can be anyone inside (no extremes) the opposite side. There are 2((j-2) +
(k-2)).

iii) Triangles with one vertix in a vertix P of the grid, and the other two
vertices inside the sides non concurrent with P. There are 4(j-2)(k-2).

We put all together and with some algebraic work,  we get

B(m,n)=(m^3-m)(n^3-n)/6 - 2·Sum(Sum((m-j+1)(n-k+1)·gcd(k-1,j-1),
j,2,m),k,2,n)

And i we do A(n)=B(n,n),

A(n)=(n^3-n)^2/6 - 2·Sum(Sum((n-j+1)(n-k+1)·gcd(k-1,j-1), j,2,n),k,2,n)

For n=1 to 40, A(n) is

[0, 4, 76, 516, 2148, 6768, 17600, 40120, 82608, 157252, 280988, 477012,
775172, 1214768, 1844512, 2725000, 3930384, 5550844, 7692300, 10482124,
14066996, 18619128, 24337056, 31449200, 40212160, 50921316, 63907468,
79542108, 98239396, 120464616, 146726096, 177595280, 213693680, 255707716,
304389180, 360557540, 425103060, 499004560, 583313520, 679169592]


Un saludo,

Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosa@linuxfan.com
ICQ #94732648
Ignacio Larrosa Cañestro <ilarrosa@linuxfan.com> escribió en el mensaje de
noticias 8sud1q$68o$1@diana.bcn.ttd.net...
> For m=n see
>
> http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An
> um=045996
>
> There n is the number of points, not the squares. So, for n=4 (3 for you)
> the number is 516.
>
> a(n) = ((n - 1)^2*n^2*(n + 1)^2)/6 - 2*Sum(Sum((n - k + 1)*(n - l + 1)*gcd(k
>               - 1, l - 1), k, 2, n), l, 2, n)
>
>
>
> --
> Un saludo,
>
> Ignacio Larrosa Cañestro
> A Coruña (España)
> ilarrosa@linuxfan.com
> ICQ #94732648
> josevidosa <josevidosa@wanadoo.es> escribió en el mensaje de noticias
> NdxI5.27$6q6.1862@m2newsread.uni2.es...
> >     How many triangles(of any size)are there in an m by n checkerboard
> whith
> > (m+1)*(n+1) vertices?For m = n = 3,the numbers of vertices is
> (3+1)*(3+1)=16
> > and I have two diferents solutions a)520 triangles b)516 triangles.What´s
> > the right and general solution?.Why?
> >
> >
> > S.Lomas.
> >
> >
>
>