0
$\begingroup$

From this page it can be shown that the number of possible rectangles in and m*n grid can be found by first choosing $2$ lines from a possible $m+1$ to form the vertical sides of the rectangle, and then $2$ from the $n+1$ horizontal sides, to give ${{m+1} \choose {2}}*{{n+1} \choose {2}}$ rectangles.

I want to extend this proof to cover only squares

I have tried choosing $2$ from ${m+1}$ for one set of sides, as a square can be formed with any two lines, but I am having trouble on how many choices there are for the remaining sides. If the first two sides are beside each other, then the last two can be any two sides that are beside each other, so there are so n choices, but after that I get lost.

The formula given on the page using a different approach is $$\frac {{n}{(2n+1)}{(n+1)}}{6}$$ or the sum of squares when m = n

$\endgroup$
8
  • $\begingroup$ Do you understand why the formula for choosing a squares from a square works? The case of choosing squares from a rectangle can easily be derived from this $\endgroup$
    – Dominik
    Commented Sep 10, 2015 at 19:21
  • $\begingroup$ Note: the formula for squares is only for the special case $m=n$. $\endgroup$
    – vadim123
    Commented Sep 10, 2015 at 19:21
  • $\begingroup$ Let $m\le n$. Count the number of $1\times 1$ squares, $2\times 2$ squares, and so on up to $m\times m$ and add up. The "sum of consevutive squares" formula will be useful. $\endgroup$
    – André Nicolas
    Commented Sep 10, 2015 at 19:24
  • $\begingroup$ @AndréNicolas I understand that proof, my question is where it is possible to prove this by choosing sides for the squares $\endgroup$
    – spyr03
    Commented Sep 10, 2015 at 19:26
  • $\begingroup$ Direct use of the choosing parallel lines idea is not useful. If $m\le n$ there are indeed $\binom{m+1}{2}$ ways to chose $2$ parallel sides. But some choices, like the two lines close together, give many squares, and some choices give few squares. $\endgroup$
    – André Nicolas
    Commented Sep 10, 2015 at 19:30

2 Answers 2

Reset to default
1
$\begingroup$

If you are ok with writing summations, and expressing your formla in terms of sum of multiplied expressions, then your're basically already there. If $m \leq n$ then you can write down an expression for how many $k \times k$ squares you can form by independently choosing the two indepentdent pairs of dividing lines for the horizontal and vertical dividing lines. Once you have this summation formula, then the only thing left to (possibly) do is see if you can reduce your summation formula to a more closed form solution.

$\endgroup$
1
  • $\begingroup$ Thank you, after I tried choosing lines for a fixed width k, it worked out well $\endgroup$
    – spyr03
    Commented Sep 10, 2015 at 20:31
1
$\begingroup$

You don't state your question carefully. It sounds like you are trying to determine the number of squares in an $m \times n$ grid (so $(m+1) \times (n+1)$ gridlines). I would suggest you count the sizes separately and add them up. Let us assume $m \le n$, so the largest square you can form is $(m+1) \times (m+1)$. There are $mn$ squares of size $1$, $(m-1)(n-1)$ squares of size $2$, down to $1\cdot (n-m+1)$ squares of size $m+1$, so the total is $$\sum_{i=1}^m(m+1-i)(n+1-i)$$ Now distribute out the terms and you get a sum of terms that do not depend on $i$, a sum that depends on $i^1$ and a sum that depends on $i^2$

$\endgroup$
1
  • $\begingroup$ thank you, it is a good answer, I just didn't understand it until had I worked the solution out, after seeing user2566092's answer $\endgroup$
    – spyr03
    Commented Sep 10, 2015 at 20:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .