[seqfan] Re: A006528 and quadrilateres in a square
jean-luc.manguin at unicaen.fr
Mon Sep 7 09:27:47 CEST 2020
Thank you very much, David !
----- Mail original -----
De: "David Seal" <david.j.seal at gwynmop.com>
À: "seqfan" <seqfan at list.seqfan.eu>
Envoyé: Vendredi 4 Septembre 2020 18:14:22
Objet: [seqfan] Re: A006528 and quadrilateres in a square
Your sequence is a bit under-defined when it says "put N points on each edge of a square ; the points are equally spaced.", because there are many ways of placing N equally-spaced points on an edge of a square. I'll assume you mean that the edge is divided into N segments of equal length, and then the points are placed at the midpoints of those segments. Or in other words, if the square has side 2N, the points are placed at (x,0), (x,2N), (0,y) and (2N,y) for odd values of x and y lying between 0 and 2N.
To give the representation of a quadrilateral rotational symmetry, I'll 'reverse' two of the edges and assume that the vertices are at (x1,0), (2N,y1), (2N-x2,2N) and (0,2N-y2). And I'll denote that quadrilateral by [x1,y1,x2,y2], and its rotations are [y1,x2,y2,x1], [x2,y2,x1,y2] and [y2,x1,y2,x2], i.e. the rotations of the representations.
The area of those quadrilaterals is the area of the square minus the sum of the areas of the excluded triangles at its four corners. That area is half the area of the square if and only if the area of the square minus twice the sum of the areas of those excluded triangles is 0, i.e. if and only if:
(2N)^2 - x1*(2N-y2) - y1*(2N-x1) - x2*(2N-y1) - y2*(2N-x2)
is zero. But that's equal to:
4N^2 - 2N*(x1+y1+x2+y2) + (x1*y2+y1*x1+x2*y1+y2*x2)
= (2N-x1-x2) * (2N-y1-y2)
which is zero if and only if x1+x2 = 2N or y1+y2 = 2N.
Expanding on your explanation of the (N^4 + N^2 + 2N)/4 formula for the number of quadrilaterals, we can classify the N^4 quadrilaterals (counted without factoring out rotations) into three classes:
Squares: N quadrilaterals that are equal to all four of their rotations, namely the quadrilaterals [x,x,x,x].
Parallelograms: N^2 - N quadrilaterals that are equal to their rotations by 180 degrees, but not to all four of their rotations, namely the quadrilaterals [x,y,x,y] with x not equal to y. (Note that only some of these are rectangles, but that's just an incorrect choice of description, not anything wrong with your reasoning.)
Others: N^4 - N^2 quadrilaterals that are not in either of the other classes, namely the quadrilaterals [x1,y1,x2,y2] with x1 not equal to x2 or y1 not equal to y2.
As a check, that means the number of quadrilaterals counted factoring out rotations is N + (N^2 - N)/2 + (N^4 - N^2)/4 = (4N + 2N^2 - 2N + N^4 - N^2)/4 = (N^4 + N^2 + 2N)/4, in agreement with your result.
Now count the number of quadrilaterals whose area is half the area of the square similarly. Without factoring out rotations, there are N^3 quadrilaterals with x1+x2 = 2N, namely the ones of the form [x1,y1,2N-x1,y2], and similarly there are N^3 quadrilaterals with y1+y2 = 2N. However, adding those numbers together double-counts the quadrilaterals with both x1+x2 = 2N and y1+y2 = 2N, of which there are N^2, namely the ones of the form (x1,y1,2N-x1,2N-y1]. So the number of quadrilaterals whose area is half the area of the square, counted without factoring out rotations, is 2N^3 - N^2.
Now work out how many of those are in each class:
Squares: the quadrilateral is of the form [x,x,x,x] and the condition for it to have half the area of the square is that x+x = 2N. Since x is required to be odd, this is impossible if N is even and only happens for the single case x=N if N is odd.
Parallelograms: the quadrilateral is of the form [x,y,x,y] and the condition for it to have half the area of the square is that x+x = 2N or y+y = 2N. Since x and y are required to be odd, this is impossible if N is even. If N is odd, it happens in N-1 cases with x equal to N and y not equal to N, and another N-1 with x not equal to N and y equal to N (the case with x=N and y=N is instead in the Squares class.
Others: if N is even, all 2N^3 - N^2 quadrilaterals with half the area of the square are in this class; if N is odd, the remaining 2N^3 - N^2 - 2(N-1) - 1 = 2N^3 - N^2 - 2N + 1 are in this class.
So a formula for counting the quadrilaterals with half the area of the square, with rotations factored out, is:
(2N^3 - N^2) / 4 if N is even
(2N^3 - N^2 - 2N + 1)/4 + 2(N-1)/2 + 1
= (2N^3 - N^2 - 2N + 1 + 4N - 4 + 4) / 4
= (2N^3 - N^2 + 2N + 1) / 4 if N is odd
> On 03/09/2020 16:13 Jean-Luc Manguin <jean-luc.manguin at unicaen.fr> wrote:
> The sequence A006528 can give the solution to this interesting (at least for me) problem :
> - put N points on each edge of a square ; the points are equally spaced.
> - you can draw a quadrilatere by drawing a line from a point of an edge to another point of the neighbour edge.
> - how many quadrilateres can you draw, taking the rotations in account ?
> The answer is given by the sequence above, and the formula (N^4 + N^2 + 2*N)/4 is easy to understand because N quadrilateres are squares and are invariant for any 90 degrees rotation, and N^2 are rectangles that are invariant for a 180 degrees rotation.
> Now, the interesting question for geometry lovers is : how many quadrilateres have a surface which is half of the surface of the bounding square ? The first numbers of this sequence (not in OEIS) are (0), 1, 3, 13, 28, 59 ....
> The theoretical formula is welcome !
> Best regards,
> JL Manguin
> Seqfan Mailing list - http://list.seqfan.eu/
Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan