From: "Ignacio Larrosa Canestro" Subject: RE: Checkerboard. Date: Sun, 22 Oct 2000 18:48:25 +0200 Newsgroups: sci.math 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 degrees 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 Canestro A Coruna (Espana) ilarrosa@linuxfan.com ICQ #94732648 > 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) > > > Ignacio Larrosa Canestro > > 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. > > > >